《算法设计与分析动态顺序统计.ppt》由会员分享，可在线阅读，更多相关《算法设计与分析动态顺序统计.ppt（37页珍藏版）》请在三一文库上搜索。
1、算法设计与分析,谭守标 安徽大学 电子学院 2007.9,第十章 动态顺序统计和区间树,扩张数据结构的概念 动态顺序统计（过程及分析） 数据结构 选择操作 确定元素的秩 维护操作 扩张数据结构概念的一般步骤 红黑树扩张定理介绍及证明 区间树概念及扩张步骤（过程及分析） 程序演示及说明,一、扩张数据结构的概念,向标准的数据结构中增加一些信息 附加的信息能为该数据数据结构上普通的操作所更新和维护,二、动态顺序统计,数据结构 选择操作 确定元素的秩 维护操作,数据结构,定义：sizeNIL为0 则有等式：sizex=sizeleftx+sizerightx+1,选择操作(检索具有给定秩的元素),元素
2、的秩它在集合的线性序中的位置 调用过程OS-SELECT(rootT,i),找出顺序统计树T中的第i小关键字,以x为根的子树中x的秩为sizeleftx+1 i=r,第i小元素为x； ir,第i小元素在x的右子树中， x的右子树前共有r个元素，故所求即为以rightx为根的子树中第(i-r)小元素 例：i=17 OS-SELECT的运行时间为O(lg n),确定元素的秩,y从x节点开始循环往上遍历： y是个左孩子，r保持不动 y是个右孩子，r将加上sizeleftpy+1 y=rootT时， r就是keyx的秩,例：确定关键字为38的节点的秩 keyy和r的一系列值如下：,OS-RANK的运行
3、时间为O(lg n),维护操作,红-黑树上的插入操作包括两个阶段： 第一阶段由根开始沿树下降，将新节点插入为某个已有节点的孩子 对由根至叶子的路径上遍历的每个节点x的 sizex增加1;新增加的节点的size为1 维护size域的额外代价为O(lg n),第二阶段沿树上升，做一些颜色修改和旋转以保持红黑性质 旋转会改变红-黑树的结构，次数至多为2， 仅影响旋转操作的支撑链两头节点的size域 在14.2节中我们给出LEFT-ROTATE(T,x)， 现增加如下代码：,对RIGHT-ROTATE所做的改动是对称的,红-黑树上的删除操作同样包括两个阶段： 第一阶段对查找树进行操作，删除节点y， 可
4、遍历一条由节点y至根的路径，并减小路径 上每个节点的size域，所需额外时间为O(lg n) 第二阶段作至多三次的旋转，可如插入时同 样的方式来处理 对一棵含n个节点的顺序统计树，插入操作加上删除操作，再加上维护size域，总共需O(lg n)时间,三、扩张数据结构的一般步骤,对一个数据结构的扩张可分为四个步骤： 1 选择基础数据结构 2 确定要在基础数据结构中记录的附加 信息 3 验证可用基础数据结构上的基本修改 操作来维护附加信息 4 设计新的操作,顺序统计树扩张步骤分析,上一节设计顺序统计树时，就依照了这些步骤。 步骤 1中，我们选择了红-黑树作为基础数据结构。之所以选择这种数据结构，是
5、因为它能有效地支持一些动态集合操作，如MINMUM, MAXIMUM, SUCCESSOR和PREDECESSOR等。 步骤2中，我们提供了size域，它可以存放各节点的子树规模的信息。一般地，附加信息可使得各类操作更加有效。例如，我们本可以仅用树中存储的关键字来实现OS-SELECT和OS-RANK，但这种实现的运行就不止是O(lgn)了。有些时候，附加信息是指针类信息，而不是具体的数据。,顺序统计树扩张步骤分析,步骤3中，我们保证了插入和删除操作仍能在O(lgn)时间内维护size域。比较理想的是对原有数据结构略作改动就足以维护附加的信息。例如，如果我们把每一个节点秩存在树中，则OS-SE
6、LECT和OS-RANK过程能较快地运行，但要插入一个新的最小元素则会使树中每个节点的秩发生变化。如果我们存储的是子树的规模，则插入一个新元素的操作仅影响到O(lgn)个节点。 步骤4中，我们设计了操作OS-SELECT和OS-RANK。对新操作的需要是我们对数据结构进行扩张的首要动因。有时，我们并不设计新的操作，而是利用附加的信息来加速已有操作的执行速度。,红黑树扩张定理,设域f对含n 个节点的红-黑进行了扩张，且假设某节点x的域f的内容可以仅用节点x，leftx，和rightx中的信息（包括fleftx与frightx）来计算。这样，在插入和删除操作中我们可以不影响这两个操作O(lgn)渐
7、进性能的情况下对T的所有节点的f值进行维护。,红黑树扩张定理证明,证明的主要思想是对树中某节点x的f域的改动仅会波及树中x的祖先，而不会波及到其他节点。 将一个节点x插入T的过程包括两个阶段： 在第一阶段中，x被插入为一个现存节点Px的孩子。fx的值可在O(1)时间内计算出。根据假设，fx被求出后，这个变化就沿树向上传播。这样，插入的第一阶段的总时间为O(lgn)。 在第二阶段中，对树结构的仅有变化来源于旋转操作。在一次旋转中只有两个节点发生变化。故每次旋转中更新f 域的总时间为O(lgn)。又因为插入操作中旋转次数至多为，故插入的总时间为O(lgn)。,红黑树扩张定理证明,和插入一样，删除操
8、作也包括两个阶段。 在第一阶段中，如果被删除的节点由其后继替代，则树发生变化。这些变化波及到f的代价至多为O(lgn)，因为这些变化对树的影响只是局部的。 第二阶段对红-黑树的修改复至多需要三次旋转，且每次旋转至多需要O(lgn)时间就可以将变化传播到f。这样，删除的总时间为O(lgn)。,四、区间树概念及扩张步骤,引言: 我们把一个区间t1,t2表示成一个对象i，其各个域为lowi=t1(低端点)，highi=t2(高端点)。我们说区间i和i重叠，如果ii ，亦即，如果lowihighi,且lowihighi。任意两个区间i和i满足区间三分法，亦即，下列三种情况中只有一种成立： i和i重叠。
9、 highilowi. highilowi.,下图给出这三种情况： (a)如果i和I重叠，则共有四种情况；每种情况都满足lowihighi及lowihighi。 (b)highilowi。 (c)highilowi。,区间树概念,区间树是对一动态集合进行维护的红-黑树，该集合中的每一个元素x都包含一个区间intx.区间树支持下列操作： INTERVAL-INSERT(T,x):将包含区间域int的元素x插入到区间树T中。 INTERVAL-DELETE(T,x):从区间树T中删除元素x。 INTERVAL-SEARCH(T,i):返回一个指向区间树T中元素x的指针，使intx与i重叠；或集合中
10、无此元素存在时返回NIL。,下图说明了区间树是如何表示一个区间集合的。(a) 十个区间按左端点自底向上顺序示出。(b) 表示它们的区间树。对该树做中序遍历即可按左端点顺序列出各个节点。我们可以按照上节中的四步模式来进行区间树以及区间树上的操作的设计过程。,区间树的扩张步骤,步骤1 基础数据结构 我们选择的基础数据为这样一种红-黑树，其中每个节点x包含一个区间域intx，x的关键字为区间的低端点lowintx。这样，对树进行中序遍历可按低端点的次序列出各区间。,区间树的扩张步骤,步骤2 附加信息 每个节点x 中除了区间信息外，还包含一个值maxx。即以x为根的子树中所有区间的端点的最大值。因为任
11、一区间的高端点至少和其低端点一样大，故maxx是以x为根的子树中所有区间的右端点中的最大值。,区间树的扩张步骤,步骤3 对信息的维护 要验证对含n个节点的区间树的插入和删除能在O(lgn)时间内完成。给定区间intx和x的子节点的max值，我们可以确定maxx: maxx=maxhighintx,maxleftx,maxrightx) 这样，根据红黑树扩张定理可知，插入和删除操作的运行时间为O(lgn)。事实上在一次旋转后更新max域只需O(1)时间。,区间树的扩张步骤,步骤4 设计新的操作 我们唯一需要的新操作是INTERVAL-SERARCH(T,i)，它用来找出树T中与区间i重叠的那个区
12、间。如果这样的区间不存在，则返回NIL. 1 INTERVAL-SEARCH(T,i) 2 XrootT 3 While xNIL and i 没有与intx重叠 4 Do if leftxNIL and maxleftxlowi 5 then xleftx 6 else xrightx 7 return x,区间树搜索算法过程举例,查找与i=22,25交迭的区间 查找与i=11,14交迭的区间,区间树搜索算法性能分析,查找与i交迭的区间x的过程先以x为根开始，逐步下降。当找到一个重迭区域或返回NIL时该过程结束。因为基本循环的每次迭代要花O(1)时间。又含n个节点的红-黑树的高度为O(lgn
13、)，故INTERVAL-SEARCH过程的时间为O(lgn)。,区间树搜索算法正确性,为什么只检查一条由根开始的路径就足够了 ？ 如果有，沿这条路径是否肯定能找到？ 如果没找到，是否别的路径上也没有？,区间树搜索算法正确性,定理15.2： 在INTERVAL-SEARCH(T,i)的每次while循环中： （1）如果执行了第4行(查找向左转)，则x的左子树中包含与i重叠的区间(或者说x的右子树中没有一个区间与i重叠)。 （2）如果执行了第5行(查找向右转)，则x的左子树中不包含与i重叠的区间。,区间树搜索算法正确性,情况二,情况一,区间三分法,区间三分法,程序演示及说明,(程序演示及说明),作业,思考题15-1：最大重叠点,The End,Thank you!,