为什么红黑树总是将 nil 节点作为它们的叶节点，这意味着什么？

Question

我不知道为什么我们需要NIL节点作为红黑树中的叶子节点。谁能解释一下它的用途？

Answer 1

NIL是一种特殊类型的节点，它表示其他树如二叉搜索树和AVL树中的叶节点

NIL 节点有助于平衡黑色高度

当你删除一个节点时，黑色高度会立即传递给子节点，如果它没有子节点，它必须传递给某人......所以 NIL 节点有助于它

另一种方式，当你插入一个新节点时，nil节点帮助我们识别我们所面临的情况（无论是红色叔叔还是黑色叔叔）有时叔叔可以是NIL节点

Answer 2

红黑树不需要NIL节点。实际上，在该结构的典型实现中，完全省略了 NIL 节点以减少内存消耗。此外，我们可以改变红黑树的定义来避免提及 NIL 节点，而不会丢失结构的任何基本特性：

将红黑树定义为具有

附加属性的二叉搜索树

1. 每个节点都有一个颜色属性，要么是红色要么是黑色。
2. 如果黑色节点只有一个子节点，则子节点必须是红色和一片叶子。
3. 红色节点要么是叶节点，要么有两个黑色子节点。
4. 从根到叶的所有路径必须具有相同数量的黑色节点。

任意取一个NIL节点的红黑树，擦除NIL节点，就满足上面的定义。反之，取一棵满足上述定义的树，将黑色NIL节点放在每个子节点少于两个的非NIL节点下面，使它们有两个子节点，那么按照标准定义就是一棵红黑树。