问题描述
我创建了一个双向链接列表，并且前哨节点的好处很明显-在列表边界没有空检查或特殊情况.
I created a doubly-linked list, and the benefits of a sentinel node were clear - no null checks or special cases at list boundaries.
现在我正在写一棵红黑树，试图弄清楚这种概念是否有好处.
Now I'm writing a red black tree, and trying to figure out if there is any benefit to such a concept.
我的实现基于 这篇文章 (自上而下的插入/删除).作者使用虚拟树的根"或头"来避免其插入/删除算法的特殊情况.作者的头节点仅限于功能本身-似乎是由于其用途有限.
My implementation is based on the last two functions in this article (top down insertion/deletion). The author uses a "dummy tree root" or "head" to avoid special cases at the root for his insertion/deletion algorithms. The author's head node is scoped to the functions themselves - seemingly due to it's limited usefulness.
我碰到的另一篇文章提到使用头顶上方的永久根作为迭代的终点".这似乎很有趣，但是我尝试了一下，但看不到使用NULL作为最终迭代器的任何实际好处.我还发现了几篇文章，它们使用一个共享的哨兵来表示所有空叶节点，但这似乎比第一种情况更没有意义.
One other article I came across mentioned using a permanent root above the head as an "end" for iteration. This seems interesting, but I tried it and couldn't see any real benefit over using NULL as an end iterator. I also found several articles that used a shared sentinel to represent all empty leaf nodes, but this seems even more pointless than the first case.
任何人都可以详细说明前哨节点在红黑树中的用处吗?
Can anyone elaborate on how a sentinel node would be useful in a red black tree?
推荐答案
红黑树实现几乎总是对所有叶子使用一个黑哨兵.
Red-black tree implementations almost always use one black sentinel for all the leaves.
当您可以检查颜色而无需先检查null时，它将节省大量的null检查.
It saves a lot of null checks when you can check color without checking for null first.
当然，这在使用父指针的实现中不起作用.在这些实现中，通常不使用叶子标记，因为您需要为每个叶子位置分配一个不同的标记，这会浪费大量内存.
This doesn't work in implementations that use parent pointers, of course. In those implementations leaf sentinels usually aren't used because you'd need to allocate a different sentinel for each leaf position, and that's a waste of much memory.
这篇关于红黑树中的前哨节点的好处?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！