红黑树的性质 ◆(4)n个内部结点的红黑树树高 最大是2log2(n+1)+1 证明: ◆设红黑树的阶为k,设红黑树的树高是h。 ◆由性质(2)得h<=2k+1 则k>=(h-1)/2 ◆由性质(3)得n>=2k-1 即n>=2(h-1)/2 ◆可得出h<=2log2(n+1)+1 2007年12月25日2时19分 北京大学张铭⊙红黑树2007年12月25日2时19分 北京大学 张铭© 红黑树 12 红黑树的性质 (4) n个内部结点的红黑树树高 最大是2 log2 (n+1)+1 证明： 设红黑树的阶为k，设红黑树的树高是h。 由性质（2）得h <= 2k+1 „ 则 k >= (h-1) / 2 由性质（3）得n >= 2k – 1 „ 即 n >= 2 (h-1)/2 – 1 可得出 h <= 2 log2 (n+1)+1