北大信息院數(shù)據(jù)結(jié)構(gòu)12advds

第十二章高級(jí)樹結(jié)構(gòu)

任課教員：張銘

北京大學(xué)信息科學(xué)與技術(shù)學(xué)院網(wǎng)絡(luò)與信息系統(tǒng)研究所，轉(zhuǎn)載或翻印必究北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page2主要內(nèi)容12.1Trie和Patricia

結(jié)構(gòu)

12.2改進(jìn)的BST

最佳二叉搜索樹

AVL樹伸展樹

12.3空間樹結(jié)構(gòu)

12.4決策樹和博弈樹北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page312.1Trie結(jié)構(gòu)和Patricia樹BST（二叉搜索樹）不是一棵平衡的樹，它的樹結(jié)構(gòu)與輸入數(shù)據(jù)的順序有很大的關(guān)系北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page4

對(duì)象空間(objectspace)分解BST是一種組織上基于對(duì)象空間(objectspace)分解的數(shù)據(jù)結(jié)構(gòu)空間分解是存儲(chǔ)在樹中的對(duì)象（關(guān)鍵碼值）決定最簡(jiǎn)單的方法就是對(duì)對(duì)象（這里是關(guān)鍵碼）的范圍進(jìn)行劃分平均劃分按照某種方式不平均劃分北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page5

假設(shè)劃分因子為2每次僅把當(dāng)前范圍分為兩部分（對(duì)應(yīng)于二叉樹）在進(jìn)行插入的時(shí)候，只要是小于結(jié)點(diǎn)的關(guān)鍵碼的都在左子樹中只要是大于結(jié)點(diǎn)的關(guān)鍵碼的都在右子樹中

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page6關(guān)鍵碼空間（keyspace）分解

不依賴于關(guān)鍵碼的插入順序樹的深度受到關(guān)鍵碼精度的影響最壞的情況下，深度等于存儲(chǔ)關(guān)鍵碼所需要的位數(shù)

例如，如果關(guān)鍵碼是0到255之間的整數(shù)，那么關(guān)鍵碼的精度就是8個(gè)二進(jìn)制位。如果有兩個(gè)關(guān)鍵碼：10000010和10000011，它們的前面7位都是相同的所以直到第8次劃分才能將這兩個(gè)關(guān)鍵碼分開這樣的搜索樹深度也為8，但這是最壞的情況

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page7基于關(guān)鍵碼范圍的分解保證平衡嗎？顯然是不行的如果關(guān)鍵碼的分布得很不均衡，將導(dǎo)致樹的結(jié)構(gòu)失衡

一種極端的情況，導(dǎo)致所有的關(guān)鍵碼都小于根結(jié)點(diǎn)，那么以該結(jié)點(diǎn)為根的子樹的右子樹將沒有任何的元素

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page8Trie結(jié)構(gòu)

基于關(guān)鍵碼分解的數(shù)據(jù)結(jié)構(gòu)，叫作Trie結(jié)構(gòu)

“trie”這個(gè)詞來(lái)源于“retrieval”主要應(yīng)用信息檢索（informationretrieval）

用來(lái)存儲(chǔ)英文字符串，尤其大規(guī)模的英文詞典自然語(yǔ)言理解系統(tǒng)中經(jīng)常用到

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page9Trie結(jié)構(gòu)的適用情況Trie結(jié)構(gòu)主要基于兩個(gè)原則有一個(gè)固定的關(guān)鍵碼集合

對(duì)于結(jié)點(diǎn)的分層標(biāo)記

如果所有的元素都可以使用數(shù)字或者字母等來(lái)標(biāo)記，那么就可以考慮使用Trie結(jié)構(gòu)

例如，元素可以用0-9的數(shù)字來(lái)標(biāo)記在根結(jié)點(diǎn)的地方，它分出10個(gè)子結(jié)點(diǎn)，分別標(biāo)記0-9然后每個(gè)子結(jié)點(diǎn)又可以分出10個(gè)結(jié)點(diǎn)如此下去直到所有的元素都能夠被區(qū)分開北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page10Trie結(jié)構(gòu)特點(diǎn)與B+樹一樣，基于關(guān)鍵碼空間分解的樹結(jié)構(gòu)，其內(nèi)部結(jié)點(diǎn)僅作為占位符引導(dǎo)檢索過程，數(shù)據(jù)紀(jì)錄只存儲(chǔ)在葉結(jié)點(diǎn)中

Huffman編碼樹(Huffmancodingtree)也是一種二叉Trie樹

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page11Trie結(jié)構(gòu)示意圖北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page12Trie結(jié)構(gòu)應(yīng)用：“字符樹”

存儲(chǔ)字典里面的單詞英文的單詞是有26個(gè)字母組成的（簡(jiǎn)單起見，我們忽略大小寫），英文字符樹每一個(gè)內(nèi)部結(jié)點(diǎn)都有26個(gè)子結(jié)點(diǎn)樹的高度為最長(zhǎng)字符串長(zhǎng)度北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page13英文字符樹

一棵子樹代表具有相同前綴的關(guān)鍵碼的集合。例如“an”子樹代表具有相同前綴an-的關(guān)鍵碼集合{and，ant}

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page14字符樹的改進(jìn)

由于單詞可能不等長(zhǎng)，所以更好的存儲(chǔ)是其內(nèi)部結(jié)點(diǎn)不存儲(chǔ)單詞信息，只有葉結(jié)點(diǎn)才存儲(chǔ)單詞信息

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page15字符樹的改進(jìn)（續(xù)）觀察上圖中的bad和bee兩個(gè)單詞，它們的父結(jié)點(diǎn)都只有一個(gè)兒子就是它們自己，也就是說，實(shí)際上它們?cè)诟附Y(jié)點(diǎn)的時(shí)候就已經(jīng)被區(qū)分開了因?yàn)槲覀冋嬲胱龅氖且獧z索每一個(gè)單詞，不需要在已經(jīng)能夠區(qū)分每個(gè)單詞的情況下繼續(xù)進(jìn)行分裂結(jié)點(diǎn)的動(dòng)作

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page16字符樹的改進(jìn)（續(xù)）北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page17字符樹中的檢索

首先用待查關(guān)鍵碼的第一個(gè)字符與樹林的各個(gè)根的字符相比較

然后下一步的檢索在前次比較相等的那棵樹上進(jìn)行其中，用待查關(guān)鍵碼的第二個(gè)字符與選定的這棵樹的根的各個(gè)子結(jié)點(diǎn)進(jìn)行比較，接著再沿著前次比較相等的分支進(jìn)行進(jìn)一步的檢索...

