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