BST tự cân bằng tốt nhất để chèn nhanh số lượng lớn các nút

Question

Tôi đã có thể tìm thấy chi tiết về một số tự cân bằng BST s thông qua một số nguồn, nhưng tôi chưa tìm thấy bất kỳ mô tả tốt nào. để sử dụng trong các tình huống khác nhau (hoặc nếu nó thực sự không quan trọng).

Tôi muốn một BST tối ưu để lưu trữ vượt quá mười triệu nút. Thứ tự chèn các nút về cơ bản là ngẫu nhiên, và tôi sẽ không bao giờ cần phải xóa các nút, do đó, thời gian chèn là điều duy nhất cần được tối ưu hóa.

Tôi định sử dụng nó để lưu trữ trạng thái trò chơi đã truy cập trước đó trong trò chơi xếp hình, để tôi có thể nhanh chóng kiểm tra xem cấu hình trước đó đã gặp phải chưa.

Answer 1

Red-black tốt hơn AVL cho các ứng dụng chèn nặng. Nếu bạn thấy trước tương đối đồng nhất, thì Red-black là con đường để đi. Nếu bạn thấy trước một cái nhìn tương đối không cân bằng trong đó nhiều yếu tố được xem gần đây có nhiều khả năng được xem lại, bạn muốn sử dụng splay trees.

Answer 2

Hai tự cân bằng BST s Tôi quen thuộc nhất với màu đỏ-đen và AVL, vì vậy tôi không thể nói chắc chắn nếu có giải pháp nào khác tốt hơn, nhưng khi tôi nhớ lại, màu đỏ đen có chèn nhanh hơn và truy xuất chậm hơn so với AVL.

Vì vậy, nếu chèn là ưu tiên cao hơn truy xuất, màu đỏ đen có thể là giải pháp tốt hơn.

Answer 3

Tại sao lại sử dụng BST? Từ mô tả của bạn, một từ điển cũng sẽ hoạt động tốt, nếu không tốt hơn.

Lý do duy nhất để sử dụng BST sẽ là nếu bạn muốn liệt kê ra nội dung của vùng chứa theo thứ tự chính. Nó chắc chắn không có vẻ như bạn muốn làm điều đó, trong trường hợp đó đi cho bảng băm. O(1) chèn và tìm kiếm, không phải lo lắng về việc xóa, điều gì có thể tốt hơn?

Answer 4

[bảng băm có] O (1) chèn và tìm kiếm

Tôi nghĩ rằng điều này là sai.

Trước hết, nếu bạn giới hạn không gian khóa là hữu hạn, bạn có thể lưu trữ các phần tử trong một mảng và thực hiện quét tuyến tính O (1). Hoặc bạn có thể shufflesort mảng và sau đó làm một tuyến tính quét trong O (1) dự kiến ​​thời gian. Khi công cụ là hữu hạn, công cụ có thể dễ dàng O (1).

Vì vậy, giả sử bảng băm của bạn sẽ lưu trữ bất kỳ chuỗi bit tùy ý nào; nó không quan trọng lắm, miễn là có một bộ khóa vô hạn, mỗi khóa đều có giới hạn. Sau đó, bạn phải đọc tất cả các bit của bất kỳ truy vấn và chèn đầu vào, khác tôi chèn y0 vào một băm rỗng và truy vấn trên y1, trong đó y0 và y1 khác nhau ở một vị trí bit duy nhất mà bạn không nhìn vào.

Nhưng giả sử độ dài khóa không phải là tham số. Nếu chèn và tìm kiếm của bạn lấy O (1), cụ thể băm mất O (1) thời gian, có nghĩa là bạn chỉ nhìn vào một số lượng hữu hạn của đầu ra từ hàm băm (từ đó có khả năng là chỉ là một kết quả hữu hạn , được cấp).

Điều này có nghĩa là với nhiều nhóm hợp lý, phải có một chuỗi các chuỗi vô hạn mà tất cả đều có cùng giá trị băm. Giả sử tôi chèn rất nhiều, ví dụ: ω (1), trong số đó và bắt đầu truy vấn.Điều này có nghĩa là bảng băm của bạn phải rơi vào một số cơ chế tìm kiếm/chèn tìm O (1) khác để trả lời các truy vấn của tôi. Cái nào và tại sao không chỉ sử dụng trực tiếp?