直到進(jìn)行到某一層，該層所有結(jié)點(diǎn)的字符都與待查關(guān)鍵碼相應(yīng)位置的字符不同，這說明此關(guān)鍵碼在樹目錄里沒有出現(xiàn)；若檢索一直進(jìn)行到樹葉，那么就在樹目錄里找到了給定的關(guān)鍵碼北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page18Trie字符樹的缺陷Trie結(jié)構(gòu)顯然也不是平衡的在它存取英文單詞的時(shí)候，顯然t子樹下的分支比z子樹下的分支多很多（以t開頭的單詞比以z開頭的單詞多很多）

而且，每次有26個(gè)分支因子使得樹的結(jié)構(gòu)過于龐大，給檢索也帶來(lái)了不便

字母在計(jì)算機(jī)中是以二進(jìn)制ASCII碼的形式存儲(chǔ)的使用每個(gè)字母的二進(jìn)制編碼來(lái)代表這個(gè)字母關(guān)鍵碼就只有編碼0和1而不是a到z的26個(gè)字母二叉Trie樹

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page19Trie樹的插入Trie樹的插入

首先根據(jù)插入紀(jì)錄的關(guān)鍵碼找到需要插入的結(jié)點(diǎn)位置

如果該結(jié)點(diǎn)是葉結(jié)點(diǎn)，那么就將為其分裂出兩個(gè)子結(jié)點(diǎn)，分別存儲(chǔ)這個(gè)紀(jì)錄和以前的那個(gè)紀(jì)錄

如果是內(nèi)部結(jié)點(diǎn)，則在那個(gè)分支上應(yīng)該是空的，所以直接為該分支建立一個(gè)新的葉結(jié)點(diǎn)即可

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page20Trie樹的刪除Trie樹的刪除根據(jù)插入紀(jì)錄的關(guān)鍵碼找到需要?jiǎng)h除的結(jié)點(diǎn)位置如果一個(gè)被刪除結(jié)點(diǎn)的父結(jié)點(diǎn)沒有其他的兒子，那么就需要合并否則只需要將此分支設(shè)置為空即可北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page21PATRICIA結(jié)構(gòu)為了得到更加平衡的結(jié)構(gòu)，D.Morrision發(fā)明了Trie結(jié)構(gòu)的一種變體PATRICIA

“PracticalAlgorithmToRetrieveInformationCodedInAlphanumeric”它不是對(duì)整個(gè)關(guān)鍵碼大小范圍的劃分而是根據(jù)關(guān)鍵碼每一個(gè)二進(jìn)制位的編碼來(lái)劃分因?yàn)槊恳晃灰词?，要么是1，所以分支因子是2，生成的樹是二叉樹

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page22PATRICIA結(jié)構(gòu)圖北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page23PATRICIA結(jié)構(gòu)圖（續(xù)）上圖因?yàn)樽畲蟮臄?shù)是63，用6位二進(jìn)制表示即可每一個(gè)結(jié)點(diǎn)都有一個(gè)標(biāo)號(hào)，表示它是在比較第幾位，然后根據(jù)那一位是0還是1來(lái)劃分左右兩個(gè)子樹標(biāo)號(hào)為2的結(jié)點(diǎn)的右子樹一定是編碼形式為xx1xxx

（x表示該位或0或1，標(biāo)號(hào)為2說明比較第2位）在圖中檢索5的話，5的編碼為000101

首先我們比較第0位，從而進(jìn)入左子樹然后在第1位仍然是0，還是進(jìn)入左子樹在第2位還是0，仍進(jìn)入左子樹第3位變成了1，從而進(jìn)入右子樹，就找到了位于葉結(jié)點(diǎn)的數(shù)字5北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page24

PATRICIA結(jié)構(gòu)圖改進(jìn)觀察PATRICIA的圖發(fā)現(xiàn)有與Trie圖類似的情況在區(qū)分2和5、41和45的時(shí)候，在第三個(gè)二進(jìn)制位的比較是不能區(qū)別它們的

可以將它省略，得到一棵更為簡(jiǎn)潔的樹

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page25PATRICIA結(jié)構(gòu)圖改進(jìn)（續(xù)）北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page26PATRICIA的特點(diǎn)每個(gè)內(nèi)部結(jié)點(diǎn)都代表一個(gè)位的比較，必然產(chǎn)生兩個(gè)子結(jié)點(diǎn)所以它是一個(gè)滿二叉樹進(jìn)行一次檢索，最多只需要關(guān)鍵碼位數(shù)次的比較即可

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page2712.2二叉樹結(jié)構(gòu)的改進(jìn)

平衡的二叉搜索樹、伸展樹和最佳二叉排序樹，它們都是對(duì)二叉樹的結(jié)構(gòu)或者操作規(guī)則做部分的改進(jìn)以使樹保持在一種類似于平衡的狀態(tài)，從而達(dá)到較好的效率

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page2812.2.1最佳二叉搜索樹

根據(jù)前面章節(jié)的二叉樹介紹我們知道對(duì)應(yīng)于關(guān)鍵碼集合K:K={xal,wan,wil,zol,yo,xul,yum,wen,wim,zi,yon,xem,wul,zom}的二叉排序樹

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page29二叉搜索樹的多樣性

同一個(gè)關(guān)鍵碼集合，其關(guān)鍵碼插入二叉搜索樹的次序不同，就構(gòu)成不同的二叉搜索樹。

包括n個(gè)關(guān)鍵碼的集合中，關(guān)鍵碼可以有n!種不同的排列法，因此可以構(gòu)成n!個(gè)二叉搜索樹(其中有相同的)

可以用檢索效率來(lái)衡量二叉搜索樹北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page30

如果只計(jì)算不同的搜索樹，則排列{2，1，3}的順序插入關(guān)鍵碼與按照排列{2，3，1}的順序插入所構(gòu)成的二叉搜索樹完全相同

這種非前序排列的序列，總是可以找到與其相對(duì)應(yīng)的一個(gè)合法前序排列這n!種排列中，

只有

就是說n個(gè)結(jié)點(diǎn)可以構(gòu)造稱為Catalan函數(shù)

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page31擴(kuò)充的二叉樹第4章討論過擴(kuò)充的二叉樹的概念。擴(kuò)充的二叉樹是滿二叉樹，新增加的空樹葉(以下稱為外部結(jié)點(diǎn))的個(gè)數(shù)等于原來(lái)二叉樹的結(jié)點(diǎn)(以下稱為內(nèi)部結(jié)點(diǎn))個(gè)數(shù)加1

