CHAP9查找[修復(fù)的]

1、121. 查找表和查找查找表和查找（1）查找表）查找表是由是由同一類(lèi)型同一類(lèi)型的數(shù)據(jù)的數(shù)據(jù)元素元素(或記錄或記錄)構(gòu)成的構(gòu)成的集合集合。 由于由于“集合集合”中的數(shù)據(jù)元素之間中的數(shù)據(jù)元素之間存在著松散的關(guān)系，因此查找表是存在著松散的關(guān)系，因此查找表是一種應(yīng)用靈便的結(jié)構(gòu)。一種應(yīng)用靈便的結(jié)構(gòu)。查找的基本概念查找的基本概念 3關(guān)鍵字：關(guān)鍵字：是數(shù)據(jù)元素（或記錄）中某是數(shù)據(jù)元素（或記錄）中某個(gè)個(gè)數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)的值，用以的值，用以標(biāo)識(shí)標(biāo)識(shí)（識(shí)別）一（識(shí)別）一個(gè)數(shù)據(jù)元素（或記錄）。個(gè)數(shù)據(jù)元素（或記錄）。（2）關(guān)鍵字）關(guān)鍵字 若此關(guān)鍵字可以識(shí)別若此關(guān)鍵字可以識(shí)別唯一的唯一的一個(gè)記一個(gè)記錄，則稱(chēng)之為錄，則稱(chēng)之為

2、“主關(guān)鍵字主關(guān)鍵字”。4 根據(jù)給定的某個(gè)值，在查找表中根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)確定一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素或其關(guān)鍵字等于給定值的數(shù)據(jù)元素或(記錄記錄).（3）查找）查找 若查找表中存在這樣一個(gè)記錄，則稱(chēng)若查找表中存在這樣一個(gè)記錄，則稱(chēng)“查找成功查找成功”，查找結(jié)果：，查找結(jié)果：給出整個(gè)記錄給出整個(gè)記錄的信息，或指示該記錄在查找表中的位置的信息，或指示該記錄在查找表中的位置； 否則稱(chēng)否則稱(chēng)“查找不成功查找不成功”，查找結(jié)果：，查找結(jié)果：給給出出“空記錄空記錄”或或“空指針空指針”。5 由于查找表中的數(shù)據(jù)元素之間不存在明由于查找表中的數(shù)據(jù)元素之間不存在明顯的組織規(guī)律，因此不便于

3、查找。顯的組織規(guī)律，因此不便于查找。 為了提高查找的效率，需要在查找表中為了提高查找的效率，需要在查找表中的元素之間人為地的元素之間人為地 附加某種確定的關(guān)系，附加某種確定的關(guān)系，換句話(huà)說(shuō)，換句話(huà)說(shuō)，用另外一種結(jié)構(gòu)來(lái)表示查找表用另外一種結(jié)構(gòu)來(lái)表示查找表。（4）如何進(jìn)行查找）如何進(jìn)行查找查找的方法取決于查找表的結(jié)構(gòu)。查找的方法取決于查找表的結(jié)構(gòu)。6（5）查找的操作）查找的操作1）查詢(xún)查詢(xún)某個(gè)某個(gè)“特定的特定的”數(shù)據(jù)元素是否數(shù)據(jù)元素是否在查找表中；在查找表中；2）檢索檢索某個(gè)某個(gè)“特定的特定的”數(shù)據(jù)元素的各數(shù)據(jù)元素的各種屬性；種屬性；3）在查找表中）在查找表中插入插入一個(gè)數(shù)據(jù)元素；一個(gè)數(shù)據(jù)元素；4

4、）從查找表中）從查找表中刪去刪去某個(gè)數(shù)據(jù)元素。某個(gè)數(shù)據(jù)元素。7僅作僅作查詢(xún)查詢(xún)和和檢索檢索操作的查找表。操作的查找表。靜態(tài)靜態(tài)查找查找有時(shí)在查詢(xún)之后，還需要將有時(shí)在查詢(xún)之后，還需要將“查詢(xún)查詢(xún)”結(jié)結(jié)果為果為“不在查找表中不在查找表中”的數(shù)據(jù)元素的數(shù)據(jù)元素插入插入到到查找表中；或者，從查找表中查找表中；或者，從查找表中刪除刪除其其“查詢(xún)查詢(xún)”結(jié)果為結(jié)果為“在查找表中在查找表中”的數(shù)據(jù)的數(shù)據(jù)元素。元素。動(dòng)態(tài)動(dòng)態(tài)查找查找2.2.查找的查找的類(lèi)型類(lèi)型8 定義：定義：(Average Search Length) 3.3.平均查找長(zhǎng)度平均查找長(zhǎng)度niiiCPASL1iP為查找第i個(gè)記錄的概率iC查找到第

5、i個(gè)記錄時(shí)，已比較的次數(shù)99.1 靜態(tài)靜態(tài)查找查找9.2 動(dòng)態(tài)動(dòng)態(tài)查找查找9.3 哈哈希查找希查找109.1 靜靜 態(tài)態(tài) 查查 找找 11typedef struct ElemType *elem; int length; / 表的長(zhǎng)度表的長(zhǎng)度 SSTable;假設(shè)靜態(tài)查找表靜態(tài)查找表的順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)元素類(lèi)型的定義為數(shù)據(jù)元素類(lèi)型的定義為: :typedef struct keyType key; / 關(guān)鍵字域關(guān)鍵字域 / 其它屬性域其它屬性域 ElemType , TElemType ;129.1.1 順序順序查找查找9.1.2 有序有序查找查找9.1.3 索引索引順序順序13

6、 以線(xiàn)性表的順序存儲(chǔ)以線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)表示靜態(tài)查找表。結(jié)構(gòu)表示靜態(tài)查找表。鏈表與之類(lèi)似。鏈表與之類(lèi)似。9.1.1 順序順序查找查找141. 順序查找的基本思想順序查找的基本思想 從表的一端開(kāi)始，從表的一端開(kāi)始，順序掃描線(xiàn)性順序掃描線(xiàn)性表，依次將掃描到的結(jié)點(diǎn)關(guān)鍵宇和給表，依次將掃描到的結(jié)點(diǎn)關(guān)鍵宇和給定值定值K相比較。相比較。若當(dāng)前掃描到的結(jié)點(diǎn)若當(dāng)前掃描到的結(jié)點(diǎn)關(guān)鍵字與關(guān)鍵字與K相等，則查找成功；若掃相等，則查找成功；若掃描結(jié)束后，仍未找到關(guān)鍵字等于描結(jié)束后，仍未找到關(guān)鍵字等于K的的結(jié)點(diǎn)，則查找失敗。結(jié)點(diǎn)，則查找失敗。1521 37 88 19 92 05 64 56 80 75 13 0 1

