插入红黑树

Question

我正在学习一个算法课程，在我的课程幻灯片中，有一个关于将节点插入红黑树的示例：

我的问题是，为什么我们不让“2”成为叶节点呢？如果我们让它成为叶节点，那么似乎不会违反红黑树的任何条件。我在这里错过了什么吗？

- user2110714

Answer 1

问题不在于图像中第二棵树的位置，而在于不同节点的颜色。以下是解释：

红黑树插入的第一条规则是：新插入的节点必须始终为红色。你遇到了第三种情况的插入，其中节点2的父节点和叔节点都是红色。因此，它们需要重新着色为黑色，祖父节点将变为红色，但由于祖父节点是根节点，所以它将再次变为黑色。

所以，在插入2后，新树应该像这样（r和b表示颜色，.b表示Nil节点）：

       5b
     /    \     
    1b     7b
  /   \    / \
 .b    2r .b  .b
       / \
      .b  .b

为什么我们总是需要在 RBT 中插入红色节点呢？你可能会问。答案是，首先我们知道 RBT 中每个 NIL 节点都是黑色的，其次我们有规则 5：从给定节点到任何后代叶子节点的每条简单路径都包含相同数量的黑色节点。如果我们在树的末尾插入黑色节点，那么树将违反此规则。只需将上面的树中的 2r 替换为 2b，并保持 1 和 7 的颜色为红色，然后从根节点到任何 Nil 节点计算黑色节点的数量，您将看到某些路径具有 2 个黑色节点，而某些路径具有 3 个黑色节点。

- sowrov

Answer 2

所有红黑树的叶子节点都必须是NIL。 检查属性3。

- noMAD

---

@noMAD：恐怕你的回答并没有回答问题。 - sowrov

@sowrov：我看了你的回答，你解释了插入操作，但是你没有回答OP的问题。他问：“为什么我们不让‘2’成为叶节点呢？”我刚刚回答了这个问题。 - noMAD

Answer 3

基于相同的思想，维基百科文章解释如下：

在许多树数据结构的演示中，一个节点只能有一个子节点，叶节点包含数据。可以按照这种范式呈现红黑树，但这会改变几个属性并使算法复杂化。因此，本文使用“空叶子”。

所以显然没有什么阻止你按照自己的方式进行，但你必须在算法中考虑到它，这会使它们显著复杂化。也许可以通过使用面向对象编程（OOP）来缓解这个问题，其中叶子包含元素，但行为类似于带有空叶子的节点。

无论如何，这是一种权衡：您在空间上获得的收益（在C中大约是两个指针设置为NULL），可能会在代码复杂性、计算时间或对象运行时表示（叶子的专门方法）方面失去。

- didierc

Answer 4

黑色节点高度不均匀。

如果你从根节点开始搜索NIL节点并计算黑色节点的数量，5-1-2-nil有三个，而5-7-nil或5-1-nil只有两个。

（规则：从给定节点到任何后代NIL节点的每条路径包含相同数量的黑色节点）

- jac