樹結(jié)構(gòu)在程序設(shè)計中的運(yùn)用

1、樹結(jié)構(gòu)在程序設(shè)計中的運(yùn)用,復(fù)旦大學(xué)附中 周文超,樹結(jié)構(gòu)在程序設(shè)計中的運(yùn)用,引言一．并查集二．線段樹三．樹狀數(shù)組小結(jié),引言,近年來，由于各種競賽紛紛采用free-pascal，因此對于算法來說，空間效率上的要求降低了，而對時間效率卻提出了更高的要求。這使得選手不僅要嫻熟地掌握常規(guī)算法，而且要大膽創(chuàng)新，構(gòu)造更高效的算法來解決問題。在以往的程序設(shè)計中，鏈?zhǔn)浇Y(jié)構(gòu)采用得較多。的確鏈?zhǔn)浇Y(jié)構(gòu)有編程復(fù)雜度低、簡單易懂等優(yōu)點(diǎn)，但有一個致命

2、的弱點(diǎn)：相鄰的兩個元素間的聯(lián)系并不明顯。而樹結(jié)構(gòu)卻能很好的做到這一點(diǎn)。 返回,并查集,競賽中會經(jīng)常遇到這樣的題目：給出各個元素之間的聯(lián)系，要求將這些元素分成幾個集合，每個集合中的元素直接或間接有聯(lián)系。在這類問題中主要涉及的是對集合的合并和查找，因此將這種集合稱為并查集。鏈結(jié)構(gòu)的并查集樹結(jié)構(gòu)的并查集,鏈結(jié)構(gòu)的并查集,鏈表被普通用來計算并查集：表中的每個元素設(shè)兩個指針：一個指向同一集合中的下一個

3、元素；另一個指向表首元素。采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，在進(jìn)行集合的查找時的算法復(fù)雜度僅為O（1）；但合并集合時的算法復(fù)雜度卻達(dá)到了O（n）。如果我們希望兩種基本操作的時間效率都比較高的話，鏈?zhǔn)酱鎯Ψ绞骄汀傲Σ粡男摹绷恕?返回,樹結(jié)構(gòu)的并查集,采用樹結(jié)構(gòu)支持并查集的計算能夠滿足我們的要求。并查集與一般的樹結(jié)構(gòu)不同，每個頂點(diǎn)紀(jì)錄的不是它的子結(jié)點(diǎn)，而是將它的父結(jié)點(diǎn)記錄下來。下面我介紹一下樹結(jié)構(gòu)的并查集的兩種運(yùn)算

4、方式⑴直接在樹中查詢⑵邊查詢邊“路徑壓縮”,對應(yīng)與前面的鏈?zhǔn)酱鎯Y(jié)構(gòu)，樹狀結(jié)構(gòu)的優(yōu)勢非常明顯：編程復(fù)雜度低；時間效率高。 返回,直接在樹中查詢,集合的合并算法很簡單，只要將兩棵樹的根結(jié)點(diǎn)相連即可，這步操作只要O（1）時間復(fù)雜度。所以算法的時間效率取決于集合查找的快慢。而集合的查找效率與樹的深度呈線性關(guān)系。因此直接查詢所需要的時間復(fù)雜度平均為O（logN）。但在最壞情況下，樹退化成為一條鏈，使

5、得每一次查詢的算法復(fù)雜度為O（N）。,邊查詢邊“路徑壓縮”,其實(shí)，我們還能將集合查找的算法復(fù)雜度進(jìn)一步降低：采用“路徑壓縮”算法。它的想法很簡單：在集合的查找過程中順便將樹的深度降低。采用路徑壓縮后，每一次查詢所用的時間復(fù)雜度為增長極為緩慢的ackerman函數(shù)的反函數(shù)——α（x）。對于可以想象到的n，α（n）都是在5之內(nèi)的。,返回,,線段樹,處理涉及到圖形的面積、周長等問題的時候，并不需要依賴很深的數(shù)學(xué)知識，但要提高處理此類問題的效率

6、卻又十分困難。這就需要從根本上改變算法的基礎(chǔ)——數(shù)據(jù)結(jié)構(gòu)。這里要說的就是一種特殊的數(shù)據(jù)結(jié)構(gòu)——線段樹。先看一道較基礎(chǔ)的題目：給出區(qū)間上的n條線段，判斷這些線段覆蓋到的區(qū)間大小。通過這題我們來逐步認(rèn)識線段樹。線段樹的定義在線段樹中加入和刪除線段計算測度和連續(xù)線段數(shù) 返回,線段樹的定義,線段樹是一棵二叉樹，將一個區(qū)間劃分為一個個[i，i+1]的單元區(qū)間，每個單元區(qū)間對應(yīng)線段樹中的一個葉子結(jié)點(diǎn)。每個結(jié)點(diǎn)用

