algorithm - 红黑树中哨兵节点的好处？

Question

我创建了一个双向链表，哨兵节点的好处很明显——在列表边界没有空检查或特殊情况。

现在我正在写一棵红黑树，并试图弄清楚这样的概念是否有任何好处。

我的实现基于 this article 中的最后两个函数
(自上而下插入/删除)。作者使用“虚拟树根”或“头”来避免其插入/删除算法在根处出现特殊情况。作者的头节点仅限于函数本身——似乎是因为它的用处有限。

我遇到的另一篇文章提到使用头部上方的永久根作为迭代的“结束”。这看起来很有趣，但我尝试过，并没有看到使用 NULL 作为结束迭代器的任何真正好处。我还发现了几篇文章，使用共享哨兵来表示所有空叶节点，但这似乎比第一种情况更没有意义。

谁能详细说明哨兵节点在红黑树中的作用？

Answer 1

红黑树实现几乎总是对所有叶子使用一个黑色哨兵。

当您可以检查颜色而不先检查空值时，它可以节省大量空值检查。

当然，这在使用父指针的实现中不起作用。在这些实现中，通常不使用叶子哨兵，因为您需要为每个叶子位置分配不同的哨兵，这会浪费很多内存。