在擴(kuò)充的二叉搜索樹里，關(guān)鍵碼值最小的內(nèi)部結(jié)點(diǎn)的左子女(外部結(jié)點(diǎn))代表了值小于該內(nèi)部結(jié)點(diǎn)的可能關(guān)鍵碼的集合；關(guān)鍵碼值最大的內(nèi)部結(jié)點(diǎn)的右子女(外部結(jié)點(diǎn))代表了值大于該內(nèi)部結(jié)點(diǎn)的可能關(guān)鍵碼的集合除此之外，每個(gè)外部結(jié)點(diǎn)代表其值處于原來(lái)二叉搜索樹的兩個(gè)相鄰結(jié)點(diǎn)的關(guān)鍵碼值之間的可能關(guān)鍵碼的集合北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page32路徑長(zhǎng)度外部路徑長(zhǎng)度E定義為從擴(kuò)充的二叉樹的根到每個(gè)外部結(jié)點(diǎn)的路徑長(zhǎng)度之和。內(nèi)部路徑長(zhǎng)度I定義為擴(kuò)充的二叉樹里從根到每個(gè)內(nèi)部結(jié)點(diǎn)的路徑長(zhǎng)度之和

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page33二叉搜索樹里檢索算法在二叉搜索樹里檢索算法十分簡(jiǎn)單：首先用待查的關(guān)鍵碼與二叉搜索樹的根結(jié)點(diǎn)進(jìn)行比較，若比較相等，則找到了要檢索的關(guān)鍵碼；若比較不等，具待查關(guān)鍵碼值小于根結(jié)點(diǎn)的關(guān)鍵碼值，則下一次與根的左子樹的根比較；否則與根的右子樹的根比較。如此遞歸地進(jìn)行下去，直到某一次比較相等，檢索成功；或一直比較到樹葉都不相等，檢索失敗。

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page34檢索一個(gè)關(guān)鍵碼的比較次數(shù)

在檢索過程中，每進(jìn)行一次比較，就進(jìn)入下面一層。因此，對(duì)于成功的檢索，比較的次數(shù)就是關(guān)鍵碼所在的層數(shù)加1。對(duì)于不成功的檢索，被檢索的關(guān)鍵碼屬于哪個(gè)外部結(jié)點(diǎn)代表的可能關(guān)鍵碼集合，比較次數(shù)就等于此外部結(jié)點(diǎn)的層數(shù)

在二叉搜索樹里，檢索一個(gè)關(guān)鍵碼的平均比較次數(shù)為北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page35參數(shù)意義其中1i，是第i個(gè)內(nèi)部結(jié)點(diǎn)的層數(shù)，是第i個(gè)外部結(jié)點(diǎn)的層數(shù)，pi是檢索第i個(gè)內(nèi)部結(jié)點(diǎn)所代表的關(guān)鍵碼的頻率qi是被檢索的關(guān)鍵碼屬于第i個(gè)外部結(jié)點(diǎn)代表的可能關(guān)鍵碼集合(即處于第i個(gè)和第i+1個(gè)內(nèi)部結(jié)點(diǎn)之間)的頻率。pi，qi也叫做結(jié)點(diǎn)的權(quán)

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page36最佳二叉搜索樹定義

是檢索第i個(gè)內(nèi)部結(jié)點(diǎn)所代表的關(guān)鍵碼的概率，是被檢索的關(guān)鍵碼屬于第i個(gè)外部結(jié)點(diǎn)代表的可能關(guān)鍵碼集合的概率。

我們把檢索中平均比較次數(shù)最小，也就是ASL(n)最小的二叉搜索樹稱作最佳二叉搜索樹

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page37什么樣的二叉搜索樹是最佳的？檢索所有結(jié)點(diǎn)的概率都相等，即所有結(jié)點(diǎn)的權(quán)都相等：因此，要平均比較次數(shù)ASL(n)最小，就是要內(nèi)部路徑長(zhǎng)度I最小

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page38在一棵二叉樹里，路徑長(zhǎng)度為0的結(jié)點(diǎn)僅有一個(gè)，路徑長(zhǎng)度為1的結(jié)點(diǎn)至多有兩個(gè)，路徑長(zhǎng)度為2的結(jié)點(diǎn)至多有四個(gè)，等等。因此，有n個(gè)結(jié)點(diǎn)的二叉樹其內(nèi)部路徑長(zhǎng)度I至少等于序列:0，1，1，2，2，2，2，3，3，3，3，3，3，3，4，4，…的前n項(xiàng)和。這個(gè)和寫成:北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page39可以證明：這種二叉樹的特點(diǎn)是只有最下面的兩層結(jié)點(diǎn)的度數(shù)可以小于2，其它結(jié)點(diǎn)度數(shù)必須等于2。在所有結(jié)點(diǎn)的權(quán)相等的情況下，這樣的二叉搜索樹是最佳二叉搜索樹，對(duì)它進(jìn)行檢索的平均比較次數(shù)為這個(gè)ASL(n)是O(log2n)量級(jí)的

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page40最佳二叉搜索樹構(gòu)造舉例首先將集合K里的關(guān)鍵碼排序

{wan，wen，wil，wim，wul，xal，xem，xul，yo，yon，yum，zi，zol，zom}然后用二分法依次檢索這些關(guān)鍵碼，并把在檢索中遇到的在二叉搜索樹里還沒有的關(guān)鍵碼依次插入二叉搜索樹中。首先檢索序列中的第一個(gè)關(guān)鍵碼wan，用二分法檢索wan的過程中會(huì)依次遇到關(guān)鍵碼xem，wil，wan，這就是最先插入二叉搜索樹的三個(gè)關(guān)鍵碼。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page41最佳二叉搜索樹構(gòu)造舉例然后檢索序列中的第二個(gè)關(guān)鍵碼wen，用二分法檢索wen的過程中會(huì)依次遇到關(guān)鍵碼xem，wil，wan，wen，其中只有

wen是二叉搜索樹中還沒有的，因此第四個(gè)插入到二叉搜索樹中的關(guān)鍵碼是wen。再檢索序列中的第三個(gè)關(guān)鍵碼wil，…，如此進(jìn)行下去，直到所有的關(guān)鍵碼都已插入到二叉搜索樹中，這樣可得到最佳二叉搜索樹。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page42北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page43二叉搜索樹的效率反過來(lái)，如果關(guān)鍵碼按值遞增的順序依次插入到二叉搜索樹中，則將得到退化為線性的二叉搜索樹平均比較次數(shù)為O(n)

