red-black-tree - 红黑树高证明

Question

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

标签： red-black-tree

Answer 1

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

最简单的情况是一棵根本没有红色节点的树，对于这样的树来说，它是一个有效的红黑树，它的底层必须被完全填充。（请注意，在示例中我没有显示叶节点）。

举个例子：

  2b
 / \
1b  3b

它的高度为 2，即 floor(log_2(3+1))。

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

  2b
 / \
1r  3b

然而下面也是一个有效的红黑树，高度仍然是 2（注意 1 2 和 3 的颜色都可以翻转，形成一排完全填充的内部黑色节点）（ floor(log_2(5+1 ))==2):

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