Tại sao triển khai dựa trên cây đỏ đen cho TreeMap java?

Question

Đoạn thứ ba của wikipedia's article on AVL trees nói: "Vì cây AVL cân bằng hơn, chúng nhanh hơn cây đỏ-đen cho các ứng dụng chuyên sâu tra cứu".

Vì vậy, không nên TreeMap được triển khai bằng cách sử dụng cây AVL thay vì cây đỏ đen (vì sẽ có nhiều tìm kiếm các ứng dụng chuyên sâu hơn cho cấu trúc dữ liệu dựa trên băm)?

Answer 1

Cây đỏ-đen là mục đích chung hơn. Chúng tương đối tốt khi thêm, xóa và tra cứu nhưng cây AVL có giao diện nhanh hơn với chi phí thêm/xóa chậm hơn. Chính sách chung của Java là cung cấp các cấu trúc dữ liệu mục đích chung tốt nhất. Nó cũng là lý do tương tự của Java mặc định Array.sort (Object [] a) thực hiện là ổn định, thích ứng, lặp lại sắp xếp hợp nhất thay vì quicksort.

Answer 2

Bài viết trên Wikipedia sai (hoặc ít nhất, không có trích dẫn hỗ trợ để sao lưu xác nhận quyền sở hữu). Đúng là chiều cao trường hợp xấu nhất của cây AVL (1.44 lg n) tốt hơn chiều cao trường hợp xấu nhất của BST màu đỏ đen (2 lg n), nhưng đây là trường hợp xấu nhất và có thể không có nhiều việc phải làm với hiệu suất thực tế.

Answer 3

Trước đây, số lần quay được cho là rất quan trọng vì vậy cây đỏ đen được chọn trên AVL vì màu đỏ đen thực hiện phép quay ít hơn một chút với chèn ngẫu nhiên - .6 so với 7 trung bình mỗi lần chèn.

Trong chế độ hindsight, cây AVL có lẽ sẽ là lựa chọn tốt hơn. Bạn có thể thấy so sánh hiệu suất của AVL & cây đỏ-đen trong Java tại đây: https://refactoringlightly.wordpress.com/2017/10/29/performance-of-avl-red-black-trees-in-java/

Với chèn ngẫu nhiên, hiệu suất là tương tự. Với dữ liệu tuần tự, cây AVL hoạt động tốt hơn nhiều - 30% trở lên.