7、 2 3 4 5 6 7 8 9 10 11 ST.LengthST.elem例如：例如：假設(shè)給定值假設(shè)給定值 e=64,要求要求 ST.elemk = e, 問(wèn)問(wèn): k = ?kk16int location( SqList L, ElemType& e, Status (*compare)(ElemType, ElemType) k = 1; p = L.elem; while ( k=L.length & !(*compare)(*p+,e) k+; if ( k=1;i-) for(i=ST.length;i=1;i-) if ( ST.elemi.key=keyST.

8、elemi.key=key) return i; return 0; 2.經(jīng)典順序查找算法經(jīng)典順序查找算法1821 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 ST.LengthST.elemi21 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 ST.LengthST.elemi60ikey=64key=60i64改進(jìn)改進(jìn)(加哨兵加哨兵)19int Search_Seq(SSTable ST, KeyType key) / 在順序表ST中順序查找其關(guān)鍵字等于 /

9、 key的數(shù)據(jù)元素。若找到，則函數(shù)值為 / 該元素在表中的位置，否則為0。 ST.elem0.key = key; / “哨兵” for (i=ST.length; ST.elemi.key!=key; -i); / 從后往前找 return i; / 找不到時(shí)，i為0 / Search_Seq,不需要每次和長(zhǎng)度比較不需要每次和長(zhǎng)度比較3.改進(jìn)順序查找算法改進(jìn)順序查找算法20在在等概率等概率查找的情況下，查找的情況下， 順序表查找的平均查找長(zhǎng)度順序表查找的平均查找長(zhǎng)度為：為：對(duì)對(duì)順序表順序表而言，而言，Ci = n-i+1(i=1n)nPi121111n)i(nnASLnissASL = nP

10、1 +(n-1)P2 + +2Pn-1+Pn4.算法分析算法分析niiiCPASL121 若查找概率無(wú)法事先測(cè)定，則查若查找概率無(wú)法事先測(cè)定，則查找過(guò)程采取的改進(jìn)辦法是，找過(guò)程采取的改進(jìn)辦法是，在每次查找在每次查找之后，將剛剛查找到的記錄直接移至表之后，將剛剛查找到的記錄直接移至表尾的位置上。尾的位置上。在在不等概率查找不等概率查找的情況下的情況下，ASLss 在在 PnPn-1P2P1時(shí)時(shí)取極小值。取極小值。22（1 1）優(yōu)點(diǎn)）優(yōu)點(diǎn) 算法簡(jiǎn)單，算法簡(jiǎn)單，且對(duì)表的結(jié)構(gòu)無(wú)任何且對(duì)表的結(jié)構(gòu)無(wú)任何要求，無(wú)論是用順序還是用鏈表來(lái)存放要求，無(wú)論是用順序還是用鏈表來(lái)存放結(jié)點(diǎn)，也無(wú)論結(jié)點(diǎn)之間是否按關(guān)鍵字有結(jié)

11、點(diǎn)，也無(wú)論結(jié)點(diǎn)之間是否按關(guān)鍵字有序，它都同樣適用。序，它都同樣適用。（2 2）缺點(diǎn)）缺點(diǎn)查找效率低，查找效率低，因此，當(dāng)因此，當(dāng)n n較大時(shí)不較大時(shí)不宜采用順序查找。宜采用順序查找。5.順序查找的優(yōu)缺點(diǎn)順序查找的優(yōu)缺點(diǎn)23 二分查找要求：二分查找要求：線(xiàn)性表是有序表，線(xiàn)性表是有序表，即表中結(jié)點(diǎn)按關(guān)鍵字有序，并且要用即表中結(jié)點(diǎn)按關(guān)鍵字有序，并且要用順序存儲(chǔ)結(jié)構(gòu)。順序存儲(chǔ)結(jié)構(gòu)。9.1.2 有序有序查找查找 若以若以有序表有序表表示靜態(tài)查找表，則查表示靜態(tài)查找表，則查找過(guò)程可以基于找過(guò)程可以基于“折半折半”進(jìn)行。稱(chēng)為進(jìn)行。稱(chēng)為二分查找或折半查找。二分查找或折半查找。241.二分查找的基本思想二分查找

12、的基本思想設(shè)設(shè)Rlow.highRlow.high是當(dāng)前的查找區(qū)間是當(dāng)前的查找區(qū)間 （1 1）首先確定該區(qū)間的中點(diǎn)位置；）首先確定該區(qū)間的中點(diǎn)位置；mid=(low+high)/2mid=(low+high)/2 （2 2）然后將待查的）然后將待查的K K值與值與Rmid.keyRmid.key比較：比較：若相等，則查找成功并返回此位置，否則若相等，則查找成功并返回此位置，否則須確定新的查找區(qū)間，繼續(xù)二分查找。須確定新的查找區(qū)間，繼續(xù)二分查找。 25若若Rmid.keyKRmid.keyK，則由表的有序性可知?jiǎng)t由表的有序性可知Rmid.n.keysRmid.n.keys均大于均大于K K，因此

13、若表中存在關(guān)鍵，因此若表中存在關(guān)鍵字等于字等于K K的結(jié)點(diǎn)，的結(jié)點(diǎn)，則該結(jié)點(diǎn)必定是在位置則該結(jié)點(diǎn)必定是在位置midmid左左邊的子表邊的子表R1.mid-1R1.mid-1中中，故新的查找區(qū)間是左，故新的查找區(qū)間是左子表子表R1.mid-1R1.mid-1。類(lèi)似地，類(lèi)似地，若若Rmid.keyKRmid.keyK，則要查找的則要查找的K K必在必在midmid的右子表的右子表Rmid+1.nRmid+1.n中，中，即新的查找區(qū)間即新的查找區(qū)間是右子表是右子表Rmid+1.nRmid+1.n。下一次查找是針對(duì)新的。下一次查找是針對(duì)新的查找區(qū)間進(jìn)行的。查找區(qū)間進(jìn)行的。二分查找的基本思想二分查找的基

14、本思想2605 13 19 21 37 56 64 75 80 88 92 0 1 2 3 4 5 6 7 8 9 10 11 ST.elemST.length例如例如: key=64 的查找過(guò)程如下lowhighmidlow mid high midlow 指示查找區(qū)間的下界指示查找區(qū)間的下界; ;high 指示查找區(qū)間的上界指示查找區(qū)間的上界; ;mid = (low+high)/2。27int Search_Bin ( SSTable ST, KeyType key ) low = 1; high = ST.length; / 置區(qū)間初值 while (low = high) mid =

15、 (low + high) / 2; if （EQ (key , ST.elemmid.key) ) return mid; / 找到待查元素 else if ( LT (key , ST.elemmid.key) ) high = mid - 1; / 繼續(xù)在前半?yún)^(qū)間進(jìn)行查找 else low = mid + 1; /繼續(xù)在后半?yún)^(qū)間進(jìn)行查找return 0; / 順序表中不存在待查元素 / Search_Bin2.二分查找的算法二分查找的算法28先看一個(gè)具體的情況，假設(shè)：先看一個(gè)具體的情況，假設(shè)：n=113.二分查找判定樹(shù)二分查找判定樹(shù)63914-11-22-33-44-55-66-77-8

16、8-99-1010-1111-25781011i123456789 10 11Ci1223333444429（1 1）二分查找判定樹(shù)的組成及其查找）二分查找判定樹(shù)的組成及其查找圓結(jié)點(diǎn)即樹(shù)中的內(nèi)部結(jié)點(diǎn)。圓結(jié)點(diǎn)即樹(shù)中的內(nèi)部結(jié)點(diǎn)。樹(shù)中圓結(jié)點(diǎn)內(nèi)的數(shù)樹(shù)中圓結(jié)點(diǎn)內(nèi)的數(shù)字表示該結(jié)點(diǎn)在有序表中的位置。字表示該結(jié)點(diǎn)在有序表中的位置。外部結(jié)點(diǎn)：圓結(jié)點(diǎn)中的所有空指針均用一個(gè)虛外部結(jié)點(diǎn)：圓結(jié)點(diǎn)中的所有空指針均用一個(gè)虛擬的方形結(jié)點(diǎn)來(lái)取代，即外部結(jié)點(diǎn)。擬的方形結(jié)點(diǎn)來(lái)取代，即外部結(jié)點(diǎn)。樹(shù)中某結(jié)點(diǎn)樹(shù)中某結(jié)點(diǎn)i i與其左與其左( (右右) )孩子連接的左孩子連接的左( (右右) )分分支上的標(biāo)記支上的標(biāo)記“ ”表示：表示：當(dāng)待

