张铭红黑树 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