按任意的順序把關(guān)鍵碼插入到二叉搜索樹中，它的檢索效率如何呢？平均比較次數(shù)是接近最壞的情況O(n)呢，還是接近最好的情況O(1og2n)?可以證明，對(duì)n!種二叉搜索樹進(jìn)行平均，得到的平均檢索次數(shù)仍是O(1og2n)

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page44檢索各結(jié)點(diǎn)的概率不相等的情況

檢索各結(jié)點(diǎn)的概率不相等的情況，即在具有不等權(quán)結(jié)點(diǎn)的二叉搜索樹里進(jìn)行檢索。

現(xiàn)在的問題是給了一個(gè)排好序的關(guān)鍵碼集合{keyl，key2，…，keyn}，和權(quán)的集合{p1，p2，…，pn，q0，q1，…，qn}，要找使得ASL(n)為最小的最佳二叉排序樹，也就是要找使得為最小，上式也稱為二叉排序樹的開銷

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page45北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page46最佳二叉搜索樹的構(gòu)造方法最佳二叉搜索樹有個(gè)特點(diǎn)：它的任何子樹都是最佳二叉搜索樹。這一事實(shí)引導(dǎo)我們可以用這樣的方法構(gòu)造越來(lái)越大的最佳二叉搜索樹：先構(gòu)造包括一個(gè)結(jié)點(diǎn)的最佳二叉搜索樹，再構(gòu)造包括兩個(gè)結(jié)點(diǎn)的最佳二叉搜索樹，…，直到把所有的結(jié)點(diǎn)都包括進(jìn)去。后來(lái)構(gòu)造的較大的最佳二叉搜索樹用前面構(gòu)造的較小的最佳二叉搜索樹作為其子樹

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page47設(shè)包括關(guān)鍵碼keyi+1，keyi+2，…，keyj為內(nèi)部結(jié)點(diǎn)(0≤i≤j≤n)，結(jié)點(diǎn)的權(quán)為(qi，pi+1，

qi+1，…，pj，qj)的最佳二叉搜索樹為t(i，j)，其根為r(i，j)，其花費(fèi)為C(i，j)，其權(quán)的總和為W(i，j)=pi+1+…+pj+qi+qi+1+…+qj第一步構(gòu)造包括一個(gè)結(jié)點(diǎn)的最佳二叉搜索樹，就是找t(0，1)，t(1，2)，…，t(n-1，n)。

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page48第二步構(gòu)造包括兩個(gè)結(jié)點(diǎn)的最佳二叉搜索樹，就是找t(0，2)，t(1，3)，…，t(n-2，n)

再構(gòu)造包括三個(gè)，四個(gè)，…結(jié)點(diǎn)的最佳二叉搜索樹，直到最后構(gòu)造t(0，n)如何構(gòu)造最佳二叉搜索樹t(i，j)呢?由最佳二叉搜索樹的子樹必是最佳二叉搜索樹的原理可知：C(i，j)=W(i，j)+(C(i，k-1)+C(k，j))北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page49這個(gè)式子的意思是，用下列方法來(lái)找包括keyi+1，keyi+2，…，keyj為內(nèi)部結(jié)點(diǎn)的最佳二叉搜索樹t(i，j)：分別用keyi+1，keyi+2，…，keyj為根，考慮j-i棵二叉搜索樹。以keyk為根的二叉搜索樹其左子樹包括keyi+1，…，keyk-1，而包括這些關(guān)鍵碼為內(nèi)部結(jié)點(diǎn)的最佳二又排序樹t(i，k-1)已在前面的步驟確定，C(i，

k-1)已求出，而以keyk為根的二叉搜索樹其右子樹包括keyk+l，keyk+2，…，keyj，以這些關(guān)鍵碼為內(nèi)部結(jié)點(diǎn)的最佳二叉搜索樹t(k，j)也已在前面的步驟確定，C(k，j)已求出。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page50對(duì)于i<k≤l找出使C(i，k-1)+C(k，j)為最小的那個(gè)k0，以keyk0為根，t(i，k0-1)為左子樹，t(k0，j)為右子樹的那個(gè)二叉搜索樹就是所要求的t(i，j)。其花費(fèi)

C(i，j)等于其根的左子樹的花費(fèi)C(i，

k0-1)加上右子樹花費(fèi)C(k0，j)，再加上結(jié)點(diǎn)的總的權(quán)W(i，j)

每一步構(gòu)造出一棵最佳二叉搜索樹t(i，j)就記下其根r(i，j)，花費(fèi)C(i，j)，最后構(gòu)造出t(0，

n)，整個(gè)最佳二叉搜索樹的結(jié)構(gòu)就明確了

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page51不等權(quán)結(jié)點(diǎn)的最佳二叉搜索樹算法

