第14章_数据结构的扩张_算法分析与设计_杭电_褚一平

1、数据结构的扩张 许多应用要求在现在数据结构有所创新,很少需要创造出全新的数据结构大纲数据结构的扩张 应用 总结 顺序统计树 区间树数据结构的扩张数据结构扩张 为什么提出数据结构扩张 数据结构如何扩张数据结构的扩张 在标准数据结构中增加信息比如：AVL、双链表215105502-110-1150(n+1)/2lgn251015 nil51015 nil2nil数据结构的扩张数据结构扩张为什么提出数据结构扩张 数据结构如何扩张数据结构的扩张 为什么提出数据结构扩张？ 优化查找 BST，最坏情况下，查找长度为(n+1)/2, 最好情况下，logn AVL，查找最好最坏都是O(lgn)数据结构的扩张数

2、据结构扩张为什么提出数据结构扩张数据结构如何扩张数据结构如何扩张选择基础数据结构10315181620附加信息验证11612013615210318基本操作停止 YN数据结构如何扩张 要求：要求：在不影响RB-Tree上插入和删除的渐近时间的前提下对size域进行维护。 插入： 第一阶段：在RB-Tree中插入结点11 第二阶段:对RB-Tree进行调整156102183161201size15+;size10+;111183157第一阶段维第一阶段维护护size域的域的时间复杂度时间复杂度为为O(lgn)第二阶段维第二阶段维护护size域的域的时间复杂度时间复杂度为为O(1)31310310

3、3数据结构如何扩张 左旋转：42196931274xy子子树树的的sizexy左旋47931942116插入调整过程最多进行插入调整过程最多进行两次旋转，时间复杂度两次旋转，时间复杂度为为O(1),及插入过程维护及插入过程维护size域的时间复杂度为域的时间复杂度为O(lgn)sizey=sizexsizex=sizeleftx+sizerightx+1数据结构如何扩张 右旋转：42196931274yx子子树树的的sizexy右旋47931942116插入调整过程最多进行插入调整过程最多进行两次旋转，时间复杂度两次旋转，时间复杂度为为O(1),及插入过程维护及插入过程维护size域的时间复杂

4、度为域的时间复杂度为O(lgn)sizey=sizexsizex=sizeleftx+sizerightx+1数据结构如何让扩张 删除 第一阶段，对查找树进行操作，O(lgn)； 第二阶段，对RB-Tree进行调整，至多做三次旋转，O(1)；对一棵含n个结点的顺序统计树，插入操作和删除操作，包括维护size域，都需要O(lgn)时间。数据结构如何扩张 删除： 第一阶段，对查找树进行操作 第二阶段：对RB-Tree进行调整11612013615210318删除：20size -；O(lgn)515218218116O(1)插入和删除： O(lgn)对一棵含n个结点的顺序统计树，插入操作和删除操作

5、，包括维护size域，都需要O(lgn)时间。大纲数据结构的扩张应用 总结 顺序统计树 区间树顺序统计树顺序统计树提出的原因 顺序统计树的介绍 如何利用顺序统计树解决问题 举例Josephus排列求逆序对MIN-GAP顺序统计 顺序统计量： 例如 数组 在上述的无序数组中:第1个顺序统计量 第9个顺序统计量 在无序的集合中查找任意顺序统计量为O(n)528719913 4O(lgn)顺序统计 若在动态集合查找任意元素x在有序的线性序中的位置i。 例如：3 5 8 9 4 6 7 2 1 查找任意元素的位置i时间复杂度为：O(N)O(lgn)顺序统计树顺序统计树提出的原因顺序统计树 如何利用顺序

6、统计树解决问题 举例Josephus排列求逆序对MIN-GAP顺序统计树 支持快速顺序统计量操作的红黑树15610218331161201key域size域20151631810顺序统计树基础数据结构：RB-Tree，包括的域为： keyx、colorx、px、leftx、rightx附加的域为:sizex:包含以结点x为根的子树的内部结点数，包括x本身，即子树的大小。sizex=sizeleftx+sizerightx+1;设计新的操作：SELECT(rootx,i),RANK(T,x);15610218331161201key域size域顺序统计树是支持快速顺序统计量的操作的数据结构.顺序

