为什么红黑树总是以零节点作为它们的叶节点，这意味着什么?

Question

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

Answer 1

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

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

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

当您插入新节点时，另一种方法nil节点可以帮助我们识别我们所面临的情况(红叔或黑叔(，有时叔叔会可以是NIL节点

Answer 2

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

将红黑树定义为具有以下附加属性的二叉搜索树：

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

取任何具有NIL节点的红黑树，擦除NIL节点，它将满足上面的定义。反之，取一棵满足上述定义的树，将黑色的NIL节点放在每个少于两个子节点的非NIL节点下，这样它们就有两个子节点，根据标准定义，它将是一棵红黑树。