并非所有的红黑树都平衡吗？

Question

直观地，“平衡树”应该是每个节点处的左右子树的树，必须具有“大致相同”的节点。

当然，当我们谈论红黑树*（见最后的定义）是平衡的，我们实际上是指它们是 高度 平衡和从这个意义上讲，它们是平衡的。

假设我们尝试将上述直觉形式化如下：

定义： 一棵二进制树称为$ mu $ - 平衡，带有$ 0 le mu leq frac frac {1} {2} $，如果对于每个节点$ n $，则不等式

$$ mu le frac {| n_l | + 1} {| n | + 1} le 1- mu $$

持有，并且对于每$ mu' gt mu $，都有一些节点失败。 $ | n_l | $是$ n $的左子树中的节点数，$ | n | $是树下的节点数，$ n $作为root（包括root）。

我相信，这些被称为 重量平衡 关于该主题的一些文献中的树木。

可以证明，如果带有$ n $ nodes的二进制树是$ mu $ - balanced（对于常数$ mu gt 0 $），那么树的高度为$ nathcal {o}（ log n ）$，从而维护不错的搜索属性。

所以问题是：

是否有一些$ mu gt 0 $，以至于每一个足够大的红黑树都是$ mu $ - 平衡的？

---

我们使用的红黑树的定义（从Cormen等人的算法引入到算法）：

一个二进制搜索树，每个节点颜色为红色或黑色，并且

• 根是黑色的
• 所有空节点都是黑色的
• 如果一个节点是红色的，那么它的两个孩子都是黑色的。
• 对于每个节点，从该节点到后代无效节点的所有路径均具有相同数量的黑色节点。

注意：我们不计算上述$ mu $的定义中的空节点。 （尽管我相信我们是否这样做都没关系）。

Answer 1

宣称: ：红黑树可以任意地 -$ mu $-均衡。

证明想法: ：填充右子树用尽可能多的节点填充，并用尽可能少的节点填充给定数字 $ k $ 每个根叶路径上的黑色节点。

证明: ：定义序列 $ T_K $ 红黑树，这样 $ T_K $ 有 $ k $ 从根到任何（虚拟）叶的每个路径上的黑色节点。定义 $ t_k = b（l_k，r_k）$ 和

• $ r_k $ 完整的高度树 $ 2K-1 $ 第一个，第三，...水平的红色，其他的黑色，
• $ l_k $ 完整的高度树 $ k-1 $ 所有节点颜色为黑色。

显然，一切 $ T_K $ 是红黑树。

例如，这些是 $ T_1 $, $ T_2 $ 和 $ T_3 $, ， 分别：

---

^[资源]

---

^[资源]

---

^[资源]

---

现在让我们验证右侧的视觉印象 巨大的 与左派相比。我不会数虚拟叶子；它们不会影响结果。

左子树的 $ T_K $ 完整，总是有身高 $ k-1 $ 因此包含 $ 2^k -1 $ 节点。另一方面，右子树已完成并且具有高度 $ 2K-1 $ 因此包含 $ 2^{2K} -1 $ 节点。现在 $ mu $- 根的平衡值为

美元$

证明没有 $ mu> 0 $ 按照要求。

Answer 2

不。 考虑具有以下特殊结构的红黑树。

• 左子树是一棵完整的二进制树，具有深度$ d $，其中每个节点都是黑色的。
• 右子树是一棵完整的二进制树，深度为$ 2D $，其中每个节点在奇数深度为红色，并且每个节点均匀，均匀深度为黑色。

直接检查这是有效的红黑树。但是右边的子树中的节点数（$ 2^{2d+1} -1 $）大致是 正方形 左子树中的节点数（$ 2^{d+1} -1 $）。