紅黑樹 - 用兩個非葉孩子擦除節點

我一直在實現我自己的紅黑樹版本，主要基於我的算法從維基百科（http://en.wikipedia.org/wiki/Red-black_tree）。它的大部分內容相當簡潔，但有一部分我想澄清。紅黑樹 - 用兩個非葉孩子擦除節點

從具有2個非葉子（非NULL）子樹的樹中刪除一個節點時，它說將兩邊的子節點移動到可刪除節點並刪除該子節點。

我有點困惑，基於這一點，要刪除哪一方。我是否會隨機挑選一邊，是否在兩邊交替切換，還是每次刪除時都堅持同一邊？

來源

2010-04-03 Salami

如果您對輸入數據沒有任何先驗知識，則無法知道哪一方更有利於成爲新的中間節點或新的子節點。

因此，您可以適用最適合您的規則（最容易編寫/計算 - 可能「總是拿左邊的」）。採用隨機方案通常會引入更多不必要的計算。

來源

2010-04-03 09:00:16 ypnos

+1 - 避免故意引入隨機行爲;在某些情況下，某處會有bug，隨機行爲會使bug的效果更加令人困惑，難以一致地重現，等等。 – 2010-04-03 09:05:07

同意。值得引入隨機行爲的一種情況是使病態的最壞情況行爲以低概率和不可預知的方式發生，而不是在某些輸入上可預測地發生。因此，在發明introsort之前qsort中的隨機樞軸選擇。我不認爲紅黑樹的最壞情況行爲足以證明這裏是正確的。有一個衆所周知的隨機「可能平衡」的樹形結構，我暫時不記得它的名字。 – 2010-04-03 09:27:00

感謝您的快速響應！ – Salami 2010-04-03 09:49:13

紅黑樹 - 用兩個非葉孩子擦除節點

回答

相關問題