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

我从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节点并在我的insert函数中对其进行初始化吗？

最佳答案

它基本上是一个占位符。

从代码自述文件:
/ *前哨用于root和nil。这些哨兵是
对RedBlackTreeCreate进行计算时创建。 root-> left应该始终指向树的根节点。 nil指向一个节点，该节点应始终为黑色，但具有子级和子级且没有键或信息。使用这些标记的目的是使根节点和零节点在代码中不需要特殊情况* /

从维基百科red-black tree

1.节点为红色或黑色。

2.根是黑色的。 (有时会忽略此规则。由于根始终可以从红色更改为黑色，但不一定相反，因此该规则对分析的影响很小。)

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

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

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

关于c++ - 红黑树插入实现-什么是前哨？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/25068106/