17、查關(guān)鍵字當(dāng)待查關(guān)鍵字KRi.keyKRi.key ）時(shí)，應(yīng)走左）時(shí)，應(yīng)走左( (右右) )分支到達(dá)分支到達(dá)i i的左的左( (右右) )孩子，將該孩子的關(guān)鍵字進(jìn)一步和孩子，將該孩子的關(guān)鍵字進(jìn)一步和K K比較。比較。若相等，則查找過(guò)程結(jié)束返回，否則繼續(xù)將若相等，則查找過(guò)程結(jié)束返回，否則繼續(xù)將K K與樹(shù)中與樹(shù)中更下一層的結(jié)點(diǎn)比較。更下一層的結(jié)點(diǎn)比較。3063914-11-22-33-44-55-66-77-88-99-1010-1111-25781011所經(jīng)過(guò)的內(nèi)部結(jié)點(diǎn)為所經(jīng)過(guò)的內(nèi)部結(jié)點(diǎn)為6 6、9 9、1010，最后到達(dá)方形結(jié)，最后到達(dá)方形結(jié)點(diǎn)點(diǎn)9-109-10，其比較次數(shù)為，其比較次數(shù)為3 3

18、。例如：查找例如：查找k85，31假設(shè)假設(shè) n=2h-1 并且查找概率相等并且查找概率相等則則 在在n50時(shí)，可得近似結(jié)果時(shí)，可得近似結(jié)果 （2）二分查找的平均查找長(zhǎng)度）二分查找的平均查找長(zhǎng)度 一般情況下，表長(zhǎng)為一般情況下，表長(zhǎng)為 n 的折半查找的的折半查找的判定樹(shù)的深度和含有判定樹(shù)的深度和含有 n 個(gè)結(jié)點(diǎn)的完全二叉?zhèn)€結(jié)點(diǎn)的完全二叉樹(shù)的深度樹(shù)的深度h相同。相同。1) 1(log12112111nnnjnCnASLhjjniibs1) 1(log2nASLbs324.二分查找的優(yōu)點(diǎn)和缺點(diǎn)二分查找的優(yōu)點(diǎn)和缺點(diǎn)雖然雖然二分查找的效率高二分查找的效率高，但是要將表按關(guān)但是要將表按關(guān)鍵字排序。鍵字排序。

19、而排序本身是一種很費(fèi)時(shí)的運(yùn)算。而排序本身是一種很費(fèi)時(shí)的運(yùn)算。既使采用高效率的排序方法也要花費(fèi)既使采用高效率的排序方法也要花費(fèi)O(nlgn)的的時(shí)間。時(shí)間。二分查找只適用順序存儲(chǔ)結(jié)構(gòu)。二分查找只適用順序存儲(chǔ)結(jié)構(gòu)。為保持表為保持表的有序性，在順序結(jié)構(gòu)里插入和刪除都必須移的有序性，在順序結(jié)構(gòu)里插入和刪除都必須移動(dòng)大量的結(jié)點(diǎn)。因此，動(dòng)大量的結(jié)點(diǎn)。因此，二分查找特別適用于那二分查找特別適用于那種一經(jīng)建立就很少改動(dòng)、而又經(jīng)常需要查找的種一經(jīng)建立就很少改動(dòng)、而又經(jīng)常需要查找的線(xiàn)性表。線(xiàn)性表。339.1.3索引查找索引查找(分塊查找分塊查找)1.分塊分塊查找查找分塊有序的線(xiàn)性表分塊有序的線(xiàn)性表+索引表索引表兩

20、部分組成。兩部分組成。012345678910 11 12 1317 08 21 19 14 31 33 22 25 40 52 61 78 4621 040 578 10順序表順序表索引表索引表索引順序表的特點(diǎn)：索引順序表的特點(diǎn)：塊內(nèi)無(wú)序塊內(nèi)無(wú)序，塊間有序。塊間有序。342.索引查找的思想索引查找的思想（1）由索引確定記錄所在區(qū)間）由索引確定記錄所在區(qū)間索引表是有序表，可采用索引表是有序表，可采用二分查找二分查找或或順序查找順序查找，以確定待查的結(jié)點(diǎn)在哪一，以確定待查的結(jié)點(diǎn)在哪一塊。塊。（2）在確定的區(qū)間內(nèi)進(jìn)行查找）在確定的區(qū)間內(nèi)進(jìn)行查找由于塊內(nèi)無(wú)序，只能用順序查找。由于塊內(nèi)無(wú)序，只能用順序

21、查找。 351 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1822 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 5322 48 861 7 13索引表索引表查查38例如：例如：查查7036索引順序查找的平均查找長(zhǎng)度索引順序查找的平均查找長(zhǎng)度 = 查找查找“索引索引”的平均查找長(zhǎng)度的平均查找長(zhǎng)度 + 查找查找“順序表順序表”的平均查找長(zhǎng)度的平均查找長(zhǎng)度3.3.算法分析算法分析37ASLbs =Lb+Lw 其中：其中：Lb索引查找長(zhǎng)度，索引查找長(zhǎng)度，Lw塊中查找長(zhǎng)度，塊中查找長(zhǎng)度，每塊含每塊含s個(gè)記錄，個(gè)記錄，B

22、=n/s 1s)sn(2121s21bjs1jb1ASLs1ib1jbs2) 1(log2ssnASLbs（2）用折半查找確定所在的塊）用折半查找確定所在的塊（1）用順序查找確定所在的塊）用順序查找確定所在的塊38【例例】若表中有若表中有1000010000個(gè)結(jié)點(diǎn)，則應(yīng)把它分成個(gè)結(jié)點(diǎn)，則應(yīng)把它分成100100個(gè)塊，每塊中含個(gè)塊，每塊中含100100個(gè)結(jié)點(diǎn)。分別計(jì)算順序個(gè)結(jié)點(diǎn)。分別計(jì)算順序查找、二分查找和索引查找的平均查找長(zhǎng)度。查找、二分查找和索引查找的平均查找長(zhǎng)度。（2）二分查找）二分查找（1）順序查找）順序查找ASL=(n+1)/2=5001ASL=log2(n+1)-1=14（3）索引查找

23、）索引查找ASL2=log2(n/s+1)+s/2=57ASL1=(n/s+s)/2+1=10139查找方法比較查找方法比較ASL最大最大最小最小兩者之間兩者之間表結(jié)構(gòu)表結(jié)構(gòu)有序表有序表.無(wú)序表無(wú)序表 有序表有序表分塊有序表分塊有序表存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)順序結(jié)構(gòu)順序結(jié)構(gòu)線(xiàn)性鏈表線(xiàn)性鏈表順序結(jié)構(gòu)順序結(jié)構(gòu)順序結(jié)構(gòu)順序結(jié)構(gòu)線(xiàn)性鏈表線(xiàn)性鏈表順序查找順序查找折半查找折半查找 分塊查找分塊查找409.2 動(dòng)動(dòng) 態(tài)態(tài) 查查 找找 419.2.1 二叉排序樹(shù)（二叉查找樹(shù)）二叉排序樹(shù)（二叉查找樹(shù)）9.2.2 平衡二叉樹(shù)平衡二叉樹(shù)429.2.1 二叉排序樹(shù)二叉排序樹(shù)（二叉查找樹(shù)）（二叉查找樹(shù)）1定義定義4查找算法查找

24、算法5插入算法插入算法6刪除算法刪除算法7查找性能的分析查找性能的分析2特點(diǎn)特點(diǎn)3存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)43（1）若它的左子樹(shù)不空，則）若它的左子樹(shù)不空，則左子樹(shù)上左子樹(shù)上 所有所有結(jié)點(diǎn)的值結(jié)點(diǎn)的值均小于均小于根結(jié)點(diǎn)的值；根結(jié)點(diǎn)的值；1 1定義定義 二叉排序樹(shù)二叉排序樹(shù)或者是一棵空樹(shù)；或者或者是一棵空樹(shù)；或者是具有如下特性的二叉樹(shù)：是具有如下特性的二叉樹(shù)：（3）它的左、右子樹(shù)）它的左、右子樹(shù)也都也都分別分別是二叉是二叉 排序樹(shù)排序樹(shù)。（2）若它的右子樹(shù)不空，則）若它的右子樹(shù)不空，則右子樹(shù)上右子樹(shù)上 所有所有結(jié)點(diǎn)的值結(jié)點(diǎn)的值均大于均大于根結(jié)點(diǎn)的值；根結(jié)點(diǎn)的值；445030802090108540352

