紅黑樹僞代碼冗餘

在算法第三版的介紹中，他們有一個紅黑樹刪除的僞代碼實現。這是...紅黑樹僞代碼冗餘

RB-DELETE(T, z) 
    y = z 
    y-original-color = y.color 
    if z.left == T.nil 
     x = z.right 
     RB-TRANSPLANT(T, z, z.right) 
    elseif z.right == T.nil 
     x = z.left 
     RB-TRANSPLANT(T, z, z.left) 
    else 
     y = TREE-MINIMUM(z.right) 
     y-original-color = y.color 
     x = y.right 
     if y.p == z 
       x.p = y  // <--------- why???? 
     else 
       RB-TRANSPLANT(T, y, y.right) 
       y.right = z.right 
       y.right.p = y 
     RB-TRANSPLANT(T, z, y) 
     y.left = z.left 
     y.left.p = y 
     y.color = z.color 
    if y-original-color == BLACK 
     RB-DELETE-FIXUP(T, x)

樹最小剛剛發現樹中的最小值，RB移植需要第二個參數的家長和有它點到第三個參數，並有第三個參數的父成爲第二個參數的父代。

通過我的評論，他們測試y.p是否爲z，如果是，則將x.p設置爲y。但是x已經是y.right，所以這就像說y.right.p = y，但y.right.p已經是y！他們爲什麼這樣做？

這裏是他們的解釋...

「如y的原母公司爲z，但是，我們不希望x.p點到y的原始親本，因爲我們將要從樹節點。由於節點Y會因此向上取個Z在樹中的位置，在線路設置XP爲y 13使XP點爲y的父的原始位置，甚至如果x == T.nil。」

他們希望保持x的父母是y ...它已經是y ...

來源

2011-04-21 confused

他們在文中說x也可以是無，即當y.right是無。看起來Nil在這個代碼中也是由一個節點代表的，他們不想留下一個懸掛指針。

來源

2011-04-21 15:17:31

啊我明白了！燈泡。當他們表示他們將利用T.nil節點具有左，右和父屬性的事實時，這就是他們的意思。謝謝！ – confused 2011-04-21 15:37:04

爲了向其他人澄清，T.nil是代表樹中所有葉節點的節點。沒有它，你會有O（2^h）無葉，這是浪費空間。 T.nil的屬性，左，右，父，是任意的。所以當x = y.right時，如果x = T.nil，那麼x的父親不會是y。如果最後一次調用RB-DELETE-FIXUP（T，x）要正常工作，它需要設置爲y。 – confused 2011-04-21 16:08:58

紅黑樹僞代碼冗餘

回答

相關問題