第14章_數(shù)據(jù)結構的擴張_算法分析與設計_杭電_褚一平

1、數(shù)據(jù)結構的擴張 許多應用要求在現(xiàn)在數(shù)據(jù)結構有所創(chuàng)新,很少需要創(chuàng)造出全新的數(shù)據(jù)結構大綱數(shù)據(jù)結構的擴張 應用 總結 順序統(tǒng)計樹 區(qū)間樹數(shù)據(jù)結構的擴張數(shù)據(jù)結構擴張 為什么提出數(shù)據(jù)結構擴張 數(shù)據(jù)結構如何擴張數(shù)據(jù)結構的擴張 在標準數(shù)據(jù)結構中增加信息比如：AVL、雙鏈表215105502-110-1150(n+1)/2lgn251015 nil51015 nil2nil數(shù)據(jù)結構的擴張數(shù)據(jù)結構擴張為什么提出數(shù)據(jù)結構擴張 數(shù)據(jù)結構如何擴張數(shù)據(jù)結構的擴張 為什么提出數(shù)據(jù)結構擴張？ 優(yōu)化查找 BST，最壞情況下，查找長度為(n+1)/2, 最好情況下，logn AVL，查找最好最壞都是O(lgn)數(shù)據(jù)結構的擴張數(shù)

2、據(jù)結構擴張為什么提出數(shù)據(jù)結構擴張數(shù)據(jù)結構如何擴張數(shù)據(jù)結構如何擴張選擇基礎數(shù)據(jù)結構10315181620附加信息驗證11612013615210318基本操作停止 YN數(shù)據(jù)結構如何擴張 要求：要求：在不影響RB-Tree上插入和刪除的漸近時間的前提下對size域進行維護。 插入： 第一階段：在RB-Tree中插入結點11 第二階段:對RB-Tree進行調整156102183161201size15+;size10+;111183157第一階段維第一階段維護護size域的域的時間復雜度時間復雜度為為O(lgn)第二階段維第二階段維護護size域的域的時間復雜度時間復雜度為為O(1)31310310

3、3數(shù)據(jù)結構如何擴張 左旋轉：42196931274xy子子樹樹的的sizexy左旋47931942116插入調整過程最多進行插入調整過程最多進行兩次旋轉，時間復雜度兩次旋轉，時間復雜度為為O(1),及插入過程維護及插入過程維護size域的時間復雜度為域的時間復雜度為O(lgn)sizey=sizexsizex=sizeleftx+sizerightx+1數(shù)據(jù)結構如何擴張 右旋轉：42196931274yx子子樹樹的的sizexy右旋47931942116插入調整過程最多進行插入調整過程最多進行兩次旋轉，時間復雜度兩次旋轉，時間復雜度為為O(1),及插入過程維護及插入過程維護size域的時間復雜

4、度為域的時間復雜度為O(lgn)sizey=sizexsizex=sizeleftx+sizerightx+1數(shù)據(jù)結構如何讓擴張 刪除 第一階段，對查找樹進行操作，O(lgn)； 第二階段，對RB-Tree進行調整，至多做三次旋轉，O(1)；對一棵含n個結點的順序統(tǒng)計樹，插入操作和刪除操作，包括維護size域，都需要O(lgn)時間。數(shù)據(jù)結構如何擴張 刪除： 第一階段，對查找樹進行操作 第二階段：對RB-Tree進行調整11612013615210318刪除：20size -；O(lgn)515218218116O(1)插入和刪除： O(lgn)對一棵含n個結點的順序統(tǒng)計樹，插入操作和刪除操作

5、，包括維護size域，都需要O(lgn)時間。大綱數(shù)據(jù)結構的擴張應用 總結 順序統(tǒng)計樹 區(qū)間樹順序統(tǒng)計樹順序統(tǒng)計樹提出的原因 順序統(tǒng)計樹的介紹 如何利用順序統(tǒng)計樹解決問題 舉例Josephus排列求逆序對MIN-GAP順序統(tǒng)計 順序統(tǒng)計量： 例如 數(shù)組 在上述的無序數(shù)組中:第1個順序統(tǒng)計量 第9個順序統(tǒng)計量 在無序的集合中查找任意順序統(tǒng)計量為O(n)528719913 4O(lgn)順序統(tǒng)計 若在動態(tài)集合查找任意元素x在有序的線性序中的位置i。 例如：3 5 8 9 4 6 7 2 1 查找任意元素的位置i時間復雜度為：O(N)O(lgn)順序統(tǒng)計樹順序統(tǒng)計樹提出的原因順序統(tǒng)計樹 如何利用順序