25、52388例如例如:是二叉排序樹(shù)。是二叉排序樹(shù)。66不不452 2、二叉排序樹(shù)的特點(diǎn)、二叉排序樹(shù)的特點(diǎn)（1 1） 二叉排序樹(shù)中任一結(jié)點(diǎn)二叉排序樹(shù)中任一結(jié)點(diǎn)x x，其左，其左( (右右) )子樹(shù)子樹(shù)中任一結(jié)點(diǎn)中任一結(jié)點(diǎn)y(y(若存在若存在) )的關(guān)鍵字必小的關(guān)鍵字必小( (大大) )于于x x的關(guān)的關(guān)鍵字。鍵字。（2 2） 二叉排序樹(shù)中，各結(jié)點(diǎn)關(guān)鍵字是惟一的。二叉排序樹(shù)中，各結(jié)點(diǎn)關(guān)鍵字是惟一的。（3 3） 按中序遍歷該樹(shù)所得到的按中序遍歷該樹(shù)所得到的中序序列是一個(gè)中序序列是一個(gè)遞增有序序列遞增有序序列。503080209010854035252388463.3.二叉排序樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉排序樹(shù)的存

26、儲(chǔ)結(jié)構(gòu)typedef struct BiTNode / 結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu) TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指針 BiTNode, *BiTree;474二叉排序樹(shù)的查找算法二叉排序樹(shù)的查找算法1）若給定值）若給定值等于等于根結(jié)點(diǎn)的關(guān)鍵字，則查根結(jié)點(diǎn)的關(guān)鍵字，則查找成功；找成功；2）若給定值）若給定值小于小于根結(jié)點(diǎn)的關(guān)鍵字，則繼根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在左子樹(shù)上進(jìn)行查找；續(xù)在左子樹(shù)上進(jìn)行查找；3）若給定值）若給定值大于大于根結(jié)點(diǎn)的關(guān)鍵字，則繼根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在右子樹(shù)上進(jìn)行查找。續(xù)在右子樹(shù)上進(jìn)行查找。否則否則若二叉排

27、序樹(shù)若二叉排序樹(shù)為空為空，則查找不成功；，則查找不成功；4850308020908540358832例如例如:二叉排序樹(shù)二叉排序樹(shù)查找關(guān)鍵字查找關(guān)鍵字= 50 ,505035 ,503040355090 ,50809095 49從上述查找過(guò)程可見(jiàn)，從上述查找過(guò)程可見(jiàn)，在查找過(guò)程中，生成了一條在查找過(guò)程中，生成了一條查找路徑查找路徑: 從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支逐層向下直至關(guān)鍵字等于給定值的結(jié)點(diǎn)逐層向下直至關(guān)鍵字等于給定值的結(jié)點(diǎn);或者或者 從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支逐層向下直至指針指向空樹(shù)為止。逐層向下直至指針指向空樹(shù)為

28、止。 查找成功查找成功 查找不成功查找不成功50Status SearchBST (BiTree T, KeyType key, BiTree f, BiTree &p ) / 在根指針在根指針 T 所指二叉排序樹(shù)中遞歸地查找其所指二叉排序樹(shù)中遞歸地查找其 / 關(guān)鍵字等于關(guān)鍵字等于 key 的數(shù)據(jù)元素，若的數(shù)據(jù)元素，若查找成功查找成功， / 則返回指針則返回指針 p 指向該數(shù)據(jù)元素的結(jié)點(diǎn)，并返回指向該數(shù)據(jù)元素的結(jié)點(diǎn)，并返回 / 函數(shù)值為函數(shù)值為 TRUE; / SearchBST 否則表明否則表明查找不成功查找不成功，返回，返回 / 指針指針 p 指向查找路徑上訪問(wèn)的最后一個(gè)結(jié)點(diǎn)，指向

29、查找路徑上訪問(wèn)的最后一個(gè)結(jié)點(diǎn)， / 并返回函數(shù)值為并返回函數(shù)值為FALSE, 指針指針 f 指向當(dāng)前訪問(wèn)指向當(dāng)前訪問(wèn) / 的結(jié)點(diǎn)的雙親，其初始調(diào)用值為的結(jié)點(diǎn)的雙親，其初始調(diào)用值為NULL遞歸算法描述如下：遞歸算法描述如下：51if (!T)else if ( EQ(key, T-data.key) ) else if ( LT(key, T-data.key) ) else p = f; return FALSE; / 查找不成功查找不成功 p = T; return TRUE; / 查找成功SearchBST (T-lchild, key, T, p ); / 在左子樹(shù)中繼續(xù)查找Search

30、BST (T-rchild, key, T, p ); / 在右子樹(shù)中繼續(xù)查找5230201040352523fT設(shè)設(shè) key = 48fTfT22pfTfTTTTfffp53非遞歸算法描述如下：非遞歸算法描述如下：Status Search_BST (BiTree T, KeyType key, BiTree &p ) / 在根指針在根指針 T 所指二叉排序樹(shù)中查找其所指二叉排序樹(shù)中查找其 / 關(guān)鍵字等于關(guān)鍵字等于 key 的數(shù)據(jù)元素，若的數(shù)據(jù)元素，若查找成功查找成功， / 則返回指針則返回指針 p 指向該數(shù)據(jù)元素的結(jié)點(diǎn)，并返回指向該數(shù)據(jù)元素的結(jié)點(diǎn)，并返回 / 函數(shù)值為函數(shù)值為 TR

31、UE; / Search_BST 否則表明否則表明查找不成功查找不成功，返回，返回 / 指針指針 p 指向查找路徑上訪問(wèn)的最后一個(gè)結(jié)點(diǎn)，指向查找路徑上訪問(wèn)的最后一個(gè)結(jié)點(diǎn)， / 并返回函數(shù)值為并返回函數(shù)值為FALSE54P=T;While( p) if ( EQ(key, p-data.key) ) return TRUE; / 查找成功查找成功else if ( LT(key, p-data.key) ) p=p-lchild; / 在左子樹(shù)中繼續(xù)查找在左子樹(shù)中繼續(xù)查找 else p=p-rchild; / 在右子樹(shù)中繼續(xù)查找在右子樹(shù)中繼續(xù)查找/end whilereturn FALSE; /

32、查找不成功查找不成功55 根據(jù)動(dòng)態(tài)查找表的定義，根據(jù)動(dòng)態(tài)查找表的定義，“插入插入”操作在查找不成功時(shí)才進(jìn)行操作在查找不成功時(shí)才進(jìn)行; ;5 5二叉排序樹(shù)的插入算法二叉排序樹(shù)的插入算法 若二叉排序樹(shù)為空樹(shù)，則新插入的若二叉排序樹(shù)為空樹(shù)，則新插入的結(jié)點(diǎn)為新的根結(jié)點(diǎn)；否則，結(jié)點(diǎn)為新的根結(jié)點(diǎn)；否則，新插入新插入的結(jié)點(diǎn)必為一個(gè)新的葉子結(jié)點(diǎn)，的結(jié)點(diǎn)必為一個(gè)新的葉子結(jié)點(diǎn)，其其插入位置由查找過(guò)程得到。插入位置由查找過(guò)程得到。56Status Insert BST(BiTree &T, ElemType e ) / 當(dāng)二叉排序樹(shù)中不存在關(guān)鍵字等于當(dāng)二叉排序樹(shù)中不存在關(guān)鍵字等于 e.key 的的 / 數(shù)據(jù)

