红黑树的性质 ◆(1)红黑树是满二叉树 空叶结点也看作结点 ◆(2)阶为k的红黑树路径长度 从根到叶的简单路径长度最短是k,最长是2k 即树高最小是k+1,最高是2k+1 ◆(3)阶为k的红黑树的内部结点 最少是一棵完全满二叉树 Q 内部结点数最少是2k-1 2007年12月25日2时19分 北京大学张铭⊙红黑树
2007年12月25日2时19分 北京大学 张铭© 红黑树 11 红黑树的性质 (1) 红黑树是满二叉树 空叶结点也看作结点 (2) 阶为k的红黑树路径长度 从根到叶的简单路径长度 即树高 (3) 阶为k的红黑树的内部结点 最少是一棵完全满二叉树 内部结点数最少是2k-1 9 4 15 2 6 12 7 最短是k 最小是k+1 ，最长是2k ，最高是2k+1 6 2 9
红黑树的性质 ◆(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
插入算法 ◆先调用BST的插入算法 把新记录着色为红色 若父结点是黑色,则算法结束 ◆否则,双红调整 插入4 X 2007年12月25日2时19分 北京大学张铭⊙红黑树
2007年12月25日2时19分 北京大学 张铭© 红黑树 13 插入算法 先调用BST的插入算法 把新记录着色为红色 若父结点是黑色，则算法结束 否则，双红调整 6 3 8 6 3 8 4 X A A X 插入4