bit*_*ise 5 algorithm tree red-black-tree binary-search-tree data-structures
我创建了一个双向链表，哨兵节点的好处很明显 - 列表边界处没有空检查或特殊情况。
现在我正在写一棵红黑树，并试图弄清楚这样的概念是否有任何好处。
我的实现基于本文的最后两个函数 （自上而下插入/删除）。作者使用“虚拟树根”或“头”来避免其插入/删除算法的根部出现特殊情况。作者的头节点的范围仅限于函数本身 - 似乎是因为它的用处有限。
我遇到的另一篇文章提到使用头部上方的永久根作为迭代的“结束”。这看起来很有趣，但我尝试了它，但没有看到比使用 NULL 作为结束迭代器有任何真正的好处。我还发现了几篇文章使用共享哨兵来表示所有空叶节点，但这似乎比第一种情况更没有意义。
谁能详细说明哨兵节点在红黑树中如何有用？