3

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

在此处输入图像描述

我的问题是，为什么我们不让“2”成为这里的叶节点？看起来如果我们让它成为一个叶子节点，那么就不会违反红黑树的条件。我在这里想念什么？

4

4 回答 4

2

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

红黑树中插入的第一条规则是：新插入的节点必须始终是红色的。您属于案例 3 插入，其中节点 2 的父亲和叔叔都是红色。因此需要将它们重新着色为黑色，祖父将变为红色，但由于祖父是根，因此它将再次变为黑色。

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

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

为什么我们总是需要在彩铃中插入红色节点，你可能会问？答案是，第一个我们知道每个 NIL 节点在 RBT 中总是黑色的，第二个我们有规则 5。Every simple path from a given node to any of its descendant leaves contains the same number of black nodes.现在如果我们在最后插入一个黑色节点，树将违反此规则，只需将 2b 放在上面的树中而不是 2r 并保持颜色1 和 7 红色，然后计算从根到任何 Nil 节点的黑色节点，你会看到一些路径有 2 个后节点，一些路径有 3 个黑色节点。

于 2013-03-22T17:38:59.770 回答
1

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

于 2013-03-22T16:05:58.220 回答
0

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

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

所以很明显，没有什么能阻止你按照自己的方式去做，但是你必须在你的算法中考虑到它，这使得它们变得更加复杂。也许这个问题可以通过使用 OOP 来缓解，其中叶子包含元素，但表现为具有空叶子的节点。

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

于 2013-03-22T17:53:55.110 回答
0

黑高不均匀。

如果计算从根节点搜索 NIL 节点的黑人节点的数量，5-1-2-nil 有 3 个，5-7-nil 或 5-1-nil 只有两个。

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

于 2016-09-04T11:44:48.233 回答