33、元素時(shí)，插入元素值為數(shù)據(jù)元素時(shí)，插入元素值為 e 的結(jié)點(diǎn)，并返的結(jié)點(diǎn)，并返 / 回回 TRUE; 否則，不進(jìn)行插入并返回否則，不進(jìn)行插入并返回FALSE if (!SearchBST ( T, e.key, NULL, p ) else return FALSE; / Insert BST 57s = new BiTNode; / 為新結(jié)點(diǎn)分配空間s-data = e; s-lchild = s-rchild = NULL; if ( !p ) T = s; / 插入 s 為新的根結(jié)點(diǎn)else if ( LT(e.key, p-data.key) ) p-lchild = s; / 插入 *s

34、 為 *p 的左孩子else p-rchild = s; / 插入 *s 為 *p 的右孩子return TRUE; / 插入成功58(1)被刪除的結(jié)點(diǎn)被刪除的結(jié)點(diǎn)是葉子是葉子；(2)被刪除的結(jié)點(diǎn)被刪除的結(jié)點(diǎn)只有左子樹(shù)只有左子樹(shù)或者或者只有右子樹(shù)只有右子樹(shù)；(3)被刪除的結(jié)點(diǎn)被刪除的結(jié)點(diǎn)既有左子樹(shù)，也有右子樹(shù)既有左子樹(shù)，也有右子樹(shù)。6二叉排序樹(shù)的刪除算法二叉排序樹(shù)的刪除算法可分可分三種情況三種情況討論：討論：和插入相反，刪除在查找成功之后進(jìn)行，和插入相反，刪除在查找成功之后進(jìn)行，并且要求在刪除二叉排序樹(shù)上某個(gè)結(jié)點(diǎn)之并且要求在刪除二叉排序樹(shù)上某個(gè)結(jié)點(diǎn)之后，仍然保持二叉排序樹(shù)的特性。后，仍然保持二

35、叉排序樹(shù)的特性。5950308020908540358832（1）被刪除的結(jié)點(diǎn)是）被刪除的結(jié)點(diǎn)是葉子結(jié)點(diǎn)葉子結(jié)點(diǎn)例如例如:被刪關(guān)鍵字被刪關(guān)鍵字 = 2088其雙親結(jié)點(diǎn)中相應(yīng)指針域的值改為其雙親結(jié)點(diǎn)中相應(yīng)指針域的值改為“空空”6050308020908540358832（2）被刪除的結(jié)點(diǎn)被刪除的結(jié)點(diǎn)只有左子樹(shù)只有左子樹(shù)或者只有右子樹(shù)只有右子樹(shù) 其雙親結(jié)點(diǎn)的相應(yīng)指針域的值改為其雙親結(jié)點(diǎn)的相應(yīng)指針域的值改為 “指向被刪除結(jié)點(diǎn)的左子樹(shù)或右子樹(shù)指向被刪除結(jié)點(diǎn)的左子樹(shù)或右子樹(shù)”。被刪關(guān)鍵字被刪關(guān)鍵字 = 40806150308020908540358832（3）被刪除的結(jié)點(diǎn)）被刪除的結(jié)點(diǎn)既有左子樹(shù)，也有右

36、子樹(shù)既有左子樹(shù)，也有右子樹(shù)4040以其前驅(qū)替代之，然以其前驅(qū)替代之，然后再刪除該前驅(qū)結(jié)點(diǎn)后再刪除該前驅(qū)結(jié)點(diǎn)被刪結(jié)點(diǎn)被刪結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn)被刪關(guān)鍵字被刪關(guān)鍵字 = 5062Status DeleteBST (BiTree &T, KeyType key ) / 若二叉排序樹(shù)若二叉排序樹(shù) T 中存在其關(guān)鍵字等于中存在其關(guān)鍵字等于 key 的的 / 數(shù)據(jù)元素，則刪除該數(shù)據(jù)元素結(jié)點(diǎn)，并返回?cái)?shù)據(jù)元素，則刪除該數(shù)據(jù)元素結(jié)點(diǎn)，并返回 / 函數(shù)值函數(shù)值 TRUE，否則返回函數(shù)值，否則返回函數(shù)值 FALSE if (!T) return FALSE; / 不存在關(guān)鍵字等于key的數(shù)據(jù)元素 else /

37、 DeleteBST算法描述如下：算法描述如下： 63if ( EQ (key, T-data.key) ) / 找到關(guān)鍵字等于key的數(shù)據(jù)元素else if ( LT (key, T-data.key) ) else Delete (T); return TRUE; DeleteBST ( T-lchild, key ); / 繼續(xù)在左子樹(shù)中進(jìn)行查找DeleteBST ( T-rchild, key ); / 繼續(xù)在右子樹(shù)中進(jìn)行查找64void Delete ( BiTree &p ) / 從二叉排序樹(shù)中刪除結(jié)點(diǎn) p， / 并重接它的左子樹(shù)或右子樹(shù) if (!p-rchild) el

38、se if (!p-lchild) else / Delete其中刪除操作刪除操作過(guò)程如下所描述： 65 / 右子樹(shù)為空樹(shù)則只需重接它的左子樹(shù)右子樹(shù)為空樹(shù)則只需重接它的左子樹(shù)q = p; p = p-lchild; delete(q);pp66/ 左子樹(shù)為空樹(shù)只需重接它的右子樹(shù)左子樹(shù)為空樹(shù)只需重接它的右子樹(shù)q = p; p = p-rchild; delete(q);pp67q = p; s = p-lchild;while (s-rchild) q = s; s = s-rchild; / s 指向被刪結(jié)點(diǎn)的前驅(qū)/ 左右子樹(shù)均不空左右子樹(shù)均不空p-data = s-data;if (q !=

39、 p ) q-rchild = s-lchild; /s有右子樹(shù)else q-lchild = s-lchild;/s無(wú)右子樹(shù) / 重接*q的左子樹(shù)delete(s);pqs687查找性能的分析查找性能的分析 對(duì)于每一棵特定的二叉排序樹(shù)，對(duì)于每一棵特定的二叉排序樹(shù)，均可按照平均查找長(zhǎng)度的定義來(lái)求它均可按照平均查找長(zhǎng)度的定義來(lái)求它的的 ASL 值，顯然，由值相同的值，顯然，由值相同的 n 個(gè)關(guān)個(gè)關(guān)鍵字，構(gòu)造所得的不同形態(tài)的各棵二鍵字，構(gòu)造所得的不同形態(tài)的各棵二叉排序樹(shù)的平均查找長(zhǎng)叉排序樹(shù)的平均查找長(zhǎng) 度的值不同，度的值不同，甚至可能差別很大。甚至可能差別很大。69由關(guān)鍵字序列由關(guān)鍵字序列 3，1

40、，2，5，4構(gòu)造而得的二叉排序樹(shù)構(gòu)造而得的二叉排序樹(shù)由關(guān)鍵字序列由關(guān)鍵字序列 1，2，3，4，5構(gòu)造而得的二叉排序樹(shù)，構(gòu)造而得的二叉排序樹(shù)，例如：例如：2134535412ASL =（1+2+3+4+5）/ 5 = 3ASL =（1+2+3+2+3）/ 5 = 2.270 下面討論平均情況下面討論平均情況: 不失一般性，假設(shè)長(zhǎng)度為不失一般性，假設(shè)長(zhǎng)度為 n 的序列中有的序列中有 k 個(gè)關(guān)鍵字個(gè)關(guān)鍵字小于小于第一個(gè)關(guān)鍵字，則必有第一個(gè)關(guān)鍵字，則必有 n-k-1 個(gè)關(guān)鍵字個(gè)關(guān)鍵字大于大于第一個(gè)關(guān)鍵字第一個(gè)關(guān)鍵字,由它構(gòu)造的二由它構(gòu)造的二叉排序樹(shù)叉排序樹(shù)n-k-1k的平均查找長(zhǎng)度是的平均查找長(zhǎng)度是

