6
Làm cách nào để tìm kiếm "cân bằng" cây tìm kiếm bậc ba? Hầu hết các triển khai tst không giải quyết cân bằng, nhưng đề nghị chèn theo thứ tự tối ưu (mà tôi không thể kiểm soát.)Cân bằng cây tìm kiếm thứ ba
A
Trả lời
4
Bài viết trong Dr. Dobbs về số Ternary Search Trees cho biết: D.D. Sleator và R.E. Tarjan mô tả các thuật toán cân bằng lý thuyết cho cây tìm kiếm bậc ba trong "Cây điều chỉnh nhị phân tự điều chỉnh" (Tạp chí ACM, tháng 7 năm 1985). Bạn có thể tìm thấy các phiên bản trực tuyến của bài báo này bằng công cụ tìm kiếm yêu thích của bạn.
0
Tổng quát cây tìm kiếm nhị phân là B-Tree, hoạt động cho các fanouts ở bất kỳ đâu từ 2 trở lên. Đó không phải là cách duy nhất để làm điều đó, nhưng đó là một cách phổ biến.
Về cơ bản, cách hoạt động là nếu chèn hoặc xóa sẽ khiến cây mất cân bằng, nó đánh cắp phần tử hoặc khoảng trống từ nút lân cận. Nếu thậm chí không đủ để giữ cho cây cân bằng, chiều cao của nó sẽ được thay đổi để nhường chỗ cho nó.
+0
Cuộc đàm phán OP về các cây tìm kiếm ** ternary **. – hmuelner
+0
Tôi không rõ ràng về cách cây 1-2 B-Tree khác với cây Ternary. Bạn có thể giải thích điều đó cho tôi không? – SingleNegationElimination
+1
Một B-Tree (thường) chứa toàn bộ các phím trong các nút. Trong cây tìm kiếm thứ ba, khóa được định nghĩa bởi đường dẫn đến nút. – hmuelner
1
đọc bài viết này:
"tự điều chỉnh của ternary tìm kiếm sẽ thử dùng Xoay có điều kiện và ngẫu nhiên Heuristics" bởi "Ghada Hany Badr * và B. John Oommen †"
nó sẽ giúp bạn để hiểu sự tự điều chỉnh và cân bằng TST.
Các vấn đề liên quan
- 1. Cây tìm kiếm nhị phân cân bằng hoàn hảo
- 2. Xây dựng cây tìm kiếm nhị phân cân bằng
- 3. cân bằng cây AVL (C++)
- 4. Các bảng băm và các cây tìm kiếm tự cân bằng
- 5. Cây nhị phân tìm kiếm cân bằng ― chỉ lưu trữ dữ liệu trong lá
- 6. trọng lượng không cân bằng cây AVL
- 7. Cây tìm kiếm nhị phân trên cây AVL
- 8. Cân bằng một cây nhị phân (AVL)
- 9. Định nghĩa của một cây cân bằng
- 10. Tìm kiếm bằng tiếng Ba Lan cho Nhân sư?
- 11. Cây tìm kiếm nhị phân tích hợp trong Python?
- 12. Xây dựng cây nhị phân cân bằng với foldr
- 13. Bảng băm so với cây nhị phân cân bằng
- 14. tìm kiếm xpath trên cây con
- 15. Cây tìm kiếm nhị phân đệ quy
- 16. Tìm kiếm CMS của bên thứ ba để tích hợp với trang web MVC
- 17. nếu chữ cái thứ ba bằng
- 18. Mất cân bằng trong việc tìm hiểu
- 19. Thứ tự cấp bậc in Tìm kiếm nhị phân Định dạng cây
- 20. Tìm hiểu về cấu trúc cây tìm kiếm nhị phân
- 21. Cách nhanh nhất để tìm giá trị cao nhất/thứ hai thứ ba (thứ ba ...) trong vector hoặc cột
- 22. Ví dụ của Wikipedia về cây AVL không cân bằng thực sự không cân bằng như thế nào?
- 23. Tìm giấy phép của bên thứ ba với Nuget
- 24. Tha thứ/tìm kiếm mờ với LINQ
- 25. Tìm kiếm việc thực thi cây hậu tố trong C#?
- 26. Vùng lân cận gần nhất Tìm kiếm bằng Python mà không có cây k-d
- 27. Tìm kiếm mẫu bằng Parsec
- 28. đại diện cho cây tìm kiếm nhị phân trong python
- 29. Tìm kiếm một từ để "làm phẳng một cây"
- 30. Tìm kiếm nhị phân Cây C thực hiện
Cây tìm kiếm lớn bao nhiêu? –
Một vài nghìn từ có từ 4 đến 20 ký tự. Không chắc chắn nếu đó là lớn hay nhỏ, nhưng nó lớn đối với tôi. – uroc
Âm thanh như vứt bỏ cây khi nó đến một điểm nhất định và thay thế nó bằng một cây được xây dựng với 'thứ tự tối ưu' là đặt cược tốt nhất của bạn - sẽ mất một phần nghìn giây, nếu bạn có thể dành thời gian. –