voidOptimalBST(inta[],intb[],intn,intc[N+1][N+1],intr[N+1][N+1],intw[N+1][N+1]){for(inti=0;i<=n;i++)for(intj=0;j<=n;j++) {//初始化

c[i][j]=0; r[i][j]=0; w[i][j]=0; }北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page52

for(i=0;i<=n;i++){ w[i][i]=b[i]; //求出權(quán)和w[i.j] for(intj=i+1;j<=n;j++) w[i][j]=w[i][j-1]+a[j]+b[j]; }//確定一個(gè)結(jié)點(diǎn)的最佳二叉排序樹

for(intj=1;j<=n;j++) { c[j-1][j]=w[j-1][j]; r[j-1][j]=j; }北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page53//確定d個(gè)結(jié)點(diǎn)的最佳二叉樹

intm,k0,k; for(intd=2;d<=n;d++) { for(intj=d;j<=n;j++) { i=j-d; m=c[i+1][j]; k0=i+1; for(k=i+2;k<=j;k++) {北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page54

if(c[i][k-1]+c[k][j]<m) { m=c[i][k-1]+c[k][j]; k0=k; } } c[i][j]=w[i][j]+m; r[i][j]=k0; } }}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page55構(gòu)造過程給出關(guān)鍵碼集合及權(quán)的序列計(jì)算次數(shù)為北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page56北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page57北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page58北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page59動(dòng)態(tài)規(guī)劃（dynamicprogramming）

動(dòng)態(tài)規(guī)劃方法將問題分解為若干個(gè)子問題，分別求解子問題的解，然后由這些子問題的解得到原問題的解。動(dòng)態(tài)規(guī)劃算法的有效性依賴于問題本身所具有的兩個(gè)重要性質(zhì)：最優(yōu)子結(jié)構(gòu)性質(zhì)和子問題重疊性質(zhì)最優(yōu)子結(jié)構(gòu)是指問題的最優(yōu)解包含其子問題的最優(yōu)解重疊子問題是指在自頂向下的遞歸求解問題時(shí)，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計(jì)算多次北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page60動(dòng)態(tài)規(guī)劃與分治策略動(dòng)態(tài)規(guī)劃與分治策略有著明顯的不同。分治策略要求子問題之間相互獨(dú)立，可以根據(jù)最有子結(jié)構(gòu)直接用遞歸法求解而動(dòng)態(tài)規(guī)劃方法所處理的子問題相互交叉。直接用遞歸法來(lái)求解具有重疊子問題性質(zhì)的后一類問題時(shí)，常常要大量重復(fù)計(jì)算公共的子問題；而動(dòng)態(tài)規(guī)劃對(duì)每個(gè)子問題僅僅求解一次，并將結(jié)果填寫到若干張表中，下次計(jì)算同一子問題時(shí)直接利用表中的結(jié)果。動(dòng)態(tài)規(guī)劃的具體形式雖然多種多樣，但它們一般都具有“填表”這一基本模式。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page61動(dòng)態(tài)規(guī)劃的應(yīng)用動(dòng)態(tài)規(guī)劃方法通常由于解決優(yōu)化問題。這一類問題往往具有多個(gè)可行解，每一個(gè)解對(duì)應(yīng)一個(gè)值。我們希望找到其中一個(gè)具有最優(yōu)值（最大值或最小值）的解，稱為最優(yōu)解（可能存在多個(gè)最優(yōu)解具有同一個(gè)最優(yōu)值）。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page62動(dòng)態(tài)規(guī)劃算法的步驟設(shè)計(jì)一個(gè)動(dòng)態(tài)規(guī)劃算法的步驟如下：（1）刻畫最優(yōu)解的結(jié)構(gòu)特征（2）遞歸定義最優(yōu)值（3）以自底向上的方式計(jì)算出最優(yōu)值（4）根據(jù)計(jì)算過程的信息構(gòu)造一個(gè)最優(yōu)解步驟（1）-（3）是動(dòng)態(tài)規(guī)劃方法求解最優(yōu)值的基本步驟。如果需要求得最優(yōu)解，則需要進(jìn)一步記錄計(jì)算過程的信息并執(zhí)行步驟（4）。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page63動(dòng)態(tài)規(guī)劃算法求解例子設(shè)計(jì)一個(gè)時(shí)間的算法，找出由n個(gè)數(shù)組成的序列的最長(zhǎng)單調(diào)遞增子序列。將這個(gè)的算法的優(yōu)化為的算法

設(shè)A和B是兩個(gè)字符串。對(duì)字符串可以進(jìn)行如下操作：（1）刪除一個(gè)字符（2）插入一個(gè)字符（3）將一個(gè)字符替換為另一個(gè)字符利用以上三種操作可以將字符串A轉(zhuǎn)換為字符串B。我們稱這種轉(zhuǎn)換所需要的最少的字符串操作次數(shù)為字符串A到B的編輯距離（EditDistance），記為。設(shè)計(jì)一個(gè)算法，對(duì)任給的兩個(gè)字符串A和B，計(jì)算出它們的編輯距離

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page6412.2.2平衡的二叉搜索樹(AVL)

BST受輸入順序影響最好O(logn)

最壞O(n)

怎樣使得BST始終保持O(logn)級(jí)的平衡狀態(tài)？Adelson-Velskii和Landis發(fā)明了AVL樹一種平衡的二叉搜索樹任何結(jié)點(diǎn)的左子樹和右子樹高度最多相差1北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page65AVL樹的性質(zhì)可以為空具有n個(gè)結(jié)點(diǎn)的AVL樹，高度為O(logn)

如果T是一棵AVL樹那么它的左右子樹TL、TR也是AVL樹并且|hL-hR|≤1hL、hR是它的左右子樹的高度

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page66北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page67平衡因子平衡因子，用bf(x)來(lái)表示結(jié)點(diǎn)x的平衡因子。它被定義為：

bf(x)=x的右子樹的高度

–x的左子樹的高度對(duì)于一個(gè)AVL樹中的結(jié)點(diǎn)平衡因子之可能取值為0，1和-1

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page68AVL樹結(jié)點(diǎn)的插入

插入與BST一樣新結(jié)點(diǎn)作葉結(jié)點(diǎn)需要調(diào)整相應(yīng)子樹的根結(jié)點(diǎn)變化大致有三類結(jié)點(diǎn)原來(lái)是平衡的，現(xiàn)在成為左重或右重的修改相應(yīng)前驅(qū)結(jié)點(diǎn)的平衡因子結(jié)點(diǎn)原來(lái)是某一邊重的，而現(xiàn)在成為平衡的了樹的高度未變，不修改結(jié)點(diǎn)原來(lái)就是左重或右重的，而新結(jié)點(diǎn)又加到重的一邊不平衡“危急結(jié)點(diǎn)”北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page69恢復(fù)平衡插入17后導(dǎo)致不平衡重新調(diào)整為平衡結(jié)構(gòu)北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page70不平衡的情況正常情況下，一個(gè)結(jié)點(diǎn)A的平衡因子只能是0，1，-1，而在非正常情況有下面四種可能

LL型：導(dǎo)致不平衡的結(jié)點(diǎn)為A的左子樹的左結(jié)點(diǎn)，這時(shí)A的平衡因子為-2

LR型：導(dǎo)致不平衡的結(jié)點(diǎn)為A的左子樹的右結(jié)點(diǎn)，這時(shí)A的平衡因子為-2

RL型：導(dǎo)致不平衡的結(jié)點(diǎn)為A的右子樹的左結(jié)點(diǎn)，這時(shí)A的平衡因子為2

RR型：導(dǎo)致不平衡的結(jié)點(diǎn)為A的右子樹的右結(jié)點(diǎn)，這時(shí)A的平衡因子為2

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page71不平衡的圖示LL型RR型的北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page72不平衡情況總結(jié)LL型和RR型是對(duì)稱的，LR型和RL型是對(duì)稱的

不平衡的結(jié)點(diǎn)一定在根結(jié)點(diǎn)與新加入結(jié)點(diǎn)之間的路徑上

它的平衡因子只能是2或者-2如果是2，它在插入前的平衡因子是1如果是-2，它在插入前的平衡因子是-1

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page73解決不平衡的方法——旋轉(zhuǎn)我們可以使用一系列稱為旋轉(zhuǎn)(rotation)的局部操作解決這個(gè)問題

LL和RR的情況可以通過單旋轉(zhuǎn)(singlerotation)來(lái)解決

RL和LR的情況可以通過雙旋轉(zhuǎn)(doublerotation)來(lái)解決

調(diào)整的整個(gè)過程稱之為重構(gòu)（restructuring）北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page74

單旋轉(zhuǎn)如果加入一個(gè)新結(jié)點(diǎn)后需要對(duì)根為結(jié)點(diǎn)a的子樹進(jìn)行單旋轉(zhuǎn)，假設(shè)b為包含新加入結(jié)點(diǎn)的a的子女，c為包含新加入結(jié)點(diǎn)的b的子女單旋轉(zhuǎn)，那么令b代替a成為新根，a和c作為其子結(jié)點(diǎn)；原來(lái)c的子樹保持不變；原來(lái)b中c結(jié)點(diǎn)的兄弟子樹，代替原b子樹作為a的子樹

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page75單旋轉(zhuǎn)示意圖（LL型）北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page76北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page77單旋轉(zhuǎn)示意圖（RR型）RR型單旋轉(zhuǎn)北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page78雙旋轉(zhuǎn)

RL或者LR需要進(jìn)行雙旋轉(zhuǎn)這兩種情況是對(duì)稱的我們只討論RL的情況LR是一樣的北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page79RL型雙旋轉(zhuǎn)第一步北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page80RL型雙旋轉(zhuǎn)第二步北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page81旋轉(zhuǎn)運(yùn)算的實(shí)質(zhì)以RR型圖示為例，總共有7個(gè)部分三個(gè)結(jié)點(diǎn)：a、b、c四棵子樹a的左子樹T0b的左子樹T1c的左子樹T2和右子樹T3加重的是c為根的子樹，但是其結(jié)構(gòu)其實(shí)沒有變化因此，可以整體地看作b的右子樹

目的：重新組成一個(gè)新的AVL結(jié)構(gòu)

平衡保留了中序周游的性質(zhì)T0aT1bT2cT3

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page82旋轉(zhuǎn)運(yùn)算的實(shí)質(zhì)（續(xù)）把樹做任何一種旋轉(zhuǎn)（RR、RL、LL、LR）新樹保持了原來(lái)的中序周游順序旋轉(zhuǎn)處理中僅需改變少數(shù)指針而且新的子樹高度為h+2，保持插入前子樹的高度不變?cè)瓉?lái)二叉樹在a結(jié)點(diǎn)上面的其余部分（若還有的話）總是保持平衡的北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page83template<classT>classavlNode//平衡二叉樹結(jié)點(diǎn)類{public:avlNode(Tval);//構(gòu)造函數(shù)avlNode(Tval,avlNode<T>*left,avlNode<T>*right,intbf);voidrelease();//刪除以當(dāng)前結(jié)點(diǎn)為根的左右子樹

