北大数据结构与算法课件10B内存索引——红黑树

2007年12月25日2时19分北京大学张铭©红黑树1数据结构与算法内存索引——红黑树6384信息科学技术学院2007年12月25日2时19分北京大学张铭©红黑树2引子：索引的效率问题索引(indexing)：把一个关键码与它对应的数据记录的位置相关联„(关键码，指针)对，即(key,pointer)三类索引„线性索引：有序数组、索引顺序文件„树型索引：二叉搜索树(BST)、B/B+树字符树……„散列索引红黑树之歌2007年12月25日2时19分北京大学张铭©红黑树3BST的平衡问题输入9,4,2,6,7,15,12,21输入2,4,6,7,9,12,15,2191546212721915462127212007年12月25日2时19分北京大学张铭©红黑树4希望保持理想状况插入、删除、查找时间代价为O(logn)红黑树之歌2007年12月25日2时19分北京大学张铭©红黑树5TheRed-BlackTreeSongIseeabrandnewnodeIwanttopaintitblack.Weneedabalancedtree,we'vegottopaintitblack.Iwanttofindmykeyinlogntime--thatsall,Rotatingsub-trees'roundsurecanbeaball.2007年12月25日2时19分北京大学张铭©红黑树6TheRed-BlackTreeSongIseeabrandnewnodeIwanttopaintitblack.Can'thavealotofrednodes,Wemustpaintthemblack.Unfortunately,codingthemcanbeabitch.Ifwehadhalfabraintosplaytreeswewouldswitch.2007年12月25日2时19分北京大学张铭©红黑树7TheRed-BlackTreeSongIseeabrandnewnodeIwanttopaintitblack.NotimeforAVLtreeswemustpaintitBLACK.Andifthey'restillconfusing,youshouldhavenofear.Becauseoutsidethisclass,ofthemyou'llneverhear.Iwannapaint'emBLACK.Paintnodesblack.Againandagain.2007年12月25日2时19分北京大学张铭©红黑树8内容提要红黑树定义„red-blacktree,简称RB-tree红黑树高度结点插入算法结点删除算法红黑树之歌2007年12月25日2时19分北京大学张铭©红黑树9红黑树：平衡的扩充二叉搜索树颜色特征：结点是“红色”或“黑色”；根特征：根结点永远是“黑色”的；外部特征：扩充外部叶结点都是空的“黑色”结点；内部特征：“红色”结点的两个子结点都是“黑色”的„不允许两个连续的红色结点深度特征：任何结点到其子孙外部结点的每条简单路径都包含相同数目的“黑色”结点91546212721“红色”“黑色”扩充2007年12月25日2时19分北京大学张铭©红黑树10红黑树的阶结点X的阶（rank，也称“黑色高度”）„从该结点到外部结点的黑色结点数量„不包括X结点本身，包括叶结点外部结点的阶是零根的阶称为该树的阶91546212721rank=2rank=1rank=22007年12月25日2时19分北京大学张铭©红黑树11红黑树的性质(1)红黑树是满二叉树„空叶结点也看作结点(2)阶为k的红黑树路径长度„从根到叶的简单路径长度„即树高(3)阶为k的红黑树的内部结点„最少是一棵完全满二叉树„内部结点数最少是2k-1915462127最短是k最小是k+1，最长是2k，最高是2k+16922007年12月25日2时19分北京大学张铭©红黑树12红黑树的性质(4)n个内部结点的红黑树树高最大是2log2(n+1)+1证明：设红黑树的阶为k，设红黑树的树高是h。由性质（2）得h=2k+1„则k=(h-1)/2由性质（3）得n=2k–1„即n=2(h-1)/2–1可得出h=2log2(n+1)+12007年12月25日2时19分北京大学张铭©红黑树13插入算法先调用BST的插入算法„把新记录着色为红色„若父结点是黑色，则算法结束否则，双红调整6386384XAAX插入42007年12月25日2时19分北京大学张铭©红黑树14插入算法调整1：重构情况1：新增结点X的叔父结点是黑色每个结点的阶都保持原值，调整完成Xα以祖结点为轴旋转父结点AXBBACCα2007年12月25日2时19分北京大学张铭©红黑树154种形式的结构调整原则：保持BST的中序性质2466246422642642007年12月25日2时19分北京大学张铭©红黑树16插入算法调整2：换色情况2：新增结点X的叔父结点也是红色需要继续检查平衡X父祖换色AXBBACC对B继续红红检查αα2007年12月25日2时19分北京大学张铭©红黑树17插入4情况2红红冲突„父和叔父也是红父祖换色112141157854X2007年12月25日2时19分北京大学张铭©红黑树18插入4情况2红红冲突„父和叔父也是红父祖换色112141157854X5782007年12月25日2时19分北京大学张铭©红黑树19插入4情况2红红冲突„父和叔父也是红父祖换色情况1红红冲突„叔父是黑重构112141157854X572007年12月25日2时19分北京大学张铭©红黑树20插入4情况2红红冲突„父和叔父也是红父祖换色情况1红红冲突„叔父是黑重构72111854514152007年12月25日2时19分北京大学张铭©红黑树21插入算法和复杂度分析红黑树高度为O(logn)第1步时间代价为O(logn)„因为访问O(logn)个结点第2步时间代价为O(1)第3步时间代价为O(logn)„最多O(logn)重着色Š每次O(1)„最多O(1)次重构着色红黑树结点插入时间代价为O(logn)insertItem(k,o)1.BST插入，插入新结点z(k,o)2.把z标记为红色3.whiledoubleRed(z)ifisBlack(sibling(parent(z)))z←restructure(z)returnelse{sibling(parent(z)isred}z←recolor(z)2007年12月25日2时19分北京大学张铭©红黑树22删除算法先调用BST的删除算法„待删除的结点有一个以上的外部空指针，则直接删除„否则在右子树中找到其后继结点进行值交换（着色不变）删除v是被删除的内结点,w是被删外结点,X是w的兄弟„如果v或者X是红色,则把X标记为黑色即可„否则,X需要标记为双黑,根据其兄弟结点C进行重构调整6384vXw634X删除82007年12月25日2时19分北京大学张铭©红黑树23根据双黑X的兄弟C进行调整假设X是左子结点（若X为右孩子，则对称）情况1：C是黑色，且子结点有红色„重构，完成操作情况2：C是黑色,且有两个黑子结点„换色„父结点B原为红色，可能需要从B继续向上调整情况3：C是红色„转换状态„C转为父结点，调整为情况1或2继续处理2007年12月25日2时19分北京大学张铭©红黑树24情况1(a)重构：侄子红结点八字将兄弟结点C提上去C继承原父结点的颜色然后把B着为黑色，D着为黑色，其他颜色不变即可BDXCαDXBCα2007年12月25日2时19分北京大学张铭©红黑树25情况1(b)重构：侄子红结点同边顺将D结点旋转为C结点的父结点，D继承原子根B的颜色，B着为黑色BXECDβαCBDXαEβ2007年12月25日2时19分北京大学张铭©红黑树26情况2：兄弟是黑色,且有两个黑子结点把C着红色，B着黑色如果B原为红色，则算法结束否则，对B继续作“双黑”调整BXEDCBCEDX有可能继续双黑处理2007年12月25日2时19分北京大学张铭©红黑树27情况3：兄弟C是红色旋转X结点仍是“双黑”结点，转化为前面2种情况BCXβαXBCαβ2007年12月25日2时19分北京大学张铭©红黑树28删除90当前结点变为80的右黑叶结点C是黑色,且有两个黑色子结点：情况26550106062809070BBCXEEDCDXXCB2007年12月25日2时19分北京大学张铭©红黑树29删除90当前结点变为80的右黑叶结点C是黑色,且有两个黑色子结点：情况2换色65501060628070BBCXEEDCDXXC70B2007年12月25日2时19分北京大学张铭©红黑树30删除70红结点，不要调整655010606280702007年12月25日2时19分北京大学张铭©红黑树31删除80当前结点X变为65的右黑叶结点C是红色：情况3状态转换655010606280XBBCCXβααβXCB2007年12月25日2时19分北京大学张铭©红黑树32删除80（调整）C是黑色，且左黑、右红：情况1(b)重构5010606265XCDEBBXECDβαCBDXαEβ2007年12月25日2时19分北京大学张铭©红黑树33删除80完成调整501062D6560BCX2007年12月25日2时19分北京大学张铭©红黑树34删除操作时间代价其平均和最差检索O(log2n)„自底向根的方向调整红黑树构造（数据，左指针，右指针，颜色，父指针）自顶向下的递归插入/删除调整方法„（数据，左指针，右指针，颜色）„非递归，记录回溯路径2007年12月25日2时19分北京大学张铭©红黑树35其他BST索引AVL树„平衡的BST„左右子树高度差≤1伸展树„随检索而调整位置BCADxyzBCADxyz9118312101511-1000-12007年12月25日2时19分北京大学张铭©红黑树36红黑树是一种很好的索引结构AVL树要求完全平衡伸展树与操作频率相关RB-Tree局部平衡„统计性能好于AVL树„且增删记录算法性能好、易实现C++STL的set、multiset、map、multimap都应用了红黑树的变体2007年12月25日2时19分北京大学张铭©红黑树37总结红黑树高度平衡结点插入算法„树重构„换色、调整结点删除算法„树重构„重着色„转换状态