张铭红黑树 2007年12月25日2时19分 The Red-Black Tree Song 内容提要 ● I see a brand new node ◆红黑树定义 e i want to paint it black. ared- black tree,简称RB-tree O No time for AVL trees ● we must paint it BLACK ◆红黑树高度 ◆结点插入算法 O And if they re still confusing, you should have ◆结点删除算法 e Because outside this class, of them you' ll never o I wanna paint 'em BLACK. Paint nodes black. 红黑机之歌 2007年12月25日2时19分 京大学张铭红黑树 2007年12月25日2时19分 北京大学张铭心红黑树 红黑树:平衡的扩充二叉搜索树 红黑树的阶 ◆颜色特征:螬点是红色或色 ◆结点X的阶(rank,也称"黑色高度") 从该结点到外部结点的票色结点数量 红色“结点的两个子结点郁是黑色的 不包括X结点本身,包括叶结点 ◆簣衙暂包糖 到其子孙外部蜻点的气条简单路径都包含相 ◆外部结点的阶是零 ◆根的阶称为该树的阶 o rank=2 rank=1 2007年12月25日】时 北京大学张铭红里树 2007年12月25日2时19分 北京大学张⑥红 红黑树的性质 红黑树的性质 ◆(4)n个内部结点的红晨树树高 ●(1)红黑树是满二叉树 最大是2log2(n+1)+1 空叶结点也看作结点 (2)阶为k的红暴树路径长度 从根到叶的简单路径长度最短是k,最长是2k ◆设红黑树的阶为k,设红屏树的树高是h。 即树高最小是k+1,最高是2k+1 ◆由性质(2)得h<=2k+1 (3)阶为k的红黑树的内部结点 则k>=(h-1)/2 ◆由性质(3)得n>=2-1 最少是一棵完全满二叉树 内部结点数最少是2k-1 可得出h<=2log2(n+1)+1 00?年12月25日2时 北京大学张铭红里树 2007年12月25日2时19分 北京大学张铭红黑树张铭 红黑树 2007年12月25日2时19分 2 2007年12月25日2时19分 北京大学 张铭© 红黑树 7 The Red-Black Tree Song I see a brand new node I want to paint it black. No time for AVL trees we must paint it BLACK. And if they're still confusing, you should have no fear. Because outside this class, of them you'll never hear. I wanna paint 'em BLACK. Paint nodes black. Again and again. 2007年12月25日2时19分 北京大学 张铭© 红黑树 8 内容提要 红黑树定义 „ red-black tree, 简称RB-tree 红黑树高度 结点插入算法 结点删除算法 红黑树之歌 2007年12月25日2时19分 北京大学 张铭© 红黑树 9 红黑树：平衡的扩充二叉搜索树 颜色特征：结点是“红色” 或“黑色” ； 根特征：根结点永远是“黑色”的； 外部特征：扩充外部叶结点都是空的“黑色”结点； 内部特征： “红色”结点的两个子结点都是“黑色”的 „ 不允许两个连续的红色结点 深度特征：任何结点到其子孙外部结点的每条简单路径都包含相 同数目的“黑色”结点 9 4 15 2 6 12 7 21 “红色” “黑色” 扩充 2007年12月25日2时19分 北京大学 张铭© 红黑树 10 红黑树的阶 结点X的阶（rank，也称“黑色高度”） „ 从该结点到外部结点的黑色结点数量 „ 不包括X结点本身，包括叶结点 外部结点的阶是零 根的阶称为该树的阶 9 4 15 2 6 12 7 21 rank=2 rank=1 rank=2 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 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