红黑树高度证明

Question

我正在阅读这本算法书，在红黑树部分，它陈述了以下引理：具有 n 个内部节点的红黑树的高度最多为 2 lg(n + 1 )..然后它进入了证明的数学部分，我迷路了。谁能给我一个不那么复杂的证明？我在网上查了一下，但似乎没有找到什么好的网站或视频。

Answer 1

这来自定义红黑树的属性，即所有节点都是红色或黑色，红色节点有两个黑色子节点，并且从任何叶节点到根的路径将遍历相同数量的节点黑色节点。

最简单的情况是一棵根本没有红色节点的树，要使这样的树成为有效的红黑树，其底层必须完全填充。 （注意示例中我没有显示叶节点）。

举个例子：

  2b
 / \
1b  3b

它的高度为 2，即地板（log_2（3+1））。

另一种安排根本不是有效的红黑树：

  2b
 / \
1r  3b

不过下面也是一棵有效的红黑树，高度还是2（注意1、2、3的颜色都可以翻转，形成一排完全填满的内部黑色节点）（floor( log_2(5+1))==2):

      4b
    /  \
  2r      5b
  /\
1b  3b