7、一個變量count來記錄覆蓋該結(jié)點(diǎn)的線段條數(shù)。,區(qū)間[1，7]所對應(yīng)的線段樹如下圖所示。區(qū)間上有一條線段[3，6]。,在線段樹中插入和刪除線段,在線段樹中插入和刪除線段的方法類似，都采用遞歸逐層向兩個子結(jié)點(diǎn)掃描，直到線段能夠蓋滿結(jié)點(diǎn)表示的整個區(qū)間為止。,經(jīng)過分析可以發(fā)現(xiàn)：在線段樹中插入、刪除線段的時間復(fù)雜度均為O（logN）。,計算測度和連續(xù)線段數(shù),結(jié)點(diǎn)的測度m指的是結(jié)點(diǎn)所表示區(qū)間中線段覆蓋過的長度。,j　-　i (count&

8、gt;0）m= ０ (count=0 且結(jié)點(diǎn)為葉結(jié)點(diǎn)) lch．ｍ + rch．ｍ　　(count=0 且結(jié)點(diǎn)為內(nèi)部結(jié)點(diǎn)),,連續(xù)線段數(shù)line指的是區(qū)間中互不相交的線段條數(shù)。,連續(xù)線段數(shù)并不能像測度那樣將兩個子結(jié)點(diǎn)中的連續(xù)線段數(shù)簡單相加。于是我們引進(jìn)了兩個量lbd，rbd，分別表示區(qū)間的左右兩端是否被線段覆蓋。 1(左端點(diǎn)被線段覆蓋到)lbd = 0

9、(左端點(diǎn)不被線段覆蓋到) 1 (右端點(diǎn)被線段覆蓋到)rbd = 0 (右端點(diǎn)不被線段覆蓋到),計算測度和連續(xù)線段數(shù),,,line可以根據(jù)lbd，rbd定義如下： 1 (count > 0) 0 (count=0 且結(jié)點(diǎn)為葉結(jié)點(diǎn)) Line= lch^.Line + rch^.Line - 1 (count=0 且結(jié)點(diǎn)為

10、內(nèi)部結(jié)點(diǎn)，lch^．rbd、rch^．lbd都為1) lch^.Line + rch^.Line (count=0且結(jié)點(diǎn)為內(nèi)部結(jié)點(diǎn)， lch^．rbd,rch^．Lbd不同時為1),計算測度和連續(xù)線段數(shù),,返回,↙Lbd=1,rbd=1↘,樹狀數(shù)組,IOI2001中的MOBILE難倒了很多選手。雖然該題的題意十分簡單：在一個矩陣中，通過更新元素值修改矩陣狀態(tài)，并計算某子矩陣的數(shù)字和，

11、但難點(diǎn)在于數(shù)據(jù)的規(guī)模極大。下面，我來介紹一種新的數(shù)據(jù)結(jié)構(gòu)—樹狀數(shù)組。1、建立樹狀數(shù)組C2、更新元素值3、子序列求和,利用樹狀數(shù)組，編程的復(fù)雜度提高了，但程序的時間效率也大幅地提高。這正是利用了樹結(jié)構(gòu)能夠減少搜索范圍，將信息集中起來的優(yōu)點(diǎn)，讓更新數(shù)組和求和運(yùn)算牽連盡量少的變量。 返回,建立樹狀數(shù)組C,先將問題簡化，考察一維子序列求和的算法。設(shè)該序列為a[1]，a[2]……a[n]算法1：直接在原序列中計算

12、。顯然更新元素值的時間復(fù)雜度為O(1)；在最壞情況下，子序列求和的時間復(fù)雜度為Ｏ(n)。,以上兩種算法，要么在更新元素值上耗費(fèi)時間過長（算法1），要么在子序列求和上無法避免大量運(yùn)算（算法2）。有沒有更好的方法呢？,算法2：增加數(shù)組b，其中b[i]＝a[1]+a[2]+……+a[i]。由于a[i]的更改影響b[i]┅b[n]，因此在最壞情況下更新元素值的算法復(fù)雜度為O(n)；而子序列求和的算法復(fù)雜度僅為O(1)。,算法三：增加數(shù)組C，其中

13、C[i]=a[i-2k+1]+……+a[i](k為i在二進(jìn)制形式下末尾0的個數(shù))。由c數(shù)組的定義可以得出：c[1]=a[1]c[2]=a[1]+a[2]=c[1]+a[2]c[3]=a[3]c[4]=a[1]+a[2]+a[3]+a[4]=c[2]+c[3]+a[4]c[5]=a[5]c[6]=a[5]+a[6]=c[5]+a[6]………………,在統(tǒng)計更新元素值和子序列求和的算法復(fù)雜度后，會發(fā)現(xiàn)兩種操作的時間復(fù)雜度均為

14、Ｏ（logN），大大提高了算法效率。,,返回,c數(shù)組的結(jié)構(gòu)對應(yīng)一棵樹，因此稱之為樹狀數(shù)組。,更新元素值,定理若a[k]所牽動的序列為C[p1]，C[p2]……C[pm]。則p1=k，而p i+1=pi+2li（li為pi在二進(jìn)制中末尾０的個數(shù)）。,由此得出更改元素值的方法：若將x添加到a[k]，則c數(shù)組中c[p1]、c[p2]、…、c[pm]（pm≤n9 由此得出，c[3]、c[4]、c[8]亦應(yīng)該添加x。

15、 返回,,子序列求和,子序列求和可以轉(zhuǎn)化為求由a[1]開始的序列a[1]……a[k]的和S。而在樹狀數(shù)組中求S十分簡單： 根據(jù)c[k]=a[k-2l+1]+ … +a[k] (l為k在二進(jìn)制數(shù)中末尾０的個數(shù))我們從k1=k出發(fā)，按照ki+1=ki-2lki（lki為ki在二進(jìn)制數(shù)中末尾0的個數(shù)） 公式一遞推k2，k3，…，km (km+1=0)。由此得出

16、S=c[k1]+c[k2]+c[k3] + … + c[km],例如，計算a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7]k1=7k2= k1-2l1=7-20=6k3= k2-2l2=6-21=4k4= k3-2l3=4-22=0 即a[1]+a[2]+ a[3]+a[4]+ a[5]+a[6]+ a[7]=c[7]+c[6]+c[4],子矩陣求和,返回,推廣到二維，同樣也只需要計算由（