我必须找到一个最大不平衡的红黑树家族，并证明该家族的“各自属性”，以证明存在一个无限大的红黑树家族，其高度接近 2log(n+1)。
现在我的猜测是，这个家族基本上由所有的红黑树组成，这些树有一条带有 srsr ... 节点的路径，其余的则充满黑色节点。但我如何证明这一点？我如何正式写下这样一个家庭的样子？
谢谢！
问问题
261 次
1 回答
2
现在我的猜测是，这个家族基本上由所有的红黑树组成，它们有一条带有 srsr ... 节点的路径，其余的则充满黑色节点。
这是一个合理的猜测。
但我如何证明这一点？
描述一个无限的树 T_0, T_1, T_2, T_3, ... 序列，使得对于每个整数 n，在序列中存在一个至少有 n 个节点的树。证明存在一个常数 C，使得对于每个 i，T_i 的高度至少为 2log(n_i+1) - C，其中 n_i 是 T_i 中的节点数。（这是对“接近”这个模棱两可的术语的一种可能解释。）
我如何正式写下这样一个家庭的样子？
归纳地。我将以全黑树为例。树 T_0 为空（基本情况）。对于所有整数 i > 0，树 T_i 由一个黑色节点组成，其左右子树等于 T_{i-1}（归纳步骤）。然后，您可以使用归纳法证明有关这些树的事实。
于 2013-07-10T18:28:43.450 回答