算法2013s擴(kuò)展數(shù)據(jù)結(jié)構(gòu)

算法設(shè)計與分析2024年1月22日講授內(nèi)容：擴(kuò)展數(shù)據(jù)結(jié)構(gòu)

教師：胡學(xué)鋼、吳共慶綱要動態(tài)順序統(tǒng)計方法區(qū)間樹1/22/2024算法設(shè)計與分析-擴(kuò)展數(shù)據(jù)結(jié)構(gòu)2OS-SELECT(i,S)

：返回動態(tài)集合S中第個i最小元素

。OS-RANK(x,S)

：返回

x∈S

在

S’的元素中的排序的位置IDEA:

使用紅黑樹存儲集合

S,同時在節(jié)點中保存子樹的大小。節(jié)點示意:Keysize動態(tài)順序統(tǒng)計1/22/2024算法設(shè)計與分析-擴(kuò)展數(shù)據(jù)結(jié)構(gòu)3一個

OS-樹的例子1/22/2024算法設(shè)計與分析-擴(kuò)展數(shù)據(jù)結(jié)構(gòu)4實現(xiàn)技巧:

使用

監(jiān)視哨(啞記錄)為

NIL

，令

size[NIL]=0.OS-SELECT(x,i)

?

ithsmallestelementinthesubtreerootedatx

k←size[left[x]]+1

?

k=rank(x)ifi=k

then

return

xifi<k

thenreturnOS-SELECT(left[x],i)elsereturnOS-SELECT(right[x],i–k)(OS-RANK請參考教材。)選擇1/22/2024算法設(shè)計與分析-擴(kuò)展數(shù)據(jù)結(jié)構(gòu)5OS-SELECT(root,5)對紅黑樹而言運行時間

=O(h)=O(lgn).例子1/22/2024算法設(shè)計與分析-擴(kuò)展數(shù)據(jù)結(jié)構(gòu)6Q.

為什么不在節(jié)點中直接保存它的級別，而是保存子樹的大??？當(dāng)紅黑樹被修改后很難維護(hù)。修改操作:

INSERT和

DELETE.策略:

當(dāng)插入和刪除的時候更新子樹的大小。數(shù)據(jù)結(jié)構(gòu)維護(hù)1/22/2024算法設(shè)計與分析-擴(kuò)展數(shù)據(jù)結(jié)構(gòu)7INSERT(“K〞)插入的例子1/22/2024算法設(shè)計與分析-擴(kuò)展數(shù)據(jù)結(jié)構(gòu)8不要忘記RB-INSERT和

RB-DELETE

操作為了維持平衡可能需要修改紅黑樹。?重著色:

對子樹大小沒有影響.?旋轉(zhuǎn):

可以在

O(1)

的時間內(nèi)修正子樹的大小.例子:∴RB-INSERT和

RB-DELETE的運行時間仍然是

O(lgn)

。處理重新平衡1/22/2024算法設(shè)計與分析-擴(kuò)展數(shù)據(jù)結(jié)構(gòu)9方法:

(e.g.,順序統(tǒng)計樹)1.

選擇底層數(shù)據(jù)結(jié)構(gòu)

(紅黑樹)。2.

確定在數(shù)據(jù)結(jié)構(gòu)中存儲的附加信息。

(子樹大小)。3.

驗證這個信息在修改操作中會被正確的維護(hù)

(RB-INSERT,RB-DELETE—不要忘記旋轉(zhuǎn)).4.

利用這些信息設(shè)計新的動態(tài)集合操作

(OS-SELECT和

OS-RANK)。這些步驟僅僅是指導(dǎo)，不是嚴(yán)格的公式。數(shù)據(jù)結(jié)構(gòu)擴(kuò)展1/22/2024算法設(shè)計與分析-擴(kuò)展數(shù)據(jù)結(jié)構(gòu)10目標(biāo):

維護(hù)一個區(qū)間的動態(tài)集合，

例如時間區(qū)間.查詢:

對于一個給定的查詢區(qū)間

i,在集合中找到一個區(qū)間與

i重疊。區(qū)間樹1/22/2024算法設(shè)計與分析-擴(kuò)展數(shù)據(jù)結(jié)構(gòu)111.選擇底層數(shù)據(jù)結(jié)構(gòu)。?使用紅黑樹，并且以低〔左〕端點為鍵。2.

決定在數(shù)據(jù)結(jié)構(gòu)中存儲的附加信息。?

在每個節(jié)點

x

中存儲以

x為根的子樹的最大值

m[x]和與鍵對應(yīng)的區(qū)間int[x]

