Xóa trong các cây màu đỏ thẫm trái

Question

Tôi đang tìm hiểu về Left Leaning Red Black Trees.

Trong thuật toán xóa được nêu trong bài báo, nếu khóa phù hợp cho nút và nhánh phải là NULL cho nút đó, thì nút đó sẽ bị xóa. Nhưng có thể có một subtree trái cũng không được xem xét.

Tôi không thể hiểu được tại sao subtree bên trái là NULL cũng như. Điều tương tự cũng được thực hiện khi xóa tối thiểu hoặc tối đa. Bất cứ ai có thể xin vui lòng hướng dẫn tôi về điều này?

Answer 1

Có vẻ như bạn đang nói về đoạn mã này:

if (isRed(h.left)) 
    h = rotateRight(h); 
if (key.compareTo(h.key) == 0 && (h.right == null)) 
    return null; 

hậu duệ Dưới đây trái không thể "đỏ" vì trước mã sẽ xoay nó sang bên phải.

Hậu duệ bên trái không được "đen" vì trong trường hợp này có đường dẫn bên trái h chứa ít nhất một nút "đen" trong khi không có đường dẫn nào bên phải có nút "đen". Nhưng trong RB-cây số lượng các nút màu đen trên mỗi con đường phải giống nhau.

Điều này có nghĩa là không có hậu duệ bên trái nào cả và nút h là nút lá.

Trong chức năng deleteMin không cần kiểm tra cây con nếu cây con trái trống vì không có cây con phải của cây LLRB có thể lớn hơn cây con trái tương ứng.

Answer 2

Có một phân tích thú vị về việc liệu các cây đen đỏ có trái thực sự tốt hơn hay đơn giản hơn các triển khai trước đó. Bài viết Left-Leaning Red Black Trees Considered Harmful được viết bởi giáo sư Harvard Comp Sci Eddie Kohler. Ông viết:

Tricky writing 

Sedgewick’s paper is tricky. As of 2013, the insert section presents 2–3–4 trees as 
the default and describes 2–3 trees as a variant. The delete implementation, however, 
only works for 2–3 trees. If you implement the default variant of insert and the 
only variant of delete,your tree won’t work. The text doesn’t highlight the switch 
from 2–3–4 to 2–3: not kind.