Hãy chọn từng cái một, phải không?
Đối với nhiệm vụ tìm kiếm, không bao giờ. Về cơ bản, đặc tính hiệu suất của chúng sẽ hoàn toàn không thể dự đoán được và chi phí của việc cân bằng một cây sẽ không quá lớn để làm cho cây không cân bằng trở thành một giải pháp thay thế khả thi.
Ngoài ra, cây nhị phân không cân bằng tất nhiên có các ứng dụng khác, nhưng không phải là cây tìm kiếm.
Họ rất dễ để phát triển nhưng hiệu suất của chúng thường được vượt qua bởi các chiến lược cân bằng khác vì cân bằng chúng là tương đối tốn thời gian. Wikipedia claims rằng chúng hoạt động tốt hơn trong các kịch bản tìm kiếm chuyên sâu vì chiều cao của chúng thấp hơn một chút trong trường hợp xấu nhất.
Chúng được sử dụng trong hầu hết C++’std::map implemenations và có lẽ trong một vài thư viện tiêu chuẩn khác là tốt. Tuy nhiên, có good evidence rằng chúng thực sự kém hơn B (+) cây trong mỗi trường hợp do hành vi lưu vào bộ nhớ cache của CPU hiện đại. Trong lịch sử, khi bộ nhớ đệm không quan trọng (hoặc là tốt), chúng vượt qua cây B khi được sử dụng trong bộ nhớ chính.
Những đòi hỏi sự cân nhắc kỹ lưỡng nhất của tất cả các cây, vì hằng số khác nhau được sử dụng là về cơ bản các phép thuật "huyền diệu" liên quan đến cách kỳ lạ và đôi khi không thể đoán trước được với kiến trúc phần cứng cơ bản. Ví dụ: số lượng nút con tối ưu cho mỗi cấp có thể phụ thuộc vào kích thước của trang bộ nhớ hoặc dòng bộ nhớ cache.
Tôi biết không có quy tắc chung tốt để phân biệt giữa chúng.
hoàn toàn khác nhau. Tries cũng là các cây tìm kiếm, nhưng đối với việc truy xuất văn bản của các phần tử trong một kho văn bản. Một trie là một cây tiền tố không nén (tức là một cây trong đó các đường dẫn từ gốc đến các nút lá tương ứng với tất cả các tiền tố của một chuỗi đã cho).
Tries nên được so sánh với, và bù trừ, cây hậu tố, mảng hậu tố và chỉ số q-gram - không quá nhiều so với cây tìm kiếm khác vì dữ liệu rằng họ tìm kiếm khác: thay vì của các từ rời rạc trong một kho văn bản, cấu trúc chỉ mục sau cho phép tìm kiếm hệ số .
Như bạn đã nói, họ không được cây tìm kiếm ở tất cả.
bạn đang thiếu cây Andersson (còn gọi là cây AA), tương đương với cây 2-3 và có đặc điểm hiệu suất tương tự như cây đỏ đen, nhưng dễ thực hiện hơn – Christoph
một cây khác giống cấu trúc dữ liệu đang treaps – swegi
Và danh sách bỏ qua xác định! – Anna