7、统计树顺序统计树提出的原因顺序统计树的介绍如何利用顺序统计树解决问题 举例Josephus排列求逆序对MIN-GAP顺序统计树-操作 SELECT(rootx,i):返回指向x为根的子树中包含第i小关键字的指针；15610218331161201例如：例如：SELECT(15,4)r=sizeleft15+1 =2+1=31r=4-r=4-3=1SELECT(16,1)r=sizeleft16+1 =0+1=1=1,return 16时间复杂时间复杂度为：度为：O(lgn)顺序统计树-操作 RANK(T,x)，返回对T进行中序遍历后的线性序中x的位置。例如：例如：RANK(26,38)r=si

8、zeleft38+1 =1+1=2r=r+sizeleft30+1 =2+1+1=4r不变，不变，r=4r=r+sizeleft26+1 =4+10+1=15r38=15，O(lgn)数组的为数组的为O(n)顺序统计树顺序统计树提出的原因顺序统计树的介绍如何利用顺序统计树解决问题举例Josephus排列求逆序对MIN-GAP顺序统计树应用-Josephus排列 问题：12436 5 7 n=7，m=n,m=3m是常数是常数36 2 7 5 14顺序统计树应用-Josephus排列 问题：1635427m=3 3输出序列：6 2 7 5 1 4 顺序统计树应用-Josephus排列 方法一：1

9、2 3 4 5 6 7 12435763625147时间复杂度为时间复杂度为:O(N)n=7,m=3m是常数是常数顺序统计树应用-Josephus排列 方法二：若m不是常数初始化：start=0,t=n；31271145637151271163457151start=(start+m-1)%tSELECT(T,start+1);m=3,start=(0+3-1)%7=2,SELECT(T,3);6426输出序列输出序列：3m=4,start=(2+4-1)%6=5,SELECT(T,6);74442顺序统计树应用-Josephus排列64514211266225m=5,start=(5+5-1

10、)%5=3,SELECT(T,4);输出序列输出序列：3754311254362614224顺序统计树顺序统计树提出的原因顺序统计树的介绍如何利用顺序统计树解决问题举例Josephus排列求逆序对MIN-GAP顺序统计树应用-求逆序对 逆序对：例如：无序数组: 9212620106: 12: 310: 2for (i = 0 ;i N ;i +)for(j = i + 1; j aj)count +;传统方法传统方法：时间复杂度为O(N2)9比6大, 所以1个9,6, 12都比2大, 3个12,别20 比10 大, 2个SUM: 1+3+2=6 SUM=SUM+ i +1-RANK(T,x)

11、数组中某个数字si的逆序数是指出现在si之前，但是比si大的数字的个数。 根据顺序统计量的Rank(T,x)，每插入到一个元素x后，可以求得在已经出现的元素中，比x小的数字的个数。 /Rank(T, z)表示s0.i中min-gap;时间复杂度:O(lgn)大纲数据结构的扩张 应用 总结 顺序统计树 区间树区间树区间树的定义 区间三分法 区间树的查找操作 举例区间树 将RB-Tree扩张为由区间构成的数据结构。16,213016,218,95,819,2017,1926,2625,306,10优点:查找特定区间内发生什么事情8,91025,30305,8106,101017,192026,26

12、2619,2020max域maxx=max(highint x,maxleftx,maxrightx)25,3030区间树 区间树与线段树的对比：16,213026,26268,9105,8106,101017,192019,202025,30301,10 1,5 6,10 1,3 4,5 6,8 9,10 1,2 3,3 4,4 5,5 6,7 8,8 9,9 10,10 1,1 2,2 6,6 7,7 区间树区间树的定义区间三分法 区间树的查找操作 举例区间三分法 区间 i 和 i之间的关系： 重叠 i 在 i左边 i 在 i右边条件：条件：low i =high i ,且且 low i

13、=high i 条件：条件：high i high i 区间树区间树的定义区间三分法 区间树的查找操作 举例区间树的INTERVAL-SEARCH(T,i)操作 操作说明：用来找出树T中覆盖区间i的那个结点16,21308,92325,30305,81015,232317,192026,262619,20206,10100,33SEARCH(16，22,25)overlap( int x ,interval i) if(low x high i ) return 0； if(high x low i ) return 0; else return 1; return 15;时间复杂度为时间复杂

14、度为O(lgn)；区间树的INTERVAL-SEARCH(T,i)操作 SEARCH(16，11,14)16,21308,92325,30305,81015,232317,192026,262619,20206,10100,33overlap( int x ,interval i) if(low x high i ) return 0； if(high x low i ) return 0; else return 1; return null;时间复杂度为时间复杂度为:O(lgn)区间树区间树的定义区间三分法区间树的查找操作 举例举例 1.最大重叠点 亦即覆盖它的区间最多的那个点。 最大重叠点总存在于某段的端点上。013