avlNode<T>*leftptr;//左右指針avlNode<T>*rightptr; intadd(avlNode<T>*&p,Tval);//插入一個(gè)值；返回新的avl樹的根結(jié)點(diǎn)的指針voidpreorderview(avlNode<T>*current,inti=-1);//前序周游avlNode<T>*remove(Tval,avlNode<T>*&waste,int&flag);//根為當(dāng)前結(jié)點(diǎn)的val結(jié)點(diǎn)avlNode<T>*findNodeValue(Tval);//查找val結(jié)點(diǎn)Tvalue;//碼值北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page84private:intbf;//平衡因子avlNode<T>*removeLeftmostElement(avlNode<T>*&childptr,int&flag);//找最左的結(jié)點(diǎn)avlNode<T>*LL_singleRotation();//左子樹LL失衡，返回調(diào)整后新樹根avlNode<T>*RR_singleRotation();//右子樹RR失衡，返回調(diào)整后新樹根avlNode<T>*LR_doubleRotation();//左子樹LR失衡，返回調(diào)整后新樹根avlNode<T>*RL_doubleRotation();//右子樹RL失衡，返回調(diào)整后新樹根};北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page85template<classT>classavlTree//平衡二叉樹類{ public: avlTree();//構(gòu)造函數(shù)

avlTree(constavlTree<T>&source); ~avlTree();//析構(gòu)函數(shù)