41、n 和和 k 的函數(shù)的函數(shù)P(n, k) ( 0 k n-1 )71 假設(shè)假設(shè) n 個(gè)關(guān)鍵字可能出現(xiàn)的個(gè)關(guān)鍵字可能出現(xiàn)的 n! 種排列種排列的可能性相同，則含的可能性相同，則含 n 個(gè)關(guān)鍵字的二叉?zhèn)€關(guān)鍵字的二叉排序樹(shù)的平均查找長(zhǎng)度排序樹(shù)的平均查找長(zhǎng)度10),(1)(nkknPnnPASL在在等概率等概率查找的情況下，查找的情況下，CnnnnPlog12)(729.2.2平衡二叉樹(shù)平衡二叉樹(shù)1. “平衡二叉樹(shù)平衡二叉樹(shù)”2. 失衡的類(lèi)型及調(diào)整方法失衡的類(lèi)型及調(diào)整方法3. “平衡二叉樹(shù)平衡二叉樹(shù)”的插入的插入4. “平衡二叉樹(shù)平衡二叉樹(shù)”查找性能分析查找性能分析731.平衡二叉樹(shù)平衡二叉樹(shù)(AVL

42、樹(shù)樹(shù))定義：平衡二叉樹(shù)又稱(chēng)定義：平衡二叉樹(shù)又稱(chēng)AVL樹(shù)，是二叉排序樹(shù)，是二叉排序樹(shù)的另一種形式。它或者是一棵空樹(shù)，或者樹(shù)的另一種形式。它或者是一棵空樹(shù)，或者是具有下列性質(zhì)的二叉樹(shù)：是具有下列性質(zhì)的二叉樹(shù)：它的左子樹(shù)和右它的左子樹(shù)和右子樹(shù)都是平衡二叉樹(shù)，且左子樹(shù)和右子樹(shù)的子樹(shù)都是平衡二叉樹(shù)，且左子樹(shù)和右子樹(shù)的深度之差的絕對(duì)值不超過(guò)深度之差的絕對(duì)值不超過(guò)1。1RLhh結(jié)點(diǎn)的平衡因子：結(jié)點(diǎn)的平衡因子： 該結(jié)點(diǎn)的左子樹(shù)高度減去它的右子樹(shù)高度。即：該結(jié)點(diǎn)的左子樹(shù)高度減去它的右子樹(shù)高度。即：74例如例如:548254821是平衡樹(shù)是平衡樹(shù)不是平衡樹(shù)不是平衡樹(shù)失去平衡的最小子樹(shù)失去平衡的最小子樹(shù)75平衡二叉

43、樹(shù)存儲(chǔ)結(jié)構(gòu)平衡二叉樹(shù)存儲(chǔ)結(jié)構(gòu)Typedef struct BSTNodeElemTypedata;intbf; /平衡因子平衡因子 struct BSTNode *lchild,*rchild;BSTNode,*BSTree;762.失衡的類(lèi)型及調(diào)整方法失衡的類(lèi)型及調(diào)整方法 （1）失衡的類(lèi)型）失衡的類(lèi)型54242586774265894258678LL型型：定義失去平衡的最小子樹(shù)根節(jié)點(diǎn)定義失去平衡的最小子樹(shù)根節(jié)點(diǎn)為為a，則該類(lèi)不平衡可歸納為，在，則該類(lèi)不平衡可歸納為，在a的左子的左子樹(shù)根節(jié)點(diǎn)的左子樹(shù)上插入導(dǎo)致的不平衡可樹(shù)根節(jié)點(diǎn)的左子樹(shù)上插入導(dǎo)致的不平衡可使用單向右旋平衡處理，可以記為使用單向右

44、旋平衡處理，可以記為左左左左-右右。（2 2）失衡的類(lèi)型及調(diào)整方法）失衡的類(lèi)型及調(diào)整方法5410543102543000右旋右旋79可歸納為可歸納為L(zhǎng)LLL型型- -右旋右旋2ABBLBRh-1h1ARh-10h-1ABBLBRh-1hAR0在單向右旋平衡處理后在單向右旋平衡處理后BF(B)BF(B)由由1 1變變?yōu)闉? 0，BF(A)BF(A)由由2 2變?yōu)樽優(yōu)? 0。80RR型型：在在a的右子樹(shù)根節(jié)點(diǎn)的右子樹(shù)上的右子樹(shù)根節(jié)點(diǎn)的右子樹(shù)上插入導(dǎo)致的不平衡可使用單向左旋平衡處插入導(dǎo)致的不平衡可使用單向左旋平衡處理，可以記為理，可以記為右右右右-左左。左旋左旋43580-10-1435819000

45、0-143581900-1-2-281可歸納為可歸納為RRRR型型- -左旋左旋在單向左旋平衡處理后在單向左旋平衡處理后BF(B)BF(B)由由-1-1變?yōu)樽優(yōu)? 0，BF(A)BF(A)由由-2-2變?yōu)樽優(yōu)? 0。ABBRBLh-1h-1-2ALh-1ABBRALh-1h0BLh-1082LR型型：在在3的左子樹(shù)根節(jié)點(diǎn)的左子樹(shù)根節(jié)點(diǎn)1的右子樹(shù)上的右子樹(shù)上插入節(jié)點(diǎn)插入節(jié)點(diǎn)2導(dǎo)致不平衡，可使用雙向旋轉(zhuǎn)：導(dǎo)致不平衡，可使用雙向旋轉(zhuǎn)：先使其子樹(shù)左旋再整棵樹(shù)右旋，可記為左先使其子樹(shù)左旋再整棵樹(shù)右旋，可記為左右右-左右。左右。先左旋先左旋458190003211-12045819000321211045

46、8190003002010后右旋后右旋83可歸納為可歸納為L(zhǎng)RLR型型在雙向旋轉(zhuǎn)平衡處理后在雙向旋轉(zhuǎn)平衡處理后BF(A)BF(A)由由2 2變?yōu)樽優(yōu)?1-1，BF(B)BF(B)由由-1-1變?yōu)樽優(yōu)? 0，BF(C)BF(C)由由1 1變?yōu)樽優(yōu)? 0。CACLARh-1h-12CRh-21BBL-1h-1BLh-1CLh-1B0C0CRh-2AARh-1-184RL型：型：在在19的右子樹(shù)根節(jié)的右子樹(shù)根節(jié)點(diǎn)點(diǎn)25的左子樹(shù)上插入節(jié)點(diǎn)的左子樹(shù)上插入節(jié)點(diǎn)23導(dǎo)致不平衡，導(dǎo)致不平衡，可使用雙向旋可使用雙向旋轉(zhuǎn)：先使其子樹(shù)右旋再整棵轉(zhuǎn)：先使其子樹(shù)右旋再整棵樹(shù)左旋，可記為右左樹(shù)左旋，可記為右左-右左。右左

47、。先右旋先右旋后左旋后左旋45819-2-2030-2201025231045819-2-2030-220102325-10458230-1030201025190085可歸納為可歸納為RLRL型型在雙向旋轉(zhuǎn)平衡處理后在雙向旋轉(zhuǎn)平衡處理后BF(A)BF(A)由由-2-2變?yōu)樽優(yōu)? 0，BF(B)BF(B)由由1 1變?yōu)樽優(yōu)?1,BF(C)-1,BF(C)由由1 1變?yōu)樽優(yōu)? 0。ABRh-1-2CCLh-1CRh-21BAL1h-1ALh-1CLh-1A0C0CRh-2BBR-186旋轉(zhuǎn)操作特點(diǎn)旋轉(zhuǎn)操作特點(diǎn)(1)(1)對(duì)不平衡的最小子樹(shù)操作。對(duì)不平衡的最小子樹(shù)操作。(2)(2)旋轉(zhuǎn)后子樹(shù)根節(jié)點(diǎn)

