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

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

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

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

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

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

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

7、一個(gè)變量count來(lái)記錄覆蓋該結(jié)點(diǎn)的線段條數(shù)。,區(qū)間[1，7]所對(duì)應(yīng)的線段樹(shù)如下圖所示。區(qū)間上有一條線段[3，6]。,在線段樹(shù)中插入和刪除線段,在線段樹(shù)中插入和刪除線段的方法類(lèi)似，都采用遞歸逐層向兩個(gè)子結(jié)點(diǎn)掃描，直到線段能夠蓋滿結(jié)點(diǎn)表示的整個(gè)區(qū)間為止。,經(jīng)過(guò)分析可以發(fā)現(xiàn)：在線段樹(shù)中插入、刪除線段的時(shí)間復(fù)雜度均為O（logN）。,計(jì)算測(cè)度和連續(xù)線段數(shù),結(jié)點(diǎn)的測(cè)度m指的是結(jié)點(diǎn)所表示區(qū)間中線段覆蓋過(guò)的長(zhǎng)度。,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ù)并不能像測(cè)度那樣將兩個(gè)子結(jié)點(diǎn)中的連續(xù)線段數(shù)簡(jiǎn)單相加。于是我們引進(jìn)了兩個(gè)量lbd，rbd，分別表示區(qū)間的左右兩端是否被線段覆蓋。 1(左端點(diǎn)被線段覆蓋到)lbd = 0

9、(左端點(diǎn)不被線段覆蓋到) 1 (右端點(diǎn)被線段覆蓋到)rbd = 0 (右端點(diǎn)不被線段覆蓋到),計(jì)算測(cè)度和連續(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不同時(shí)為1),計(jì)算測(cè)度和連續(xù)線段數(shù),,返回,↙Lbd=1,rbd=1↘,樹(shù)狀數(shù)組,IOI2001中的MOBILE難倒了很多選手。雖然該題的題意十分簡(jiǎn)單：在一個(gè)矩陣中，通過(guò)更新元素值修改矩陣狀態(tài)，并計(jì)算某子矩陣的數(shù)字和，

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

12、。顯然更新元素值的時(shí)間復(fù)雜度為O(1)；在最壞情況下，子序列求和的時(shí)間復(fù)雜度為Ｏ(n)。,以上兩種算法，要么在更新元素值上耗費(fèi)時(shí)間過(guò)長(zhǎng)（算法1），要么在子序列求和上無(wú)法避免大量運(yùn)算（算法2）。有沒(méi)有更好的方法呢？,算法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的個(gè)數(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)計(jì)更新元素值和子序列求和的算法復(fù)雜度后，會(huì)發(fā)現(xiàn)兩種操作的時(shí)間復(fù)雜度均為

14、Ｏ（logN），大大提高了算法效率。,,返回,c數(shù)組的結(jié)構(gòu)對(duì)應(yīng)一棵樹(shù)，因此稱(chēng)之為樹(shù)狀數(shù)組。,更新元素值,定理若a[k]所牽動(dòng)的序列為C[p1]，C[p2]……C[pm]。則p1=k，而p i+1=pi+2li（li為pi在二進(jìn)制中末尾０的個(gè)數(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]開(kāi)始的序列a[1]……a[k]的和S。而在樹(shù)狀數(shù)組中求S十分簡(jiǎn)單： 根據(jù)c[k]=a[k-2l+1]+ … +a[k] (l為k在二進(jìn)制數(shù)中末尾０的個(gè)數(shù))我們從k1=k出發(fā)，按照ki+1=ki-2lki（lki為ki在二進(jìn)制數(shù)中末尾0的個(gè)數(shù)） 公式一遞推k2，k3，…，km (km+1=0)。由此得出

16、S=c[k1]+c[k2]+c[k3] + … + c[km],例如，計(jì)算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],子矩陣求和,返回,推廣到二維，同樣也只需要計(jì)算由（