voidadd(Tvalue); voidremove(Tvalue); voiddeleteAllValue(); voiddisplay(); voiddisplay(avlNode<T>*found); avlNode<T>*findValue(Tval); private: avlNode<T>*root;};北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page86插入算法template<classT>intavlNode<T>::add(avlNode<T>*&rp,Tval){//返回值表明以當(dāng)前結(jié)點(diǎn)為根的樹是否再插入之后增高

if(val<value) {//左子樹插入

if(rp->leftptr==NULL) rp->leftptr=newavlNode<T>(val); elseif(rp->leftptr->add(rp->leftptr,val)==0) return0;//插入后子樹沒有增高

if(rp->bf==-1) {//原來(lái)已經(jīng)傾斜，左邊失衡，需要做平衡處理

if(rp->leftptr->bf<0)//插入在左側(cè)，單旋轉(zhuǎn)

rp=LL_singleRotation(); elserp=LR_doubleRotation(); //插入在右側(cè)，雙旋轉(zhuǎn)

return0; }

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page87return--bf;//bf=(0,+1)的情況，不需要調(diào)整樹，只要修改bf } else { if(rp->rightptr==NULL) rp->right=newavlNode<T>(val); elseif(rp->rightptr->add(rp->rightptr,val)==0) return0;//插入后子樹沒有增高

if(rp->bf==1) {//原來(lái)已經(jīng)傾斜，需要做平衡處理

if(rp->rightptr->bf>0)//插入在右側(cè)，單旋轉(zhuǎn)

rp=RR_singleRotation(); elserp=RL_doubleRotation();//插入點(diǎn)在右側(cè).雙旋轉(zhuǎn)

return0; } return++bf;//bf=(0,-1)的情況，不需要調(diào)整樹，只要修改bf }}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page88旋轉(zhuǎn)的算法(LL)template<classT>avlNode<T>*avlNode<T>::LL_singleRotation(){//以當(dāng)前結(jié)點(diǎn)this(a)進(jìn)行LL單旋轉(zhuǎn)

avlNode<T>*b; b=leftptr;//得到當(dāng)前結(jié)點(diǎn)this(a)的左子樹

leftptr=p->rightptr;//當(dāng)前結(jié)點(diǎn)的左子樹變?yōu)樵訕涞挠易訕?/p>

bf=0; b->rightptr=this;//原子結(jié)點(diǎn)成為當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)

if(b->bf==0)//如果是刪除導(dǎo)致的旋轉(zhuǎn)，則需要調(diào)整bf b->bf=1; elseb->bf=0; returnb;//返回新的子樹根結(jié)點(diǎn)}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page89旋轉(zhuǎn)的算法(RR)template<classT>avlNode<T>*avlNode<T>::RR_singleRotation(){//以當(dāng)前結(jié)點(diǎn)this(a)進(jìn)行RR單旋轉(zhuǎn)

avlNode<T>*b; b=rightptr;//得到當(dāng)前結(jié)點(diǎn)右兒子

rightptr=b->leftptr;//當(dāng)前結(jié)點(diǎn)的右兒子變?yōu)樵溆覂鹤拥淖笞优?/p>

bf=0; b->leftptr=this;//原其右兒子變?yōu)楫?dāng)前結(jié)點(diǎn)的父親

if(b->bf==0)//如果是刪除導(dǎo)致的旋轉(zhuǎn)，則需要調(diào)整bf b->bf=-1; elseb->bf=0;returnb;}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page90旋轉(zhuǎn)的算法(RL)template<classT>avlNode<T>*avlNode<T>::RL_doubleRotation(){//以當(dāng)前結(jié)點(diǎn)this(圖11-24(d)中為a)進(jìn)行LL單旋轉(zhuǎn)

avlNode<T>*c,*b; b=rightptr; c=b->leftptr; b->leftptr=c->rightptr;//第一次旋轉(zhuǎn)c,b位置互換，c的右子樹變?yōu)閎的左子樹

c->rightptr=b;bf=b->bf=0; if(c->bf==-1)b->bf=1;//因?yàn)閏的右子樹變?yōu)閎的左子樹

if(c->bf==1)bf=-1;//所以根據(jù)原來(lái)的高度可以知道現(xiàn)在的平衡因子

rightptr=c->leftptr;//第二次旋轉(zhuǎn)c和當(dāng)前結(jié)點(diǎn)a互換

c->leftptr=this;c->bf=0;//旋轉(zhuǎn)完c平衡

returnc;}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page91旋轉(zhuǎn)的算法(LR)template<classT>avlNode<T>*avlNode<T>::LR_doubleRotation(){//以當(dāng)前結(jié)點(diǎn)this(a)進(jìn)行LR雙旋轉(zhuǎn)

avlNode<T>*c,*b; b=leftptr; c=b->rightptr; b->rightptr=c->leftptr;//第一次旋轉(zhuǎn)b,c位置互換，c的左子樹變?yōu)閎的右子樹

c->leftptr=b; bf=b->bf=0; if(c->bf==-1)bf=1;//根據(jù)原來(lái)c的左子樹的高度來(lái)判斷當(dāng)前

if(c->bf==1)b->bf=-1;//b的平衡情況

leftptr=c->rightptr;//第二次旋轉(zhuǎn)c和當(dāng)前結(jié)點(diǎn)互換

c->rightptr=this; c->bf=0; returnc;}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page92插入單詞：cup，cop，

copy，

hit，

hi，

his和

hia后得到的AVL樹北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page93插入單詞：cup，cop，

copy，

hit，

hi，

his和

hia后得到的AVL樹北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page94

AVL樹結(jié)點(diǎn)的刪除

刪除是插入的逆操作。從刪除結(jié)點(diǎn)的意義上來(lái)說，AVL樹的刪除操作與BST一樣

AVL樹的刪除是比較復(fù)雜過程，下面具體討論一下刪除的過程

由于情況較多，所以圖示每種情況只列舉了一種例子，其他都是類似的北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page95AVL樹結(jié)點(diǎn)的刪除具體刪除過程請(qǐng)參考BST結(jié)點(diǎn)的刪除如果被刪除結(jié)點(diǎn)a沒有子結(jié)點(diǎn)直接刪除a；如果a有一個(gè)子結(jié)點(diǎn)用子結(jié)點(diǎn)的內(nèi)容代替a的內(nèi)容，然后刪除子結(jié)點(diǎn)；如果a有兩個(gè)子結(jié)點(diǎn)那么則要找到a在中序周游下的前驅(qū)結(jié)點(diǎn)b（b的右子樹必定為空）用b的內(nèi)容代替a，并且刪除結(jié)點(diǎn)b（如果b的左子樹不空，則該左子樹代替代替原來(lái)b的位置）。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page96AVL結(jié)點(diǎn)刪除后的調(diào)整AVL樹調(diào)整的需要?jiǎng)h除結(jié)點(diǎn)后可能導(dǎo)致子樹的高度以及平衡因子的變化沿著被刪除結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑來(lái)調(diào)整這種變化需要改動(dòng)平衡因子則修改之；如果發(fā)現(xiàn)不需要修改則不必繼續(xù)向上回溯用一個(gè)布爾變量modified來(lái)記錄之，其初值為TRUE當(dāng)modified=FALSE時(shí)，回溯停止有以下三種情況

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page97AVL樹結(jié)點(diǎn)的刪除過程2(續(xù))第一種情況當(dāng)前結(jié)點(diǎn)a平衡因子為0如果它的左子樹或者右子樹被縮短，則它的平衡因子該為1或者-1modified=FALSE因?yàn)檫@樣的變化不會(huì)影響到上面的結(jié)點(diǎn)，調(diào)整可以結(jié)束北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page98AVL樹結(jié)點(diǎn)的刪除情況1圖示北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page99AVL樹結(jié)點(diǎn)的刪除過程2(續(xù))第二種情況是當(dāng)前結(jié)點(diǎn)a平衡因子不為0，但是其較高的子樹被縮短則其平衡因子修改為0modified=TRUE需要繼續(xù)向上修改北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page100AVL樹結(jié)點(diǎn)的刪除情況2圖示北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page101

