数据结构与算法 内存索引—红黑树 匕京大学信息科学技术学院 张铭 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