Cây đỏ-đen có hình dạng như thế nào với 2-3-4 cây?

Question

Tôi có một sự hiểu biết cơ bản về cả hai cây đen đỏ và 2-3-4 cây và cách chúng duy trì cân bằng chiều cao để đảm bảo rằng các trường hợp xấu nhất là O (n logn).

Nhưng, tôi không thể hiểu được văn bản này từ Wikipedia

2-3-4 cây được một isometry cây đỏ-đen, có nghĩa rằng họ là tương đương với cấu trúc dữ liệu. Nói cách khác, đối với mỗi cây 2-3-4, có tồn tại ít nhất một cây đỏ-đen với các phần tử dữ liệu theo cùng thứ tự. Hơn nữa, chèn và xóa các hoạt động trên 2-3-4 cây gây ra các nút mở rộng, chia tách và hợp nhất tương đương với việc đảo màu và quay trong các cây đỏ đen.

Tôi không thấy cách hoạt động tương đương. Trích dẫn này có chính xác trên Wikipedia không? Làm thế nào có thể thấy rằng các hoạt động tương đương?

Answer 1

rb-tree (đỏ-đen-cây) không phải là đẳng cấu đến 2-3-4 cây. Bởi vì 3-node trong 2-3-4-tree có thể được nạc sang trái hoặc phải nếu chúng ta cố gắng ánh xạ 3-node này tới một rb-tree. Nhưng llrb-tree (cây đỏ-đen trái).

Words từ Robert Sedgewick (Trong Introduction phần):

In particular, the paper describes a way to maintain 
a correspondence between red-black trees and 2-3-4 trees, 
by interpreting red links as internal links in 3-nodes and 
4-nodes. Since red links can lean either way in 3-nodes 
(and, for some implementations in 4-nodes), the correspondence is not necessarily 1-1 

Cũng Page29 và Page30 của presentation từ Robert Sedgewick. Đây là bài trình bày về cây LLRB.

Và phần "Tương tự với cây B của đơn đặt hàng 4" của "Cây đỏ đen" trong wikipedia, nó chứa biểu đồ tốt.