紅黑樹中的哨兵節點的好處？

Question

我創建了一個雙向鏈表，並且哨兵節點的好處很明顯 - 在列表邊界沒有空檢查或特殊情況。

現在我正在寫一個紅黑樹，並試圖弄清楚這樣一個概念是否有任何好處。

我的實現是在this article （自頂向下插入/刪除）的基礎上最後兩個功能。作者使用「虛擬樹根」或「頭」來避免根插入/刪除算法的特殊情況。作者的頭節點的作用範圍本身 - 看起來是因爲它的有用性有限。

我碰到過的另一篇文章提到在頭部上方使用永久根作爲迭代的「結束」。這似乎很有趣，但我試過了，並且看不到使用NULL作爲結束迭代器的任何真正的好處。我還發現了一些使用共享標記來表示所有空葉節點的文章，但這似乎比第一種情況更無意義。

任何人都可以詳細說明一個哨兵節點如何在紅黑樹中有用嗎？

Answer 1

紅黑樹實現幾乎總是使用一個黑色哨兵所有的葉子。

它可以節省大量的空檢查時，您可以檢查顏色，而不先檢查null。

當然，這在使用父指針的實現中不起作用。在那些實現中，葉哨兵通常不會被使用，因爲你需要爲每個葉子位置分配一個不同的哨兵，這就浪費了很多內存。