48、平衡因子為旋轉(zhuǎn)后子樹(shù)根節(jié)點(diǎn)平衡因子為0 0。(3)(3)旋轉(zhuǎn)后子樹(shù)深度不變故不影響全旋轉(zhuǎn)后子樹(shù)深度不變故不影響全樹(shù)，也不影響插入路徑上所有祖先結(jié)樹(shù)，也不影響插入路徑上所有祖先結(jié)點(diǎn)的平衡度。點(diǎn)的平衡度。87例如例如:依次插入的關(guān)鍵字為依次插入的關(guān)鍵字為5, 4, 2, 8, 6, 95424258665842向右旋轉(zhuǎn)向右旋轉(zhuǎn)一次一次先向右旋轉(zhuǎn)先向右旋轉(zhuǎn)再向左旋轉(zhuǎn)再向左旋轉(zhuǎn)88426589642895向左旋轉(zhuǎn)一次向左旋轉(zhuǎn)一次繼續(xù)插入關(guān)鍵字繼續(xù)插入關(guān)鍵字 9893.3.平衡二叉樹(shù)插入算法思想平衡二叉樹(shù)插入算法思想(1)(1)若是空樹(shù)，插入節(jié)點(diǎn)作為根節(jié)點(diǎn)，樹(shù)若是空樹(shù)，插入節(jié)點(diǎn)作為根節(jié)點(diǎn)，樹(shù)深度加深度加

49、1 1。(2)(2)插入節(jié)點(diǎn)插入節(jié)點(diǎn)keykey值等于根節(jié)點(diǎn)值等于根節(jié)點(diǎn)keykey值，則值，則不插入。不插入。(3)(3)插入節(jié)點(diǎn)插入節(jié)點(diǎn)keykey值小于根節(jié)點(diǎn)值小于根節(jié)點(diǎn)keykey值，插值，插入在左子樹(shù)上，左子樹(shù)深加入在左子樹(shù)上，左子樹(shù)深加1 1并且：并且：90插入在左子樹(shù)上情況插入在左子樹(shù)上情況1 1左子樹(shù)深度左子樹(shù)深度 右子樹(shù)深度右子樹(shù)深度LLLL型型插入前若根節(jié)點(diǎn)平衡因子為插入前若根節(jié)點(diǎn)平衡因子為1,1,插入后其插入后其左子樹(shù)的平衡因子為左子樹(shù)的平衡因子為1 1（左左），則單（左左），則單向右旋，旋轉(zhuǎn)后根節(jié)點(diǎn)和右子樹(shù)的平衡向右旋，旋轉(zhuǎn)后根節(jié)點(diǎn)和右子樹(shù)的平衡因子改為因子改為0 0，

50、樹(shù)深不變。，樹(shù)深不變。ABBLBRh-1h12ARh-1ABBLBRh-1h0ARh-1093插入在左子樹(shù)上的情況插入在左子樹(shù)上的情況4 4左子樹(shù)深度左子樹(shù)深度 右子樹(shù)深度右子樹(shù)深度LRLR型型插入前若根節(jié)點(diǎn)平衡因子為插入前若根節(jié)點(diǎn)平衡因子為1,1,插入后左子樹(shù)的插入后左子樹(shù)的平衡因子為平衡因子為-1-1（左右），則先左旋再右旋，旋（左右），則先左旋再右旋，旋轉(zhuǎn)后根節(jié)點(diǎn)和其左子樹(shù)的平衡因子改為轉(zhuǎn)后根節(jié)點(diǎn)和其左子樹(shù)的平衡因子改為0 0，右，右子樹(shù)的平衡因子改為子樹(shù)的平衡因子改為-1,-1,樹(shù)深不變。樹(shù)深不變。CACLARh-1h-12CRh-21BBL-1h-1BLh-1CLh-1B0C0CRh

51、-2AARh-1-194(4)(4)插入節(jié)點(diǎn)插入節(jié)點(diǎn)keykey值大于根節(jié)點(diǎn)值大于根節(jié)點(diǎn)keykey值，值，插入在右子樹(shù)上，方法類(lèi)似第插入在右子樹(shù)上，方法類(lèi)似第3 3步。步。95 在平衡樹(shù)上進(jìn)行查找的過(guò)程和二叉在平衡樹(shù)上進(jìn)行查找的過(guò)程和二叉排序樹(shù)相同，因此，排序樹(shù)相同，因此，查找過(guò)程中和給定查找過(guò)程中和給定值進(jìn)行比較的關(guān)鍵字的個(gè)數(shù)不超過(guò)平衡值進(jìn)行比較的關(guān)鍵字的個(gè)數(shù)不超過(guò)平衡 樹(shù)的深度。樹(shù)的深度。.平衡二叉樹(shù)的查找性能分析平衡二叉樹(shù)的查找性能分析 問(wèn)：含問(wèn)：含 n 個(gè)關(guān)鍵字的二叉平衡樹(shù)個(gè)關(guān)鍵字的二叉平衡樹(shù)可能達(dá)到的最大深度是多少？可能達(dá)到的最大深度是多少？96n = 0空樹(shù)空樹(shù)最大深度為最大深度

52、為 0n = 1最大深度為最大深度為 1n = 2最大深度為最大深度為 2n = 4最大深度為最大深度為 3n = 7最大深度為最大深度為 4先看幾個(gè)具體情況:97反過(guò)來(lái)問(wèn)，深度為深度為 h 的二叉平衡樹(shù)平衡樹(shù)中所含結(jié)點(diǎn)的最小值含結(jié)點(diǎn)的最小值 Nh 是多少？h = 0N0 = 0h = 1h = 2h = 3一般情況下，一般情況下，N1 = 1N2 = 2N3 = 4Nh = Nh-1 + Nh-2 + 1利用歸納法可證得，利用歸納法可證得， Nh = Fh+2 - 1Fh+2 h/ 5 其中：其中： = (1+ 5 )/298 因此，在二叉平衡樹(shù)上進(jìn)行查找時(shí)，因此，在二叉平衡樹(shù)上進(jìn)行查找時(shí)，

53、查找過(guò)程中和給定值進(jìn)行比較的關(guān)鍵字查找過(guò)程中和給定值進(jìn)行比較的關(guān)鍵字的個(gè)數(shù)和的個(gè)數(shù)和 log(n) 相當(dāng)相當(dāng)。 由此推得，深度為由此推得，深度為 h 的二叉平衡樹(shù)的二叉平衡樹(shù)中所含結(jié)點(diǎn)的最小值中所含結(jié)點(diǎn)的最小值 Nh = h+2/5 - 1 反之，含有反之，含有 n 個(gè)結(jié)點(diǎn)的二叉平衡樹(shù)能個(gè)結(jié)點(diǎn)的二叉平衡樹(shù)能達(dá)到的最大深度達(dá)到的最大深度 hn = log ( 5 (n+1) - 2 999.2.3、 B - 樹(shù)樹(shù)1定義定義2查找查找3插入插入4刪除刪除5查找性能的分析查找性能的分析100(1)樹(shù)中每個(gè)結(jié)點(diǎn)至多有樹(shù)中每個(gè)結(jié)點(diǎn)至多有m棵子樹(shù)；棵子樹(shù)；(2)若根結(jié)點(diǎn)不是葉結(jié)點(diǎn)，則至少有兩棵子若根結(jié)點(diǎn)不

54、是葉結(jié)點(diǎn)，則至少有兩棵子樹(shù)；樹(shù)；(3)除根之外的所有非終端結(jié)點(diǎn)至少有除根之外的所有非終端結(jié)點(diǎn)至少有 m/2 棵子樹(shù)；棵子樹(shù)；m m階階B-B-樹(shù)或?yàn)榭諛?shù)樹(shù)或?yàn)榭諛?shù), ,或?yàn)闈M(mǎn)足下列特性或?yàn)闈M(mǎn)足下列特性m m叉樹(shù)叉樹(shù)1B-樹(shù)的定義樹(shù)的定義101(4)(4)所有非終端結(jié)點(diǎn)中包含下列信息：所有非終端結(jié)點(diǎn)中包含下列信息：(n,A0,K1,A1,K2,A2,(n,A0,K1,A1,K2,A2,Kn,An),Kn,An)其中：其中：KiKi為關(guān)鍵字，且均自小至大有序排為關(guān)鍵字，且均自小至大有序排列，即：列，即：K1 K2 K1 K2 Kn Kn ； Ai Ai為指向子樹(shù)根結(jié)點(diǎn)的指針，且指針為指向子樹(shù)根結(jié)點(diǎn)

