北京大学：《数据结构与算法》课程教学资源（实验班讲义）第十章 索引技术（内存索引——红黑树）

张铭红黑树 2007年12月25日2时19分 引子:索引的效率问题 数据结构与算法 内存索引一红黑树百 ◆索引( indexing):把一个关键码与它对应 的数据记录的位置相关联 ■(关键码,指针)对,即(key, pointer) 北京大学信息科学技术学院 三类索引 线性索引:有序数组、索引顺序文件 张铭 树型索引:二叉搜索树(BsT、B/B+树 http://db.pku.ecu.cn/mzhang/ds/ 散列索引 红黑机之歌 2007年12月2日2时19分 北京大学张铭心红黑树 2007年12月25日2时19分 北京大学张铭心红黑树 BsT的平衡问题 ◆输入94267151221 ◆输入246791215,21 ◆希望保持理想状况 ◆插入、删除、查找时间代价为o(ogm) 红树之歌 2007年12月25日】时 北京大学张铭红里树 2007年12月25日2时19分 北京大学张心红黑树 The Red-Black Tree Song The Red-Black Tree Song ◆ I see a brand new node ◆ I see a brand new node ● I want to paint it black OI want to paint it black. O We need a balanced tree, O Can't have a lot of red nodes Owe' ve got to paint it black. oWe must paint them black. oi want to find my key in log n time o Unfortunately coding them can be a O Rotating sub-trees round sure can be a oIf we had half a brain to splay trees we ould switch 00?年12月25日2时 北京大学张铭红里树 2007年12月25日2时19分 北京大学张铭红黑树

张铭 红黑树 2007年12月25日2时19分 1 2007年12月25日2时19分 北京大学 张铭© 红黑树 1 数据结构与算法 内存索引——红黑树 6 3 8 4 北京大学信息科学技术学院 张铭 http://db.pku.ecu.cn/mzhang/DS/ 2007年12月25日2时19分 北京大学 张铭© 红黑树 2 引子：索引的效率问题 索引( indexing )：把一个关键码与它对应 的数据记录的位置相关联 „ (关键码，指针)对，即(key, pointer) 三类索引 „ 线性索引：有序数组、索引顺序文件 „ 树型索引：二叉搜索树(BST)、 B/B+树 字符树…… „ 散列索引 红黑树之歌 2007年12月25日2时19分 北京大学 张铭© 红黑树 3 BST的平衡问题 输入9,4,2,6,7,15,12,21 输入2,4, 6,7, 9, 12,15, 21 9 4 15 2 6 12 7 21 9 15 4 6 2 12 7 21 2007年12月25日2时19分 北京大学 张铭© 红黑树 4 希望保持理想状况 插入、删除、查找时间代价为O(logn ) 红黑树之歌 2007年12月25日2时19分 北京大学 张铭© 红黑树 5 The Red-Black Tree Song I see a brand new node I want to paint it black. We need a balanced tree, we've got to paint it black. I want to find my key in log n time -- thats all, Rotating sub-trees 'round sure can be a ball. 2007年12月25日2时19分 北京大学 张铭© 红黑树 6 The Red-Black Tree Song I see a brand new node I want to paint it black. Can't have a lot of red nodes, We must paint them black. Unfortunately, coding them can be a bitch. If we had half a brain to splay trees we would switch

张铭红黑树 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=(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 = (h-1) / 2 由性质（3）得n >= 2k – 1 „ 即 n >= 2 (h-1)/2 – 1 可得出 h <= 2 log2 (n+1)+1

张铭红黑树 2007年12月25日2时19分 插入算法 插入算法调整1:重构 ◆先调用BST的插入算法 ◆情况1:新增结点X的叔父结点是黑色 把新记录着色为红色 若父结点是展色,则算法结束 以祖结点为轴 旋转父结点 A ◆否则,双红调整 插入4 ◆每个结点的阶都保持原值,调整完成 2007年12月2日2时19分 北京大学张铭心红黑树 2007年12月25日2时19分 北京大学张铭心红黑树 4种形式的结构调整 插入算法调整2:换色 ◆原则:保持BST的中序性质 ◆情况2:新增结点X的叔父结点也是红色 只A 红红检查 Q⊙父祖换色 ◆需要继续检查平衡 2007年12月25日】时 北京大学张铭红里树 2007年12月25日2时19分 北京大学张心红黑树 插入4 插入4 ◆情况2红红冲突 ◆情况2红红冲突 父和叔父也是红 父和叔父也是红 ◆父祖换色 ◆父祖换色 00?年12月25日2时 北京大学张铭红里树 2007年12月25日2时19分 北京大学张铭红黑树

张铭 红黑树 2007年12月25日2时19分 3 2007年12月25日2时19分 北京大学 张铭© 红黑树 13 插入算法 先调用BST的插入算法 „ 把新记录着色为红色 „ 若父结点是黑色，则算法结束 否则，双红调整 6 3 8 6 3 8 4 X A A X 插入4 2007年12月25日2时19分 北京大学 张铭© 红黑树 14 插入算法调整1：重构 情况1：新增结点X的叔父结点是黑色 每个结点的阶都保持原值，调整完成 X α 以祖结点为轴 旋转父结点 A X B B A C C α 2007年12月25日2时19分 北京大学 张铭© 红黑树 15 4种形式的结构调整 原则：保持BST的中序性质 2 4 6 6 2 4 6 4 2 2 6 4 2 6 4 2007年12月25日2时19分 北京大学 张铭© 红黑树 16 插入算法调整2：换色 情况2：新增结点X的叔父结点也是红色 需要继续检查平衡 X A 父祖换色 X B B C A C 对B继续 红红检查 α α 2007年12月25日2时19分 北京大学 张铭© 红黑树 17 插入4 情况2红红冲突 „ 父和叔父也是红 父祖换色 11 2 14 1 7 15 5 8 X 4 2007年12月25日2时19分 北京大学 张铭© 红黑树 18 插入4 情况2红红冲突 „ 父和叔父也是红 父祖换色 11 2 14 1 7 15 5 8 X 4 5 7 8

张铭红黑树 2007年12月25日2时19分 插入4 插入4 ◆情况2红红冲突 ◆情况2红红冲突 父和叔父也是红 父和叔父也是红 ◆父祖换色 ◆父祖换色 ◆情况1红红冲突 ◆情况1红红冲突Q 叔父是黑 叔父是黑 ◆重构 ◆重构 2007年12月2日2时19分 北京大学张铭心红黑树 2007年12月25日2时19分 北京大学张铭心红黑树 插入算法和复杂度分析 删除算法 inserter(毳a ◆红晨树高度为O(ogn) 先调用BST的删除算法 B摘入,銅入新结点.0)●第1步时闸代价为gn) 特删除的结点有一个以上的外部空指汁,则宣接删除 ◆第2步时间代价为O(1) ◆v是被剽除的内结点,w是被删外结点X是v的兄弟 2把z标记为红色 ●第3步时间代价为Oogn 否则I标记为双根据其兄弟鳍点c进行工构调整 最多O1次工构着色 删除8 dst●红票结点插入时间代价 为O(ogn) 2007年12月25日】时 北京大学张铭红里树 2007年12月25日2时19分 北京大学张心红黑树 根据双黑X的兄弟C进行调整 情况1(a)重构:侄子红结点八字 假设X是左子结点〔若X为右孩子,则对称) ◆将兄弟结点C提上去 ●情况1:c是黑色,且子结点有红色 ◆c继承原父结点的颜色 盒构,完成操作 ◆然后把B着为黑色,D着为黑色,其他颜色不变即可 ◆情况2:C是色,且有两个黑子结点 换色 父结点B原为红色,可能需要从B继续向上调整 ●情况3:c是红色 c转为父结点,调整为情况1或2继续处理 00?年12月25日2时 北京大学张铭红里树 2007年12月25日2时19分 北京大学张铭红黑树