6、統(tǒng)計樹解決問題 舉例Josephus排列求逆序對MIN-GAP順序統(tǒng)計樹 支持快速順序統(tǒng)計量操作的紅黑樹15610218331161201key域size域20151631810順序統(tǒng)計樹基礎數(shù)據(jù)結構：RB-Tree，包括的域為： keyx、colorx、px、leftx、rightx附加的域為:sizex:包含以結點x為根的子樹的內部結點數(shù)，包括x本身，即子樹的大小。sizex=sizeleftx+sizerightx+1;設計新的操作：SELECT(rootx,i),RANK(T,x);15610218331161201key域size域順序統(tǒng)計樹是支持快速順序統(tǒng)計量的操作的數(shù)據(jù)結構.順序

7、統(tǒng)計樹順序統(tǒng)計樹提出的原因順序統(tǒng)計樹的介紹如何利用順序統(tǒng)計樹解決問題 舉例Josephus排列求逆序對MIN-GAP順序統(tǒng)計樹-操作 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)順序統(tǒng)計樹-操作 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)數(shù)組的為數(shù)組的為O(n)順序統(tǒng)計樹順序統(tǒng)計樹提出的原因順序統(tǒng)計樹的介紹如何利用順序統(tǒng)計樹解決問題舉例Josephus排列求逆序對MIN-GAP順序統(tǒng)計樹應用-Josephus排列 問題：12436 5 7 n=7，m=n,m=3m是常數(shù)是常數(shù)36 2 7 5 14順序統(tǒng)計樹應用-Josephus排列 問題：1635427m=3 3輸出序列：6 2 7 5 1 4 順序統(tǒng)計樹應用-Josephus排列 方法一：1

9、2 3 4 5 6 7 12435763625147時間復雜度為時間復雜度為:O(N)n=7,m=3m是常數(shù)是常數(shù)順序統(tǒng)計樹應用-Josephus排列 方法二：若m不是常數(shù)初始化：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順序統(tǒng)計樹應用-Josephus排列64514211266225m=5,start=(5+5-1

10、)%5=3,SELECT(T,4);輸出序列輸出序列：3754311254362614224順序統(tǒng)計樹順序統(tǒng)計樹提出的原因順序統(tǒng)計樹的介紹如何利用順序統(tǒng)計樹解決問題舉例Josephus排列求逆序對MIN-GAP順序統(tǒng)計樹應用-求逆序對 逆序對：例如：無序數(shù)組: 9212620106: 12: 310: 2for (i = 0 ;i N ;i +)for(j = i + 1; j aj)count +;傳統(tǒng)方法傳統(tǒng)方法：時間復雜度為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、數(shù)組中某個數(shù)字si的逆序數(shù)是指出現(xiàn)在si之前，但是比si大的數(shù)字的個數(shù)。 根據(jù)順序統(tǒng)計量的Rank(T,x)，每插入到一個元素x后，可以求得在已經(jīng)出現(xiàn)的元素中，比x小的數(shù)字的個數(shù)。 /Rank(T, z)表示s0.i中min-gap;時間復雜度:O(lgn)大綱數(shù)據(jù)結構的擴張 應用 總結 順序統(tǒng)計樹 區(qū)間樹區(qū)間樹區(qū)間樹的定義 區(qū)間三分法 區(qū)間樹的查找操作 舉例區(qū)間樹 將RB-Tree擴張為由區(qū)間構成的數(shù)據(jù)結構。16,213016,218,95,819,2017,1926,2625,306,10優(yōu)點:查找特定區(qū)間內發(fā)生什么事情8,91025,30305,8106,101017,192026,26

12、2619,2020max域maxx=max(highint x,maxleftx,maxrightx)25,3030區(qū)間樹 區(qū)間樹與線段樹的對比：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 區(qū)間樹區(qū)間樹的定義區(qū)間三分法 區(qū)間樹的查找操作 舉例區(qū)間三分法 區(qū)間 i 和 i之間的關系： 重疊 i 在 i左邊 i 在 i右邊條件：條件：low i =high i ,且且 low i

13、=high i 條件：條件：high i high i 區(qū)間樹區(qū)間樹的定義區(qū)間三分法 區(qū)間樹的查找操作 舉例區(qū)間樹的INTERVAL-SEARCH(T,i)操作 操作說明：用來找出樹T中覆蓋區(qū)間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)；區(qū)間樹的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)區(qū)間樹區(qū)間樹的定義區(qū)間三分法區(qū)間樹的查找操作 舉例舉例 1.最大重疊點 亦即覆蓋它的區(qū)間最多的那個點。 最大重疊點總存在于某段的端點上。013