algorithm - 无限数量的最大不平衡红黑树

Question

我必须找到一个最大不平衡的红黑树家族，并证明该家族的“各自的属性”，以证明存在一个无限大的红黑树家族，其高度接近 2log(n+ 1).

现在我的猜测是，这个家族基本上由所有红黑树组成，这些红黑树的一条路径带有 s-r-s-r ... 节点，其余路径充满黑色节点。但我如何证明这一点？我如何正式写下这样一个家庭的样子？

谢谢!

Answer 1

Now my guess is that this family consists of basically all the red black trees that have one path with s-r-s-r ... nodes and the rest filled with black nodes.

这是一个合理的猜测。

But how do I prove this?

描述树 T_0、T_1、T_2、T_3、... 的无限序列，使得对于每个整数 n，序列中存在一棵至少具有 n 个节点的树。证明存在常数 C，使得对于每个 i，T_i 的高度至少为 2log(n_i+1) - C，其中 n_i 是 T_i 中的节点数。 (这是对“接近”这个含糊不清的术语的一种可能解释。)

how do i formally write down how such a family looks like?

归纳。我将以全黑树为例。树 T_0 是空的(基本情况)。对于所有整数 i > 0，树 T_i 由一个黑色节点组成，其左右子树等于 T_{i-1}(归纳步骤)。然后您可以使用归纳法证明关于这些树的事实。