张铭 红黑树 2007年12月25日2时19分 4 2007年12月25日2时19分 北京大学 张铭© 红黑树 19 插入4 情况2红红冲突 „ 父和叔父也是红 父祖换色 情况1红红冲突 „ 叔父是黑 重构 11 2 14 1 7 15 5 8 4 X 5 7 2007年12月25日2时19分 北京大学 张铭© 红黑树 20 插入4 情况2红红冲突 „ 父和叔父也是红 父祖换色 情况1红红冲突 „ 叔父是黑 重构 7 2 11 1 5 8 4 5 14 15 2007年12月25日2时19分 北京大学 张铭© 红黑树 21 插入算法和复杂度分析 红黑树高度为 O(log n) 第1步时间代价为 O(log n) „ 因为访问 O(log n) 个结点 第2步时间代价为O(1) 第3步时间代价为 O(log n) „ 最多 O(log n) 重着色 Š 每次 O(1) „ 最多 O(1) 次 重构着色 红黑树结点插入时间代价 为 O(log n) insertItem(k, o) 1. BST插入，插入新结点 z(k, o) 2. 把 z 标记为红色 3. while doubleRed(z) if isBlack(sibling(parent(z))) z ← restructure(z) return else { sibling(parent(z) is red } z ← recolor(z) 2007年12月25日2时19分 北京大学 张铭© 红黑树 22 删除算法 先调用BST的删除算法 „ 待删除的结点有一个以上的外部空指针，则直接删除 „ 否则在右子树中找到其后继结点进行值交换（着色不变）删除 v 是被删除的内结点, w 是被删外结点, X 是 w的兄弟 „ 如果 v 或者 X 是红色, 则把 X 标记为黑色即可 „ 否则, X 需要标记为双黑, 根据其兄弟结点 C 进行重构调整 6 3 8 4 v X w 6 3 4 删除 X 8 2007年12月25日2时19分 北京大学 张铭© 红黑树 23 根据双黑 X 的兄弟 C 进行调整 假设X是左子结点（若X为右孩子，则对称） 情况1： C 是黑色，且子结点有红色 „ 重构，完成操作 情况2：C 是黑色, 且有两个黑子结点 „ 换色 „ 父结点B原为红色，可能需要从B继续向上调整 情况3： C 是红色 „ 转换状态 „ C转为父结点，调整为情况1或2继续处理 2007年12月25日2时19分 北京大学 张铭© 红黑树 24 情况1(a)重构：侄子红结点八字 将兄弟结点C提上去 C继承原父结点的颜色 然后把B着为黑色，D着为黑色，其他颜色不变即可 B D X C α D X B C α

张铭红黑树 2007年12月25日2时19分 情况1b重构:侄子红结点同边顺 情况2:兄弟是黑色,且有两个黑子结点 ●将D结点旋转为C结点的父结点,D继承原子根 B的颜色,B着为黑色 ◆把C着红色,B着黑色 ◆如果B原为红色,则算法结束 ◆否则,对B继续作双黑“调整 Ra 有可能量端 双处覆 2007年12月2日2时19分 北京大学张铭心红黑树 2007年12月25日2时19分 北京大学张铭心红黑树 情况3:兄弟C是红色 删除90 ●旋转 ◆当前结点变为80的右黑叶结点 ●X结点仍是双黑“”结点,转化为前面2种情况 ◆C是黑色,且有两个黑色子结点:情况2 b 2007年12月25日】时 北京大学张铭红里树 2007年12月25日2时19分 北京大学张心红黑树 删除90 删除70 ◆当前结点变为80的右黑叶结点 ◆红结点,不要调整 ◆c是黑色且有两个黑色子结点:情况2换色 X 00?年12月25日2时 北京大学张铭红里树 2007年12月25日2时19分 北京大学张铭红黑树 5

张铭 红黑树 2007年12月25日2时19分 5 2007年12月25日2时19分 北京大学 张铭© 红黑树 25 情况1(b)重构：侄子红结点同边顺 将D结点旋转为C结点的父结点，D继承原子根 B的颜色，B着为黑色 B X E C D α β B C D X α E β 2007年12月25日2时19分 北京大学 张铭© 红黑树 26 情况2：兄弟是黑色, 且有两个黑子结点 把C着红色，B着黑色 如果B原为红色，则算法结束 否则，对B继续作“双黑”调整 B X D E C B C D E X 有可能继续 双黑处理 2007年12月25日2时19分 北京大学 张铭© 红黑树 27 情况3：兄弟C 是红色 旋转 X结点仍是“双黑”结点，转化为前面2种情况 B X C α β X B C α β 2007年12月25日2时19分 北京大学 张铭© 红黑树 28 删除90 当前结点变为80的右黑叶结点 C 是黑色, 且有两个黑色子结点：情况2 65 50 10 60 62 80 70 90 B B X C E D E C D X C X B 2007年12月25日2时19分 北京大学 张铭© 红黑树 29 删除90 当前结点变为80的右黑叶结点 C 是黑色, 且有两个黑色子结点：情况2换色 65 50 10 60 62 80 70 B B X C E D E C D X C X 70 B 2007年12月25日2时19分 北京大学 张铭© 红黑树 30 删除70 红结点，不要调整 65 50 10 60 62 80 70

张铭红黑树 2007年12月25日2时19分 删除80 删除80(调整) ◆当前结点X变为65的右黑叶结点 ◆c是黑色,且左黑、右红:情况1(b)重构 ◆C是红色:情况3状态转换 2007年12月2日2时19分 北京大学张铭心红黑树 2007年12月25日2时19分 北京大学张铭心红黑树 删除80 删除操作时间代价 ◆完成调整 ◆其平均和最差检索o(log2m) 自底向根的方向调整 ◆红黑树构造 (数据,左指针,右指针,颜色,父指 ◆自顶向下的递归插入/删除调整方法 (数据,左指针,右指针,颜色 ■非递归,记录回溯路径 2007年12月25日】时 北京大学张铭心红黑树 2007年12月25日2时19分 北京大学张心红黑树 其他BST索引 红黑树是一种很好的索引结构 ◆AvL树 ◆AVL树要求完全平衡 平衡的BsT 左右子树高度整≤1 ◆伸展树与操作频率相关 ●伸展树 ◆RB-Tree局部平衡 随检宗面训數位量 ■统计性能好于AvL树 人△ ■且增删记录算法性能好、易实现 C++ST的set、 multiset、map multimap都应用了红黑树的变体 00?年12月25日2时 京大学张铭红更树 2007年12月25日2时19分 北京大学张铭红黑树 6

张铭 红黑树 2007年12月25日2时19分 6 2007年12月25日2时19分 北京大学 张铭© 红黑树 31 删除80 当前结点X变为65的右黑叶结点 C 是红色：情况3状态转换 65 50 10 60 62 80 X B B C X C α β α β C X B 2007年12月25日2时19分 北京大学 张铭© 红黑树 32 删除80（调整） C 是黑色，且左黑、右红：情况1(b)重构 50 10 60 62 65 X C E D B B X E C D α β B C D X α E β 2007年12月25日2时19分 北京大学 张铭© 红黑树 33 删除80 完成调整 50 10 62 D 60 65 C B X 2007年12月25日2时19分 北京大学 张铭© 红黑树 34 删除操作时间代价 其平均和最差检索O(log2 n) „ 自底向根的方向调整 红黑树构造 （数据，左指针，右指针，颜色，父指 针） 自顶向下的递归插入/删除调整方法 „ （数据，左指针，右指针，颜色） „ 非递归，记录回溯路径 2007年12月25日2时19分 北京大学 张铭© 红黑树 35 其他BST索引 AVL树 „ 平衡的BST „ 左右子树高度差≤1 伸展树 „ 随检索而调整位置 A B C D x y z B C A D x y z 9 1 1 8 3 12 10 15 11 -1 0 0 0 -1 2007年12月25日2时19分 北京大学 张铭© 红黑树 36 红黑树是一种很好的索引结构 AVL树要求完全平衡 伸展树与操作频率相关 RB-Tree局部平衡 „ 统计性能好于AVL树 „ 且增删记录算法性能好、易实现 C++ STL的set、multiset、map、 multimap都应用了红黑树的变体

张铭红黑树 2007年12月25日2时19分 总结 谢谢! ◆红黑树高度平衡 ◆结点插入算法 树重构 ■换色、调整 北京大学信息学院 ◆结点删除算法 张铭 ■树重构 ■重着色 zhang@db.pku.edu.cn 转换状态 2007年12月2日2时19分 北京大学张铭心红黑树 2007年12月25日2时19分 北京大学张铭心红黑树

张铭 红黑树 2007年12月25日2时19分 7 2007年12月25日2时19分 北京大学 张铭© 红黑树 37 总结 红黑树高度平衡 结点插入算法 „ 树重构 „ 换色、调整 结点删除算法 „ 树重构 „ 重着色 „ 转换状态 2007年12月25日2时19分 北京大学 张铭© 红黑树 38 谢谢！ 北京大学信息学院 张铭 mzhang@db.pku.edu.cn