刪除左傾紅黑樹

Question

我正在學習約Left Leaning Red Black Trees。

在論文中提到的刪除算法中，如果密鑰與節點匹配，並且右側子樹對於該節點爲NULL，則刪除該節點。但是可能有一個左子樹也是沒有考慮的。

我無法理解爲什麼左子樹也是NULL。在刪除最小值或最大值時也會做類似的事情。任何人都可以請指導我呢？

Answer 1

看來你正在談論這一段代碼：

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

這裏留下後代不能爲「紅色」，因爲前面的代碼將它旋轉到正確的。

另外左後裔不能是「黑色」，因爲在這種情況下，有一條路徑在h的左側包含至少一個「黑色」節點，而沒有任何路徑右側有任何「黑色」節點。但是在RB樹中，每條路徑上的黑色節點數量必須相同。

這意味着根本沒有左後裔，並且節點h是葉節點。

在deleteMin函數中，如果左子樹是空的，則不需要檢查右子樹，因爲LLRB樹的右子樹不會比對應的左子樹大。

Answer 2

有一個有趣的分析，是否左傾紅黑樹比以前的實現更好或更簡單。文章Left-Leaning Red Black Trees Considered Harmful由Harvard Comp Sci教授Eddie Kohler編寫。他寫道：

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.