tree - 为什么红黑树的高度最多为 2 * O(ln N + 1)？

Question

具有 n 个内部节点的红黑树的高度最多为 2 * O(ln N + 1)。换句话说，红黑树的高度最多是最优的两倍。

谁能直观地解释为什么会这样？我不是在寻找归纳证明（我可以在网上找到它们）。这只是一个直观的原因吗？我想不出一个 RB 树的高度最多为 2 * O(ln N + 1) 的例子。

Answer 1

该链接为该定理提供了直观的证明。

下面，我将简单地过一遍证明的步骤：

1. 将红色节点与其黑色父节点合并，得到一棵新树。
2. 生成的树将具有分支 2、3 或 4 个子节点的节点。
3. 观察：新树的黑色高度 h' 将与原始树的黑色高度相同。
4. 观察：新树的高度h'至少可以是原树高度h的一半。（即我们有 h' >= h/2）
5. 高度为 h' 的完全二叉树有 2^h' -1 个内部节点。
   • 记住第 2 步，我们的新树在内部节点中分支 2、3 或 4。
   • 因此，新树的内部节点数超过 2^h' -1
   • 原始树比新树有更多的内部节点（因为我们将红色节点合并到继承黑色父节点）。因此，n >= 2^h' -1

6. 剩下的就是代数：

   • n+1 >= 2^h'（取两边的对数）
   • lg(n+1) >= h' （我们从上面的步骤 4 中知道 h' >= h/2）

最后我们得到

• 2lg(n+1) >= h。

这样就完成了证明。