欢迎来到天天文库
浏览记录
ID:33737250
大小:664.36 KB
页数:24页
时间:2019-02-28
《算法导论-ch14 augmenting data structures》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、算法设计与分析DesignandAnalysisofAlgorithms主讲人徐云FallFall2012,2012,USTCUSTCPart1FoundationPart2SortingandOrderStatisticsPart3DataStructurechap10chap10ElementaryDataStructuresElementaryDataStructureschap11HashTableschap12BinarySearchTreeschap13Redchap13Red--BlackTreesBlac
2、kTreeschap14chap14AugmentingDataStructuresAugmentingDataStructuresPart4AdvancedDesignandAnalysisTechniquesPart5AdvancedDataStructuresPart6GraphAlgorithmsPart7SelectedTopicsPart8Supplement第14章章数据结构的扩张数据结构的扩张14.1动态顺序统计14.2如何扩充一个数据结构14.3区间树14.1动态顺序统计OS树的定义选择问题及算法
3、求算求秩问题及算法OS树的维护:插入OS树的维护:删除2012/10/31算法设计与分析4OS树的定义(1)Def:OS(Order-Statistic)树是一棵红黑树在每个节点上扩充一个域size[x]而得到的,它是以x为根的子树中内部节点的总数(包括x),即子树大小。0ifxnil[T]size[x]size[left[x]]size[right[x]]1other节点结构:keysize2012/10/31算法设计与分析5OS树的定义(2)OS树的一个图例:Fig.14.12012/10/3
4、1算法设计与分析6选择问题及算法选择问题:在以x为根的子树中,查找第i个最小元素。算法:OSSelect(x,i){(1):r←size[left[x]]+1;(2):①若i=r,则返回x;②若i<r,则递归地在x的左子树中继续找第i个元素;③若i>r,则递归地在x的右子树中继续找第i-r个元素;}时间:O(logn)2012/10/31算法设计与分析7求秩问题及算法求秩问题:在OS树中,给定元素x求其rank。算法:step1:在以x为根的子树中,x的秩:r←size[left[x]]+1;step2:①若x是
5、根,则返回r;②若x是双亲的左子,则x在以p[x]为根的子树中的秩是r;③若x是双亲的右子,则x在以p[x]为根的子树中的秩是r←r+seze[left[p[x]]]+1;④x上移至p[x];重复②,③,④直至①成立时终止;时间:O(logn)2012/10/31算法设计与分析8OS树的维护:插入(1)插入算法Phase1:从根向下插入新节点,将搜索路径上所经历的每个节点的size+1,新节点的size置为1;-附加成本:O(logn)Phase2:采用变色和旋转方法,从叶子向上调整;-变色不改变size;-旋转可
6、能改变size:∵旋转是局部操作,又,只有轴上的两个节点的size可能违反定义∴只需要在旋转操作后,对违反节点size进行修改-附加成本:旋转为O(1),总成本为O(logn),2012/10/31算法设计与分析9OS树的维护:插入(2)例:LeftRotate(T,x)xy93421919右旋yyx9342611712左旋x4647左旋x后:size[y]←size[x]size[x]←size[left[x]]+size[right[x]]+1∵插入过程至多有2个旋转∴附加成本为O(1)2012/10/31算法设
7、计与分析10OS树的维护:删除删除算法Phase1:物理上删除y,在删除y时从y上溯至根,将所经历的节点的size均减1;-附加成本:O(logn)Phase2:采用变色和旋转方法,从叶子向上调整;-变色不改变size;-旋转可能改变size,至多有3个旋转;-附加成本:O(logn)Remark:上面介绍的插入和删除均是有效维护,有效维护保证扩充前后的基本操作的渐近时间不变。2012/10/31算法设计与分析11第14章章数据结构的扩张数据结构的扩张14.1动态顺序统计14.2如何扩充一个数据结构14.3区间树
8、14.2如何扩充一个数据结构扩充的目的扩充的步骤扩充红黑树的定理2012/10/31算法设计与分析13扩充的目的和步骤扩充的目的开发新的操作加速已有的操作扩充的步骤①选择基本结构;②确定附加信息:如,数据、指针;③维护附加信息和有效性;④开发新操作。例:OS树①选择红黑树作为OS树的基本结构;②在红黑
此文档下载收益归作者所有