AVL樹結(jié)點(diǎn)的刪除過程2(續(xù))第三種情況是當(dāng)前結(jié)點(diǎn)a平衡因子不為0，且它的較低的子樹被縮短結(jié)點(diǎn)a必然不再平衡，假設(shè)其較高子樹的根結(jié)點(diǎn)為b，出現(xiàn)下面三種情況情況3.1：b的平衡因子為0單旋轉(zhuǎn)modified=FALSE情況3.2：b的平衡因子與a的平衡因子相同單旋轉(zhuǎn)結(jié)點(diǎn)a、b平衡因子都變?yōu)?modified=TRUE北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page102情況3.3：b和a的平衡因子相反雙旋轉(zhuǎn)，先圍繞b旋轉(zhuǎn)，再圍繞a旋轉(zhuǎn)新的根結(jié)點(diǎn)平衡因?yàn)闉?其他結(jié)點(diǎn)應(yīng)做相應(yīng)的處理并且modified=TRUE北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page103AVL樹結(jié)點(diǎn)的刪除情況3圖示北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page104AVL樹結(jié)點(diǎn)的刪除情況3圖示北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page105刪除后的連續(xù)調(diào)整從被刪除的結(jié)點(diǎn)向上查找到其祖父結(jié)點(diǎn)然后開始單旋轉(zhuǎn)或者雙旋轉(zhuǎn)操作

旋轉(zhuǎn)次數(shù)為O(logn)連續(xù)調(diào)整調(diào)整可能會(huì)導(dǎo)致它祖先結(jié)點(diǎn)發(fā)生新的不平衡這樣的調(diào)整操作要一直進(jìn)行下去，可能傳遞到根結(jié)點(diǎn)為止

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page106AVL樹刪除的例子北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page107AVL樹刪除的例子北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page108AVL樹刪除的例子北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page109AVL樹的高度具有n個(gè)結(jié)點(diǎn)的AVL樹的高度一定是O(logn)n個(gè)結(jié)點(diǎn)的AVL樹的最大高度不超過Klog2

n這里K是一個(gè)小的常數(shù)

最接近于不平衡的AVL樹

構(gòu)造一系列AVL樹T1，T2，T3，…。其中Ti的高度是i每棵具有高度i的其它AVL樹都比Ti的結(jié)點(diǎn)個(gè)數(shù)多或者說，每棵這樣的樹都是具有同樣的結(jié)點(diǎn)數(shù)目的所有AVL樹中最接近不平衡狀態(tài)的，刪除一個(gè)結(jié)點(diǎn)都會(huì)不平衡北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page110北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page111高度的證明（推理）可看出有下列關(guān)系成立：t(1)=2t(2)=4t(i)=t(i-1)+t(i-2)+1對(duì)于i>2此關(guān)系很類似于定義Fibonacci數(shù)的那些關(guān)系：F(0)=0F(1)=1F(i)=F(i-1)+F(i-2)北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page112高度的證明（推理續(xù)）對(duì)于i>l僅檢查序列的前幾項(xiàng)就可有t(i)=F(i+3)-1Fibonacci數(shù)滿足漸近公式由此可得近似公式北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page113高度的證明（結(jié)果）解出高度i與結(jié)點(diǎn)個(gè)數(shù)t(i)的關(guān)系由換底公式logφX=log2X/log2φ和log2φ≈0.694我們求出近似上限t(i)=n所以n個(gè)結(jié)點(diǎn)的AVL樹的高度一定是O(logn)北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page114AVL樹的效率

AVL樹的檢索、插入和刪除效率都是O(1og2

n)，這是因?yàn)榫哂衝個(gè)結(jié)點(diǎn)的AVL樹的高度一定是O(logn)

AVL樹適用于組織較小的、內(nèi)存中的目錄。而對(duì)于較大的、存放在外存儲(chǔ)器上的文件，用二叉搜索樹來(lái)組織索引就不合適了

在文件索引中大量使用每個(gè)結(jié)點(diǎn)包括多個(gè)關(guān)鍵碼的B-樹，尤其是B+樹

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page11512.2.3伸展樹

伸展樹不是一個(gè)新數(shù)據(jù)結(jié)構(gòu)，而只是改進(jìn)BST性能的一組規(guī)則保證訪問的總代價(jià)不高，達(dá)到最令人滿意的性能不能保證最終樹高平衡北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page116展開(splaying)

每當(dāng)訪問一個(gè)結(jié)點(diǎn)x時(shí)(例如，當(dāng)x被插入、刪除或者是檢索目標(biāo)時(shí))，伸展樹就完成一次稱為展開(splaying)的過程

展開處理把結(jié)點(diǎn)x移到BST的根結(jié)點(diǎn)當(dāng)刪除結(jié)點(diǎn)x時(shí)，展開過程把結(jié)點(diǎn)x的父結(jié)點(diǎn)移到根結(jié)點(diǎn)

像在AVL樹中一樣，結(jié)點(diǎn)x的一次展開包括一組旋轉(zhuǎn)(rotation)一次旋轉(zhuǎn)通過調(diào)整結(jié)點(diǎn)x相對(duì)于其父結(jié)點(diǎn)和祖父結(jié)點(diǎn)的位置，把它移到樹結(jié)構(gòu)中的更高層

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page117單旋轉(zhuǎn)(singlerotation)

當(dāng)被訪問結(jié)點(diǎn)是根結(jié)點(diǎn)的子女時(shí)，完成單旋轉(zhuǎn),它基本上在保持BST特性的情況下把結(jié)點(diǎn)x與它的父結(jié)點(diǎn)交換位置

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page118雙旋轉(zhuǎn)(doublerotation)

雙旋轉(zhuǎn)涉及到結(jié)點(diǎn)x結(jié)點(diǎn)x的父結(jié)點(diǎn)(稱為y)結(jié)點(diǎn)x的祖父結(jié)點(diǎn)(稱為z)雙旋轉(zhuǎn)的結(jié)果是把結(jié)點(diǎn)x在樹結(jié)構(gòu)中向上移兩層北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page119

雙旋轉(zhuǎn)分為兩類一字形旋轉(zhuǎn)(zigzigrotation)也稱為同構(gòu)調(diào)整（homogeneousconfiguration）；之字形旋轉(zhuǎn)(zigzagrotation)也稱為異構(gòu)調(diào)整（heterogeneousconfiguration）

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page120一字形旋轉(zhuǎn)

當(dāng)出現(xiàn)以下兩種情況之一時(shí)，就會(huì)發(fā)生一字形旋轉(zhuǎn)：1.結(jié)點(diǎn)x是結(jié)點(diǎn)y的左子女，結(jié)點(diǎn)y是結(jié)點(diǎn)z的左子女。2.結(jié)點(diǎn)x是結(jié)點(diǎn)y的右子女，結(jié)點(diǎn)y是結(jié)點(diǎn)z的右子女。

北京大學(xué)信息學(xué)院