Ai đó có thể giải thích sự khác biệt chính giữa hai cấu trúc dữ liệu này là gì? Tôi đã cố gắng tìm một nguồn trực tuyến làm nổi bật sự khác biệt/tương đồng, nhưng tôi đã không tìm thấy bất cứ điều gì quá thông tin. Trong trường hợp nào người ta sẽ được ưu tiên hơn người kia? Những tình huống thực tế nào làm cho một tình huống "tốt hơn" để sử dụng hơn cái kia?Sự khác biệt giữa cây đỏ-đen và cây AVL
Trích dẫn từ này: Difference between AVL and Red-Black Trees
RB-Trees là, cũng như cây AVL, tự cân bằng. Cả hai đều cung cấp hiệu năng tìm kiếm và chèn O (log n). Sự khác biệt là RB-Trees đảm bảo O (1) phép quay cho mỗi thao tác chèn. Đó là những gì thực sự chi phí hiệu suất trong thực hiện thực tế. Được đơn giản hóa, RB-Trees đạt được lợi thế này từ khái niệm là 2-3 cây mà không mang theo chi phí của các cấu trúc nút động. RB-Cây vật lý được thực hiện như cây nhị phân, các cờ đỏ/đen mô phỏng hành vi 2-3.
theo định nghĩa, mỗi AVL do đó là tập con của Đỏ-Đen. Người ta có thể tô màu bất kỳ cây AVL nào mà không cần phải tái cơ cấu hay xoay vòng, để biến nó thành cây Đỏ-Đen.
Từ những gì tôi đã thấy có vẻ như cây AVL thực hiện nhiều phép quay (thỉnh thoảng gấp đôi cây) khi cần để có chiều cao mong muốn của cây AVL (Nhật ký n). Điều này làm cho nó cân bằng hơn.
Đối với cây màu đỏ đen, có 5 bộ quy tắc bạn cần phải đảm bảo duy trì việc chèn và xóa mà bạn có thể tìm thấy tại đây http://en.wikipedia.org/wiki/Red-black_tree.
Điều chính có thể giúp bạn cho cây đỏ đen là thực tế là tùy thuộc vào năm quy tắc bạn có thể đệ quy màu cây lên đến gốc nếu chú là màu đỏ. Nếu chú là màu đen, bạn sẽ cần phải làm tối đa hai phép quay để khắc phục bất kỳ vấn đề nào bạn có nhưng sau một hoặc hai phép quay mà bạn đã làm. Gói nó vào và nói chúc ngủ ngon vì đó là kết thúc của thao tác bạn cần làm.
Quy tắc lớn là số 5 ... 'Mọi đường dẫn đơn giản từ một nút nhất định đến bất kỳ phần tử con nào của nó đều có cùng số lượng nút đen'.
Điều này sẽ gây ra hầu hết các phép quay mà bạn cần để làm cho cây hoạt động và làm cho cây không bị mất quá nhiều.
Cây AVL duy trì sự cân bằng cứng nhắc hơn so với cây đỏ đen. Con đường từ gốc đến lá sâu nhất trong cây AVL là nhiều nhất ~ 1.44 lg (n + 2), trong khi ở những cây màu đen đỏ thì nó cao nhất ~ 2 lg (n + 1).
Kết quả là, tra cứu trong cây AVL thường nhanh hơn, nhưng điều này đi kèm với chi phí chèn và xóa chậm hơn do nhiều hoạt động xoay vòng hơn. Vì vậy, sử dụng một cây AVL nếu bạn mong đợi số lượng tra cứu để thống trị số lượng cập nhật cho cây.
Cây AVL thường được so sánh với cây đỏ đen vì cả hai đều hỗ trợ cùng một tập hợp các hoạt động và mất
O(log n)thời gian cho các hoạt động cơ bản. Đối với các ứng dụng chuyên sâu, các cây AVL nhanh hơn cây đỏ-đen vì chúng cứng rắn hơn. Tương tự như cây đỏ-đen, cây AVL có độ cân bằng cao. Cả hai đều nói chung không cân bằng trọng lượng và cũng không cân bằng for cho bất kỳ μ ≤ ½; có nghĩa là, các nút anh chị em có thể có số lượng con cháu rất khác nhau.
Từ Wikipedia Điều trên AVL Trees
Chiều cao tối đa của cây là quan trọng tối quan trọng để giữ thăng bằng. Nó gần như bằng 1.44 * log(n) cho AVL, nhưng đối với cây RB, nó là 2 * log(n). Vì vậy, chúng tôi có thể nhận được kết luận rằng nó là tốt hơn để sử dụng AVL khi vấn đề là khuyến khích tìm kiếm. Vấn đề là một câu hỏi khác cho cây AVL và RB. Cây RB tốt hơn AVL khi phải đối mặt với việc chèn ngẫu nhiên với chi phí thấp hơn của vòng quay nhưng AVL tốt để chèn dữ liệu tăng dần hoặc giảm dần. Vì vậy, nếu vấn đề là khuyến khích chèn, chúng ta có thể sử dụng cây RB.
Đối với dữ liệu nhỏ:
chèn: cây RB cây & AVL có hằng số của max xoay nhưng cây RB sẽ nhanh hơn bởi vì trên cây RB trung bình sử dụng rất ít vặn.
tra cứu: Cây AVL nhanh hơn, vì cây AVL có chiều sâu ít hơn.
xóa: Cây RB có số lần quay tối đa không đổi nhưng cây AVL có thể có thời gian xoay vòng O (log N) là tồi tệ nhất. và cây RB trung bình cũng có số vòng quay ít hơn nên cây RB nhanh hơn.
cho dữ liệu lớn:
chèn: cây AVL là nhanh hơn. vì bạn cần tìm kiếm một nút cụ thể trước khi chèn. khi bạn có nhiều dữ liệu hơn, sự chênh lệch thời gian khi tìm kiếm một nút cụ thể sẽ tăng tỷ lệ thuận với O (log N). nhưng cây AVL & Cây RB vẫn chỉ cần số vòng quay liên tục ở trường hợp xấu nhất. Vì vậy, cổ chai sẽ trở thành thời gian bạn tra cứu cho nút cụ thể đó.
tra cứu: Cây AVL nhanh hơn. (giống như trong trường hợp dữ liệu nhỏ)
xóa: Cây AVL nhanh hơn trung bình, nhưng trong trường hợp xấu nhất, cây RB nhanh hơn. vì bạn cũng cần tìm kiếm một nút rất sâu để hoán đổi trước khi xóa (tương tự như lý do chèn). trung bình cả hai cây đều có số vòng quay liên tục. nhưng cây RB có một giới hạn trên không đổi cho luân chuyển.
điều này có nghĩa là cây AVL hầu như luôn được ưa thích với lượng lớn dữ liệu. Làm thế nào nó được sử dụng trong Java và C++ STL? https://stackoverflow.com/questions/3901182/applications-of-red-black-trees – emschorsch
Bạn cần có số lượng dữ liệu nhất định (1 triệu ví dụ) để làm cho cây AVL tốt hơn cây RB trong trường hợp chèn/xóa, và nó thực sự phụ thuộc vào cách bạn thực hiện nó. Việc triển khai AVL thông minh có thể đánh bại std :: map ngay cả với lượng dữ liệu ít hơn. Ví dụ, bạn không cần phải kiểm tra xem đứa trẻ và cháu là null nếu cha mẹ-> chiều cao lớn hơn 5. –
Tóm lại: AvlTrees được cân bằng tốt hơn một chút so với RedBlackTrees. Cả hai cây đều lấy tổng thời gian O (log n) để tra cứu, chèn, và xóa, nhưng để chèn và xóa, cái cũ yêu cầu phép quay O (log n), trong khi cây chỉ mất O (1) phép quay.
Kể từ khi quay có nghĩa là văn bản cho bộ nhớ, và ghi vào bộ nhớ là tốn kém, RedBlackTrees là trong thực tế nhanh hơn để cập nhật hơn AvlTrees
Để có được một ý tưởng về làm thế nào một cây AVL làm việc, this trực quan tương tác giúp.
AVL cũng như RedBlack Trees là cấu trúc dữ liệu cây cân bằng chiều cao. Chúng khá giống nhau, và sự khác biệt thực sự bao gồm số hoạt động xoay được thực hiện khi thực hiện bất kỳ thao tác thêm/xóa nào - cao hơn trong trường hợp AVL, để duy trì sự cân bằng tổng thể đồng nhất hơn.
Cả hai tỷ lệ triển khai là O(lg N), trong đó N là số lá, nhưng trong thực tế, cây AVL nhanh hơn trên các nhiệm vụ tra cứu chuyên sâu: tận dụng cân bằng tốt hơn, các cây duyệt trung bình ngắn hơn. Mặt khác, chèn và xóa một cách khôn ngoan, một cây AVL sẽ chậm hơn: cần phải có số lần quay cao hơn để cân bằng lại đúng Cấu trúc dữ liệu khi sửa đổi.
Để thực hiện mục đích chung (ví dụ: ưu tiên không rõ ràng nếu tra cứu là phần lớn hoạt động), RedBlack Trees được ưu tiên: chúng dễ triển khai hơn và nhanh hơn trên các trường hợp phổ biến - bất cứ nơi nào Cấu trúc dữ liệu được sửa đổi thường xuyên như tìm kiếm. Ví dụ, TreeMap và TreeSet trong Java sử dụng sao lưu RedBlack Tree.
Thực tế là các cây RedBlack có ít phép quay hơn có thể làm cho chúng nhanh hơn khi chèn/xóa, tuy nhiên .... Vì chúng thường sâu hơn một chút Chúng cũng có thể chậm hơn khi chèn và xóa. Mỗi khi bạn đi từ một cấp độ trong cây đến tiếp theo, có một thay đổi lớn mà thông tin được yêu cầu không có trong bộ nhớ cache và phải được lấy ra từ RAM. Vì vậy, thời gian đạt được trên ít quay có thể đã bị mất vì nó phải điều hướng sâu hơn và do đó phải cập nhật bộ nhớ cache của nó thường xuyên hơn. Có thể hoạt động từ bộ nhớ cache hoặc không tạo ra sự khác biệt lớn. Nếu thông tin có liên quan nằm trong bộ nhớ cache, thì bạn có thể thực hiện nhiều thao tác xoay vòng, trong thời gian cần thiết để điều hướng cấp bổ sung và thông tin cấp tiếp theo không có trong bộ nhớ cache. Vì vậy trong trường hợp RedBlack là lý thuyết nhanh hơn, chỉ nhìn vào các hoạt động cần thiết, nó có thể chậm hơn trong thực tế, do nhớ cache.
Yêu cầu hiểu khái niệm tốt hơn. Cả cây avl và cây Đỏ Đen đều có tối đa hai vòng quay cho mỗi lần chèn. Vì vậy, làm thế nào bạn có thể nói cây AVL là chậm? Cảm ơn trước! – user2626445
@larsmans! Sự khác biệt về hiệu năng có phải là một khái niệm mới được tạo ra không? – Shashwat
@Shashwat Tôi không hiểu ý bạn là gì. Khái niệm mới? –