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

数据结构与算法 内存索引—红黑树 匕京大学信息科学技术学院 张铭 http://db.pku.ecu.cn/mzhang/ds/ 2007年12月25日2时19分 北京大学张铭⊙红黑树

2007年12月25日2时19分 北京大学 张铭© 红黑树 1 数据结构与算法 内存索引——红黑树 6 3 8 4 北京大学信息科学技术学院 张铭 http://db.pku.ecu.cn/mzhang/DS/

引子:索引的效率问题 ◆索引( indexing):把一个关键码与它对应 的数据记录的位置相关联 (关键码,指针)对,即(key, pointer) ◆三类索引 线性索引:有序数组、索引顺序文件 树型索引:二叉搜索树(BST)、B/B+树 字符树 ■■■■■■ 散列索引 红黑树之歌 2007年12月25日2时19分 北京大学张铭⊙红黑树

2007年12月25日2时19分 北京大学 张铭© 红黑树 2 引子：索引的效率问题 索引( indexing )：把一个关键码与它对应 的数据记录的位置相关联 „ (关键码，指针)对，即(key, pointer) 三类索引 „ 线性索引：有序数组、索引顺序文件 „ 树型索引：二叉搜索树(BST)、 B/B+树 字符树…… „ 散列索引 红黑树之歌

BST的平衡问题 ◆输入94267151221 ◆输入2467,9,121521 2007年12月25日2时19分 北京大学张铭⊙红黑树

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

◆希望保持理想状况 ◆插入、删除、查找时间代价为o(logn) 红黑树之歌 2007年12月25日2时19分 北京大学张铭⊙红黑树

2007年12月25日2时19分 北京大学 张铭© 红黑树 4 希望保持理想状况 插入、删除、查找时间代价为O(logn ) 红黑树之歌

The Red-Black Tree Song ◆ I see a brand new node BI want to paint it black. o We need a balanced tree, o we' ve got to paint it black. oI want to find my key in log n time thats all o Rotating sub-trees round sure can be a ball 2007年12月25日2时19分 北京大学张铭⊙红黑树

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

The Red-Black Tree Song ◆ I see a brand new node BI want to paint it black. o Cant have a lot of red nodes o We must paint them black. UNfortunately, coding them can be a bitch p If we had half a brain to splay trees we would switch 2007年12月25日2时19分 北京大学张铭⊙红黑树

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

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 o And if they 're still confusing, you should have no fear. o 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分 北京大学张铭⊙红黑树

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

内容提要 ◆红黑树定义 red- black tree简称RB-tree ◆红黑树高度 ◆结点插入算法 ◆结点删除算法 红黑树之歌 2007年12月25日2时19分 北京大学张铭⊙红黑树 8

2007年12月25日2时19分 北京大学 张铭© 红黑树 8 内容提要 红黑树定义 „ red-black tree, 简称RB-tree 红黑树高度 结点插入算法 结点删除算法 红黑树之歌

红黑树:平衡的扩充二叉搜索树 ◆颜色特征:结点是红色或黑色 ◆根特征:根结点永远是黑色”的; 2bI u at ◆外部特征:扩充外部叶结点都是空的黑色“结点 ◆内部特征:"红色"结点的两个子结点都是黑色”的 不允许两个连续的红色结点 ◆深度特征:任何绩点到其子孙外部结点的每条简单路径都包含相 同数目的黑色结点 2007年12月25日2时19分 北京大学张铭⊙红黑树

2007年12月25日2时19分 北京大学 张铭© 红黑树 9 红黑树：平衡的扩充二叉搜索树 颜色特征：结点是“红色” 或“黑色” ； 根特征：根结点永远是“黑色”的； 外部特征：扩充外部叶结点都是空的“黑色”结点； 内部特征： “红色”结点的两个子结点都是“黑色”的 „ 不允许两个连续的红色结点 深度特征：任何结点到其子孙外部结点的每条简单路径都包含相 同数目的“黑色”结点 9 4 15 2 6 12 7 21 “红色” “黑色” 扩充

红黑树的阶 ◆结点X的阶(rank,也称N黑色高度") 从该结点到外部结点的黑色结点数量 不包括X结点本身,包括叶结点 ◆外部结点的阶是零 ◆根的阶称为该树的阶 rank=2 rank=2 rank= 1 2007年12月25日2时19分 北京大学张铭⊙红黑树

2007年12月25日2时19分 北京大学 张铭© 红黑树 10 红黑树的阶 结点X的阶（rank，也称“黑色高度”） „ 从该结点到外部结点的黑色结点数量 „ 不包括X结点本身，包括叶结点 外部结点的阶是零 根的阶称为该树的阶 9 4 15 2 6 12 7 21 rank=2 rank=1 rank=2