算法导论-ch13 red-black trees

《算法导论-ch13 red-black trees》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计与分析DesignandAnalysisofAlgorithms主讲人徐云FallFall20122012,,USTCUSTCPart1FoundationPart2SortingandOrderStatisticsPart3DataStructurechap10chap10ElementaryDataStructuresElementaryDataStructureschap11HashTableschap12BinarySearchTreeschap13chap13RedRed--BlackTreesBlac

2、kTreeschap14AugmentingDataStructuresPart4AdvancedDesignandAnalysisTechniquesPart5AdvancedDataStructuresPart6GraphAlgorithmsPart7SelectedTopicsPart8Supplement第13章章红黑树红黑树13.1红黑树的性质13.2旋转13.3插入1313413.4删除13.1红黑树的性质背景知识红黑树的定义一个图例黑高的定义关于高度的一个引理2012/10/31算法设计与分析4背

3、景知识（1）树的高度决定了树上操作的成本，一些搜索树的高度如下：平衡二叉搜索树：O(logn)1962年提出的AVL树：≤144logn1.44logn1972年提出的红黑树：≤2log(n+1)4阶B树:#key(1(13)#~3),#subtree(2(24)~4)红黑树//转化3keys:αββγγTTTT1234T1T2T3T4B树边RB树边2012/10/31算法设计与分析5背景知识（2）2keys:αβorTT31T1T2T3T2T3T1T21key:B树边αRB树边T1T2TT122012/10

4、/31算法设计与分析6红黑树的定义Def.1:红黑树是满足下述性质的二叉搜索树①每个节点必须为红色或黑色；//性质1②根为黑色；//性质2③树中的nil叶子为黑；//性质3④若节点为红，则其两个孩子必为黑；//性质4⑤每节点到其后代叶子的所有路径含有同样多的黑节点；//性质5节点的结构ParentleftColorKeyright2012/10/31算法设计与分析7一个图例Fig13.1(a)表达方式：图(a)每个空指针域均连接到一个叶节点nil，比较浪费存储空间；图(b)所有空指针域共享一个哨兵nil[T]，ni

5、l[T]为黑色；图()(c)省略nil[T];2012/10/31算法设计与分析8黑高的定义Def.2：节点x的黑高bh(x)是该节点到它的任何后代叶子路径上的黑节点数(不包括x本身)注：Fig13.1(a)中节点旁的数字Def.3：红黑树的黑高是根的黑高，记bh(root[T])2012/10/31算法设计与分析9关于高度的一个引理（1）Lemma13.1：一棵n个内点的红黑树的高度至多是2log(n+1)。Proof：①先证对任何以x为根的子树其内节点数≥2bh(x)-1归纳基础：当bh(x)=0时，x就是n

6、il[T]∴2bh(x)-1=20-1=0即为0个内节点，正确归纳假设：对x的左右孩子命题正确归纳证明：∵x的左右孩子的黑高或为bh(x)或为bh(x)-1∴x的内点数=左孩子内点数+右孩子内点数+1≥(2bh(()x)-1-1)+(2bh(()x)-1-1)+1=2bh(x)-1即第①点得证。2012/10/31算法设计与分析10关于高度的一个引理（2）Proof(Cont.)：②证明bh(root[T])≥h/2，h为红黑树的树高∵红点的孩子必为黑//红黑树的性质4∴红点的层数＜h/2因此bh(root[T])≥

7、h/2③证明最后结论∵红黑树有n个内点由①n≥2bh(root[T])-1≥2h/2-1∴h≤2log(n+1)□2012/10/31算法设计与分析11第13章章红黑树红黑树13.1红黑树的性质13.2旋转13.3插入1313413.4删除13.2旋转左、右旋转定义左旋实现的步骤左旋算法2012/10/31算法设计与分析13左、右旋的定义左、右旋转的图示yxRightRotate(Ty)RightRotate(T,y)xγαyLeftRotate(T,x)αββγ注：旋转过程中二叉搜索树(BST)性质不变：α

8、≤x≤β≤y≤γ2012/10/31算法设计与分析14左旋实现的步骤左旋图示：xx③yLeftRotate(T,x)④y①αyyxγ②βγαβ步骤解释：需要变动的是3根粗链临界情形①y←rigg[]ht[x]//记录指向y节点的指针②right[x]←left[y],p[left[y]]←x//β连到x右β=ni