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

Question

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

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

Answer 1

这个link给出了定理的直观证明。

下面我简单回顾一下证明的步骤:

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。

这样就完成了证明。