红黑树插入实现-哨兵是什么？

Question

我从http://web.mit.edu/~emin/www.old/source_code/cpp_trees/index.html获取了这段代码。这个红黑树节点的构造函数如下：

RedBlackTree::RedBlackTree()
{
  nil = new RedBlackTreeNode;
  nil->left = nil->right = nil->parent = nil;
  nil->red = 0;
  nil->key = MIN_INT;
  nil->storedEntry = NULL;

  root = new RedBlackTreeNode;
  root->parent = root->left = root->right = nil;
  root->key = MAX_INT;
  root->red=0;
  root->storedEntry = NULL;  
}

什么是nil，为什么在构造函数中初始化它？我能否只声明一个空节点在我的私有数据字段中，并在插入函数中初始化它？

- user3871143

---

nil 是一个叶子节点。看红黑树的一种方式是将所有叶子节点视为 nil 节点。 - scohe001

http://en.wikipedia.org/wiki/Sentinel_value - Ed S.

Answer 1

这基本上是一个占位符。

根据代码 README： /* 当 RedBlackTreeCreate 被调用时，会使用一个哨兵节点作为根节点和 NIL 节点。root->left 应该始终指向树的根节点，NIL 指向一个节点，该节点应始终为黑色，但具有任意子节点和父节点以及没有键或信息。使用这些哨兵的目的是使根节点和 NIL 节点在代码中不需要特殊情况 */

来自维基百科 红黑树

1.一个节点要么是红色的，要么是黑色的。

2.根节点是黑色的。(此规则有时被省略。因为可以将根节点从红色更改为黑色，但不一定反之，所以此规则对分析影响较小。)

3.所有叶子（NIL）都是黑色的。(所有叶子与根节点颜色相同.)

4.每个红色节点必须有两个黑色子节点。

5.从给定节点到其任何后代叶子的路径包含相同数量的黑色节点。

- Camron_Godbout

Answer 2

一个哨兵是一个空节点，它被用来代替nullptr，因为它消除了所有边角情况的特殊处理需求，例如最后一个节点、第一个节点等。

- sp2danny