红黑树高度的上限：一个非常满意的结果 ·Let Tbe a red-bh height of Tin the usual sense is at most 21g(n+1) 当x为T的根时， ·引理：以x 邰结点 ·对x日 高度 不是黑高！ ·奠基：x的高度为 ·假设x的高度小于k时结论成立 17 ·归纳：有两个子女高度等于k的内部节点x,k>0 230 47 2(10 119 128 NIL NIL ·子女的黑高至少是bh(x)-1 1(15m120 NIL NILNIL NID 1(35)1(39 m AI N10 NIL NR ·子树至少有2(bh(x)-1)1个内点 NINI (a) ·内部节点数=两个子树内部节点数以及x自身之和红黑树高度的上限：一个非常满意的结果 • Let T be a red-black tree with n internal nodes，the height of T in the usual sense is at most 2lg(n+1). • 引理：以x为根的红黑树子树至少包含2 bh(x) -1个内部结点 • 对x的高度进行归纳 • 奠基：x的高度为0时：x是Nil，正确 • 假设x的高度小于k时结论成立 • 归纳：有两个子女高度等于k的内部节点x，k>0 • 子女的黑高至少是bh(x)-1 • 子树至少有2^(bh(x)-1)-1个内点 • 内部节点数=两个子树内部节点数以及x自身之和 当x为T的根时， 情况如何？ 不是黑高！