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

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，为什么要在构造函数中初始化它？我可以只在我的私有(private)数据字段中声明一个 nil 节点并在我的插入函数中初始化它吗？

Answer 1

它基本上是一个占位符。

来自代码自述文件:/* 哨兵用于 root 和 nil。这些哨兵是 在调用 RedBlackTreeCreate 时创建。 root->left 应该总是指向树的根节点。 nil 指向一个节点，该节点应始终为黑色但具有任意子节点和父节点并且没有 key 或信息。使用这些哨兵的目的是为了让根节点和 nil 节点在代码中不需要特殊情况 */

来自维基百科 red-black tree

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

2.根是黑色的。 (这条规则有时会被省略。由于根总是可以从红色变为黑色，但反之不一定，因此这条规则对分析影响不大。)

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

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

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