55、的指針，且指針Ai-1Ai-1所指子樹(shù)上所有關(guān)鍵字均小于所指子樹(shù)上所有關(guān)鍵字均小于Ki Ki ； An An 所指子樹(shù)上所有關(guān)鍵字均大于所指子樹(shù)上所有關(guān)鍵字均大于Kn Kn ；（5 5）樹(shù)中所有葉子結(jié)點(diǎn)均不帶信息，且在）樹(shù)中所有葉子結(jié)點(diǎn)均不帶信息，且在樹(shù)中的同一層次上。樹(shù)中的同一層次上。102例如：例如：4階階B-樹(shù)樹(shù) root 50 15 71 84 3 8 20 26 43 56 62 78 89 96103 從根結(jié)點(diǎn)出發(fā)，從根結(jié)點(diǎn)出發(fā)，沿指針?biāo)阉鹘Y(jié)點(diǎn)沿指針?biāo)阉鹘Y(jié)點(diǎn)和和在在結(jié)點(diǎn)內(nèi)進(jìn)行順序（或折半）查找結(jié)點(diǎn)內(nèi)進(jìn)行順序（或折半）查找 兩個(gè)過(guò)程兩個(gè)過(guò)程交叉進(jìn)行。交叉進(jìn)行。2.查找查找 若若查找成

56、功查找成功，則返回指向被查關(guān)鍵字所，則返回指向被查關(guān)鍵字所在在結(jié)點(diǎn)的指針結(jié)點(diǎn)的指針和和關(guān)鍵字在結(jié)點(diǎn)中的位置關(guān)鍵字在結(jié)點(diǎn)中的位置；若若查找不成功查找不成功，則返回插入位置，則返回插入位置。104例如：查找例如：查找78，26，60 root 50 15 71 84 3 8 20 26 43 56 62 78 89 96105在查找不成功之后，需進(jìn)行插入。在查找不成功之后，需進(jìn)行插入。顯然，顯然，關(guān)鍵字插入的位置必定在最下關(guān)鍵字插入的位置必定在最下層的非葉結(jié)點(diǎn)層的非葉結(jié)點(diǎn)，有下列幾種情況：，有下列幾種情況：3插入插入(1)插入后，該結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)插入后，該結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)nm， 不修改指針不修改

57、指針; ; 例如例如106(2)插入后，該結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)插入后，該結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù) n=m， 則則需進(jìn)行需進(jìn)行“結(jié)點(diǎn)分裂結(jié)點(diǎn)分裂”，令，令 s = m/2 ， 在原結(jié)點(diǎn)中保留在原結(jié)點(diǎn)中保留 （A0，K1，。，。， Ks-1，As-1）；）； 建新結(jié)點(diǎn)建新結(jié)點(diǎn) （As，Ks+1，。，。 ，Kn，An）；）； 將（將（Ks，p）插入雙親結(jié)點(diǎn)）插入雙親結(jié)點(diǎn)；例如例如(3)若雙親為空，則若雙親為空，則建新的根結(jié)點(diǎn)建新的根結(jié)點(diǎn)。 例如例如107例如例如:下列為下列為 3 階階B-樹(shù)樹(shù)50 20 40 80 插入關(guān)鍵字插入關(guān)鍵字 = 60, 60 80 90, 60 80 90 90 50 80 60

58、30 40 20 30 50 808030 50108節(jié)點(diǎn)分裂的一般規(guī)律：節(jié)點(diǎn)分裂的一般規(guī)律：假設(shè)假設(shè)p p節(jié)點(diǎn)中已有節(jié)點(diǎn)中已有m-1m-1個(gè)關(guān)鍵字，當(dāng)插入一個(gè)關(guān)鍵字，當(dāng)插入一個(gè)關(guān)鍵字之后，節(jié)點(diǎn)中信息為：個(gè)關(guān)鍵字之后，節(jié)點(diǎn)中信息為： m,Am,A0 0,(K,(K1 1,A,A1 1),(K),(K2 2,A,A2 2),),(K,(Km m,A,Am m) )其中其中K Ki i K Ki+1i+1 ，1 1imim。 以中間關(guān)鍵字為界以中間關(guān)鍵字為界, ,把結(jié)點(diǎn)一分為二把結(jié)點(diǎn)一分為二為兩個(gè)結(jié)點(diǎn)，并把中間的關(guān)鍵字向上插入為兩個(gè)結(jié)點(diǎn)，并把中間的關(guān)鍵字向上插入到父結(jié)點(diǎn)上，若父結(jié)點(diǎn)已滿(mǎn)，用通樣的方

59、到父結(jié)點(diǎn)上，若父結(jié)點(diǎn)已滿(mǎn)，用通樣的方法繼續(xù)分裂結(jié)點(diǎn)。法繼續(xù)分裂結(jié)點(diǎn)。109 和插入的考慮相反，首先必須找到待刪和插入的考慮相反，首先必須找到待刪關(guān)鍵字所在結(jié)點(diǎn)，并且要求刪除之后，結(jié)關(guān)鍵字所在結(jié)點(diǎn)，并且要求刪除之后，結(jié)點(diǎn)中點(diǎn)中關(guān)鍵字的個(gè)數(shù)不能小于關(guān)鍵字的個(gè)數(shù)不能小于 m/2 -1，否則，否則，要從其左要從其左(或右或右)兄弟結(jié)點(diǎn)兄弟結(jié)點(diǎn)“借調(diào)借調(diào)”關(guān)鍵字，關(guān)鍵字，若其左和右兄弟結(jié)點(diǎn)均無(wú)關(guān)鍵字可借若其左和右兄弟結(jié)點(diǎn)均無(wú)關(guān)鍵字可借(結(jié)結(jié)點(diǎn)中只有最少量的關(guān)鍵字點(diǎn)中只有最少量的關(guān)鍵字),則必須進(jìn)行結(jié)則必須進(jìn)行結(jié)點(diǎn)的點(diǎn)的“合并合并”。4刪除刪除110如在如在3 3階階B-B-樹(shù)中依次刪除關(guān)鍵字樹(shù)中依次刪除

60、關(guān)鍵字12,5012,50，5353，3737，分為三種情況，分為三種情況45abt24b53 90e3 12c37d50f61 70g100h3階階B-樹(shù)樹(shù)11145abt24b53 90e3 c37d50f61 70g100h(1)(1)被刪關(guān)鍵字被刪關(guān)鍵字(12)(12)所在節(jié)點(diǎn)所在節(jié)點(diǎn)(c)(c)中的關(guān)鍵中的關(guān)鍵字?jǐn)?shù)目不小于字?jǐn)?shù)目不小于 m/2m/2 -1-1，則只須從該節(jié)點(diǎn)，則只須從該節(jié)點(diǎn)(c)(c)中刪去該關(guān)鍵字中刪去該關(guān)鍵字(12)(12)和相應(yīng)指針，和相應(yīng)指針，樹(shù)的其他部分不變。樹(shù)的其他部分不變。刪除關(guān)鍵字刪除關(guān)鍵字121212112（2 2）被刪關(guān)鍵字）被刪關(guān)鍵字(50)(50)所在節(jié)點(diǎn)所在節(jié)點(diǎn)(f)(f)中的關(guān)鍵字?jǐn)?shù)中的關(guān)鍵