。intm按照方法1/22/2024算法設(shè)計與分析-擴(kuò)展數(shù)據(jù)結(jié)構(gòu)12區(qū)間樹舉例1/22/2024算法設(shè)計與分析-擴(kuò)展數(shù)據(jù)結(jié)構(gòu)133.驗證這個信息可以在修改操作中得到維護(hù)。

?插入:Fixm’sonthewaydown.?旋轉(zhuǎn)

—Fixup=每個旋轉(zhuǎn)需要

O(1)

的時間:INSERT需要的時間和

=O(lgn);DELETE類似。修改操作1/22/2024算法設(shè)計與分析-擴(kuò)展數(shù)據(jù)結(jié)構(gòu)144.

使用附加信息設(shè)計新的動態(tài)集合操作。.

INTERVAL-SEARCH(i)

x←rootwhilex≠NILand(low[i]>high[int[x]]orlow[int[x]]>high[i])

do?

i

andint[x]don’toverlapifleft[x]≠NILandlow[i]≤m[left[x]]thenx←left[x]elsex←right[x]returnx新操作1/22/2024算法設(shè)計與分析-擴(kuò)展數(shù)據(jù)結(jié)構(gòu)15x←root[14,16]

與

[17,19]

不重疊14≤18?x←left[x]例子

1:INTERVAL-SEARCH([14,16])1/22/2024算法設(shè)計與分析-擴(kuò)展數(shù)據(jù)結(jié)構(gòu)16[14,16]

與

[5,11]

不重疊14>8?x←right[x]例子

1:INTERVAL-SEARCH([14,16])1/22/2024算法設(shè)計與分析-擴(kuò)展數(shù)據(jù)結(jié)構(gòu)17[14,16]

與

[15,18]

重疊返回

[15,18]例子

1:INTERVAL-SEARCH([14,16])1/22/2024算法設(shè)計與分析-擴(kuò)展數(shù)據(jù)結(jié)構(gòu)18x←root[12,14]

與

[17,19]

不重疊12≤18?x←left[x]例子

2:INTERVAL-SEARCH([12,14])1/22/2024算法設(shè)計與分析-擴(kuò)展數(shù)據(jù)結(jié)構(gòu)19[12,14]

與

[5,11]

不重疊12>8?x←right[x]例子

2:INTERVAL-SEARCH([12,14])1/22/2024算法設(shè)計與分析-擴(kuò)展數(shù)據(jù)結(jié)構(gòu)20[12,14]

與

[15,18]

不重疊12>10?x←right[x]例子

2:INTERVAL-SEARCH([12,14])1/22/2024算法設(shè)計與分析-擴(kuò)展數(shù)據(jù)結(jié)構(gòu)21x=NIL?與[12,14]重疊的區(qū)間不存在。例子

2:INTERVAL-SEARCH([12,14])1/22/2024算法設(shè)計與分析-擴(kuò)展數(shù)據(jù)結(jié)構(gòu)22時間

=O(h)=O(lgn),因為

INTERVAL-SEARCH

沿著一條簡單路徑向下，所以在每層都花費常數(shù)時間。列出所有的重疊區(qū)間:?

搜索,列出,刪除,重復(fù)。?最后將他們重新插入。時間

=O(klgn),

k

是重疊區(qū)間的總數(shù)。存在一個

輸出敏感

的界.至今最好的算法需要:O(k+lgn).分析1/22/2024算法設(shè)計與分析-擴(kuò)展數(shù)據(jù)結(jié)構(gòu)23定理.令L為節(jié)點x的左子樹的區(qū)間集合,并且令R為節(jié)點x的右子樹的區(qū)間集合。?如果搜索走向右邊，那么{i′∈L:i′重疊i}=?.?如果搜索走向左邊,那么{i′∈L:i′重疊i}=??{i′∈R:i′重疊i}=?.換而言之,在2個孩子中選擇1個總是平安的:我們要么找到什么，要么什么都找不到。正確性1/22/2024算法設(shè)計與分析-擴(kuò)展數(shù)據(jù)結(jié)構(gòu)24證明.假設(shè)首先搜索走向右邊。?如果left[x]=NIL,那么得證,因為L=?.?否那么,代碼顯示我們一定有l(wèi)ow[i]>m[left[x]].值m[left[x]]對應(yīng)某些區(qū)間j∈L的高端點,L中的區(qū)間沒有比high[j]還大的高端點。

?

因此,{i′∈L:i′

重疊

i}=?.正確性證明1/22/2024算法設(shè)計與分析-擴(kuò)展數(shù)據(jù)結(jié)構(gòu)25假設(shè)搜索走向左邊,同時假設(shè)

{i′∈L:i′

重疊

i}=?.?然后,代碼顯示

low[i]≤m[left[x]]=

high[j]

對于某些

j∈L.?因