我必须找到一个最大不平衡的红黑树家族,并证明该家族的“各自属性”,以证明存在一个无限大的红黑树家族,其高度接近 2log(n+1)。
现在我的猜测是,这个家族基本上由所有的红黑树组成,这些树有一条带有 srsr ... 节点的路径,其余的则充满黑色节点。但我如何证明这一点?我如何正式写下这样一个家庭的样子?
谢谢!
我必须找到一个最大不平衡的红黑树家族,并证明该家族的“各自属性”,以证明存在一个无限大的红黑树家族,其高度接近 2log(n+1)。
现在我的猜测是,这个家族基本上由所有的红黑树组成,这些树有一条带有 srsr ... 节点的路径,其余的则充满黑色节点。但我如何证明这一点?我如何正式写下这样一个家庭的样子?
谢谢!
现在我的猜测是,这个家族基本上由所有的红黑树组成,它们有一条带有 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}(归纳步骤)。然后,您可以使用归纳法证明有关这些树的事实。