资源描述：
《彩色PDF讲义(10-1)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、6数据结构与算法38内存索引——红黑树4北京大学信息科学技术学院张铭http://db.pku.ecu.cn/mzhang/DS/2007年12月25日2时19分北京大学张铭©红黑树1引子：索引的效率问题索引(indexing)：把一个关键码与它对应的数据记录的位置相关联¢(关键码，指针)对，即(key,pointer)三类索引¢线性索引：有序数组、索引顺序文件+¢树型索引：二叉搜索树(BST)、B/B树字符树……¢散列索引红黑树之歌2007年12月25日2时19分北京大学张铭©红黑树2BST的平衡问题输
2、入9,4,2,6,7,15,12,21输入2,4,6,7,9,12,15,21249641526122179712152007年12月25日2时19分北京大学张铭©红黑树321希望保持理想状况插入、删除、查找时间代价为O(logn)红黑树之歌2007年12月25日2时19分北京大学张铭©红黑树4TheRed-BlackTreeSongIseeabrandnewnodeIwanttopaintitblack.Weneedabalancedtree,we'vegottopaintitblack.Iwantto
3、findmykeyinlogntime--thatsall,Rotatingsub-trees'roundsurecanbeaball.2007年12月25日2时19分北京大学张铭©红黑树5TheRed-BlackTreeSongIseeabrandnewnodeIwanttopaintitblack.Can'thavealotofrednodes,Wemustpaintthemblack.Unfortunately,codingthemcanbeabitch.Ifwehadhalfabraintospl
4、aytreeswewouldswitch.2007年12月25日2时19分北京大学张铭©红黑树6TheRed-BlackTreeSongIseeabrandnewnodeIwanttopaintitblack.NotimeforAVLtreeswemustpaintitBLACK.Andifthey'restillconfusing,youshouldhavenofear.Becauseoutsidethisclass,ofthemyou'llneverhear.Iwannapaint'emBLACK.P
5、aintnodesblack.Againandagain.2007年12月25日2时19分北京大学张铭©红黑树7内容提要红黑树定义¢red-blacktree,简称RB-tree红黑树高度结点插入算法结点删除算法红黑树之歌2007年12月25日2时19分北京大学张铭©红黑树8红黑树：平衡的扩充二叉搜索树扩充颜色特征：结点是“红色”或““黑色黑色””；根特征：根结点永远是“黑色”的；外部特征：扩充外部叶结点都是空的“黑色”结点；内部特征：“红色”结点的两个子结点都是“黑色”的¢不允许两个连续的红色结点深度特
6、征：任何结点到其子孙外部结点的每条简单路径都包含相同数目的“黑色”结点941526122172007年12月25日2时19分北京大学张铭©红黑树9红黑树的阶结点X的阶（rank，也称“黑色高度”）¢从该结点到外部结点的黑色结点数量¢不包括X结点本身，包括叶结点外部结点的阶是零根的阶称为该树的阶9rank=2rank=2415rank=126122172007年12月25日2时19分北京大学张铭©红黑树109红黑树的性质41526127(1)红黑树是满二叉树¢空叶结点也看作结点(2)阶为k的红黑树路径长度¢
7、从根到叶的简单路径长度最短是k，最长是2k¢即树高最小是k+1，最高是2k+1(3)阶为k的红黑树的内部结点6¢最少是一棵完全满二叉树¢内部结点数最少是2k-1292007年12月25日2时19分北京大学张铭©红黑树11红黑树的性质(4)n个内部结点的红黑树树高最大是2log(n+1)+12证明：设红黑树的阶为k，设红黑树的树高是h。由性质（2）得h<=2k+1¢则k>=(h-1)/2由性质（3）得n>=2k–1(h-1)/2¢即n>=2–1可得出h<=2log(n+1)+122007年12月25日2时1
8、9分北京大学张铭©红黑树12插入算法先调用BST的插入算法¢把新记录着色为红色¢若父结点是黑色，则算法结束否则，双红调整66AA插入43838XX42007年12月25日2时19分北京大学张铭©红黑树13插入算法调整1：重构情况1：新增结点X的叔父结点是黑色以祖结点为轴BA旋转父结点ACXBXCαα每个结点的阶都保持原值，调整完成2007年12月25日2时19分北京大学张铭©红黑树144种形式的结构调整原则：保持BST的中序性
