算法导论-ch14 augmenting data structures

《算法导论-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)，即子树大小。0ifxnil[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树的基本结构；②在红黑