數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言查找表詳細(xì)舉例介紹實(shí)用教案

1、 查找表是由同一類(lèi)型查找表是由同一類(lèi)型(lixng)的數(shù)據(jù)元素的數(shù)據(jù)元素(或記錄或記錄)構(gòu)成的集合。構(gòu)成的集合。 由于由于“集合集合”中的數(shù)據(jù)中的數(shù)據(jù)(shj)元素元素之間存在著松散的關(guān)系，因此查找表之間存在著松散的關(guān)系，因此查找表是一種應(yīng)用靈便的結(jié)構(gòu)。是一種應(yīng)用靈便的結(jié)構(gòu)。何謂何謂(hwi)(hwi)查找表查找表 ？第1頁(yè)/共169頁(yè)第一頁(yè)，共169頁(yè)。對(duì)查找表經(jīng)常對(duì)查找表經(jīng)常(jngchng)(jngchng)進(jìn)行的操作進(jìn)行的操作: :1. 查詢(xún)某個(gè)查詢(xún)某個(gè)(mu )“特定的特定的”數(shù)據(jù)數(shù)據(jù)元素是否在查找表中；元素是否在查找表中；2. 檢索某個(gè)檢索某個(gè)(mu )“特定的特定的”數(shù)據(jù)數(shù)據(jù)元素

2、的各種屬性；元素的各種屬性；3. 在查找表中插入一個(gè)數(shù)據(jù)元素；在查找表中插入一個(gè)數(shù)據(jù)元素；4. 從查找表中刪去某個(gè)從查找表中刪去某個(gè)(mu )數(shù)據(jù)數(shù)據(jù)元素。元素。第2頁(yè)/共169頁(yè)第二頁(yè)，共169頁(yè)。僅作查詢(xún)和檢索僅作查詢(xún)和檢索(jin su)操作的查找表。操作的查找表。有時(shí)有時(shí)(yush)在查詢(xún)之后，還需要將在查詢(xún)之后，還需要將“查查詢(xún)?cè)儭苯Y(jié)果為結(jié)果為“不在查找表中不在查找表中”的數(shù)據(jù)元素的數(shù)據(jù)元素插入到查找表中；或者，從查找表中刪除插入到查找表中；或者，從查找表中刪除其其“查詢(xún)查詢(xún)”結(jié)果為結(jié)果為“在查找表中在查找表中”的數(shù)據(jù)的數(shù)據(jù)元素。元素。查找表可分為兩類(lèi)查找表可分為兩類(lèi):第3頁(yè)/共16

3、9頁(yè)第三頁(yè)，共169頁(yè)。是數(shù)據(jù)元素（或記錄）中某個(gè)是數(shù)據(jù)元素（或記錄）中某個(gè)(mu )數(shù)據(jù)項(xiàng)的值，用以標(biāo)識(shí)（識(shí)別）數(shù)據(jù)項(xiàng)的值，用以標(biāo)識(shí)（識(shí)別）一個(gè)數(shù)據(jù)元素（或記錄）。一個(gè)數(shù)據(jù)元素（或記錄）。 若此關(guān)鍵字可以識(shí)別唯一的一個(gè)若此關(guān)鍵字可以識(shí)別唯一的一個(gè)(y )記錄，則稱(chēng)之謂記錄，則稱(chēng)之謂“主關(guān)鍵字主關(guān)鍵字”。 若此關(guān)鍵字能識(shí)別若干若此關(guān)鍵字能識(shí)別若干(rugn)記錄，則稱(chēng)記錄，則稱(chēng)之謂之謂“次關(guān)鍵字次關(guān)鍵字”。第4頁(yè)/共169頁(yè)第四頁(yè)，共169頁(yè)。 根據(jù)給定的某個(gè)值，在查找根據(jù)給定的某個(gè)值，在查找(ch zho)表中表中確定一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素或確定一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素或（

4、記錄）（記錄） 查找查找(ch zho) 若查找表中存在這樣若查找表中存在這樣(zhyng)一個(gè)記錄，一個(gè)記錄，則稱(chēng)則稱(chēng)“查找成功查找成功”，查找結(jié)果：給出整個(gè)記，查找結(jié)果：給出整個(gè)記錄的信息，或指示該記錄在查找表中的位錄的信息，或指示該記錄在查找表中的位置；置； 否則稱(chēng)否則稱(chēng)“查找不成功查找不成功”，查找結(jié)果：給出，查找結(jié)果：給出“空記錄空記錄”或或“空指針空指針”。第5頁(yè)/共169頁(yè)第五頁(yè)，共169頁(yè)。 由于查找表中的數(shù)據(jù)元素由于查找表中的數(shù)據(jù)元素(yun s)之間不存在明顯的組織規(guī)律，因之間不存在明顯的組織規(guī)律，因此不便于查找。此不便于查找。 為了提高查找的效率，為了提高查找的效率， 需

5、要在查需要在查找表中的元素找表中的元素(yun s)之間人為地之間人為地 附附加某種確定的關(guān)系，換句話(huà)說(shuō)，加某種確定的關(guān)系，換句話(huà)說(shuō)， 用另用另外一種結(jié)構(gòu)來(lái)表示查找表。外一種結(jié)構(gòu)來(lái)表示查找表。查找查找(ch zho)的方法取決于查找的方法取決于查找(ch zho)表的結(jié)構(gòu)。表的結(jié)構(gòu)。如何進(jìn)行如何進(jìn)行(jnxng)查找？查找？第6頁(yè)/共169頁(yè)第六頁(yè)，共169頁(yè)。9.1 靜態(tài)靜態(tài)(jngti)查找表查找表9.2 動(dòng)態(tài)動(dòng)態(tài)(dngti)查找樹(shù)表查找樹(shù)表9.3 哈希表哈希表第7頁(yè)/共169頁(yè)第七頁(yè)，共169頁(yè)。第8頁(yè)/共169頁(yè)第八頁(yè)，共169頁(yè)。數(shù)據(jù)數(shù)據(jù)(shj)對(duì)象對(duì)象D：數(shù)據(jù)數(shù)據(jù)(shj)關(guān)系

6、關(guān)系R：D是具有相同特性的數(shù)是具有相同特性的數(shù)據(jù)元素?fù)?jù)元素(yun s)的集合。每個(gè)數(shù)的集合。每個(gè)數(shù)據(jù)元素?fù)?jù)元素(yun s)含有類(lèi)型相同的含有類(lèi)型相同的關(guān)鍵字，可唯一標(biāo)識(shí)數(shù)關(guān)鍵字，可唯一標(biāo)識(shí)數(shù)據(jù)元素?fù)?jù)元素(yun s)。 數(shù)據(jù)元素同屬一個(gè)集合。數(shù)據(jù)元素同屬一個(gè)集合。ADT StaticSearchTable 第9頁(yè)/共169頁(yè)第九頁(yè)，共169頁(yè)。 Create(&ST, n);Destroy(&ST);Search(ST, key);Traverse(ST, Visit();基本操作基本操作 P：next ADT StaticSearchTable第10頁(yè)/共169頁(yè)第十頁(yè)，共169頁(yè)。構(gòu)造

7、一個(gè)含構(gòu)造一個(gè)含n個(gè)數(shù)據(jù)個(gè)數(shù)據(jù)(shj)元素元素的靜態(tài)查找表的靜態(tài)查找表ST。 Create(&ST, n);操作操作(cozu)結(jié)果：結(jié)果：第11頁(yè)/共169頁(yè)第十一頁(yè)，共169頁(yè)。銷(xiāo)毀銷(xiāo)毀(xiohu)表表ST。Destroy(&ST);初始條件：初始條件：操作操作(cozu)結(jié)果：結(jié)果：靜態(tài)查找靜態(tài)查找(ch zho)表表ST存在；存在；第12頁(yè)/共169頁(yè)第十二頁(yè)，共169頁(yè)。若若 ST 中存在其關(guān)鍵字等于中存在其關(guān)鍵字等于(dngy) key 的數(shù)據(jù)元素，則函數(shù)值的數(shù)據(jù)元素，則函數(shù)值為該元素的值或在表中的位為該元素的值或在表中的位置，否則為置，否則為“空空”。 Search(ST,

8、key);初始條件：初始條件：操作操作(cozu)結(jié)果：結(jié)果：靜態(tài)查找靜態(tài)查找(ch zho)表表ST存存在，在，key 為和查找為和查找(ch zho)表中元素的關(guān)鍵字類(lèi)型相同表中元素的關(guān)鍵字類(lèi)型相同的給定值；的給定值；第13頁(yè)/共169頁(yè)第十三頁(yè)，共169頁(yè)。按某種次序?qū)Π茨撤N次序?qū)T的每個(gè)元的每個(gè)元素調(diào)用函數(shù)素調(diào)用函數(shù)Visit()一次且僅一次且僅一次，一旦一次，一旦(ydn)Visit()失失敗，則操作失敗。敗，則操作失敗。Traverse(ST, Visit();初始條件：初始條件：操作操作(cozu)結(jié)果：結(jié)果：靜態(tài)查找表靜態(tài)查找表ST存在，存在，Visit是對(duì)元素操作的應(yīng)用是對(duì)

9、元素操作的應(yīng)用(yngyng)函數(shù)；函數(shù)；第14頁(yè)/共169頁(yè)第十四頁(yè)，共169頁(yè)。typedef struct / 數(shù)據(jù)元素存儲(chǔ)空間基址，建表時(shí)數(shù)據(jù)元素存儲(chǔ)空間基址，建表時(shí) / 按實(shí)際長(zhǎng)度按實(shí)際長(zhǎng)度(chngd)分配，分配，0號(hào)單元留空號(hào)單元留空 int length; / 表的長(zhǎng)度表的長(zhǎng)度(chngd) SSTable;假設(shè)靜態(tài)查找假設(shè)靜態(tài)查找(ch zho)表的順序存表的順序存儲(chǔ)結(jié)構(gòu)為儲(chǔ)結(jié)構(gòu)為ElemType *elem;第15頁(yè)/共169頁(yè)第十五頁(yè)，共169頁(yè)。數(shù)據(jù)元素?cái)?shù)據(jù)元素(yun s)類(lèi)型的定義為類(lèi)型的定義為:typedef struct keyType key; / 關(guān)鍵字域

10、/ 其它(qt)屬性域 ElemType ; , TElemType ;第16頁(yè)/共169頁(yè)第十六頁(yè)，共169頁(yè)。第17頁(yè)/共169頁(yè)第十七頁(yè)，共169頁(yè)。 以順序以順序(shnx)表或線(xiàn)表或線(xiàn)性鏈表表示靜態(tài)查找表性鏈表表示靜態(tài)查找表一、順序一、順序(shnx)查找查找表表第18頁(yè)/共169頁(yè)第十八頁(yè)，共169頁(yè)。21 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 ST.LengthST.elem回顧順序表的查找回顧順序表的查找(ch zho)過(guò)程：過(guò)程：假設(shè)給定假設(shè)給定(i dn)值值 e=64,要求要求 ST.elemk =

11、 e, 問(wèn)問(wèn): k = ?kk第19頁(yè)/共169頁(yè)第十九頁(yè)，共169頁(yè)。int Location( SqList L, ElemType& e, Status (*compare)(ElemType, ElemType) k = 1; p = L.elem; while ( k=L.length & compare(*p+,e) k+; if ( k= L.length) return k; else return 0;第20頁(yè)/共169頁(yè)第二十頁(yè)，共169頁(yè)。21 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 ST.Lengt

12、hST.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第21頁(yè)/共169頁(yè)第二十一頁(yè)，共169頁(yè)。int Search_Seq(SSTable ST, KeyType key) / 在順序表在順序表ST中順序查找其關(guān)鍵字等于中順序查找其關(guān)鍵字等于 / key的數(shù)據(jù)元素。若找到，則函數(shù)值為的數(shù)據(jù)元素。若找到，則函數(shù)值為 / 該元素在表中的位置，否則為該元素在表中的位置，否則為0。 ST.elem0.key = key; / “哨兵哨兵” for

13、(i=ST.length; ST.elemi.key!=key; -i); / 從后往前從后往前(wn qin)找找 return i; / 找不到時(shí)，找不到時(shí)，i為為0第22頁(yè)/共169頁(yè)第二十二頁(yè)，共169頁(yè)。 定義：定義： 查找算法的平均查找長(zhǎng)度查找算法的平均查找長(zhǎng)度 (Average Search Length) 為確定記錄為確定記錄(jl)在查找表中的位置，需和給定值在查找表中的位置，需和給定值 進(jìn)行比較的關(guān)鍵字個(gè)數(shù)的期望值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)的期望值 其中其中: n 為表長(zhǎng)，為表長(zhǎng)，Pi 為查找表中第為查找表中第i個(gè)記錄個(gè)記錄(jl)的概率，的概率， 且且 Ci為找到該記錄為找到該

14、記錄(jl)時(shí)，曾和給定值時(shí)，曾和給定值 比較過(guò)的關(guān)鍵字的個(gè)數(shù)。比較過(guò)的關(guān)鍵字的個(gè)數(shù)。分析順序查找分析順序查找(ch zho)的時(shí)間性能。的時(shí)間性能。niiiCPASL111niiP第23頁(yè)/共169頁(yè)第二十三頁(yè)，共169頁(yè)。在等概率查找的情況在等概率查找的情況(qngkung)下，下， 順序表查找的平均查找長(zhǎng)度為：順序表查找的平均查找長(zhǎng)度為：對(duì)順序?qū)樞?shnx)表而言，表而言，Ci = n-i+1nPi121111n)i(nnASLnissASL = nP1 +(n-1)P2 + +2Pn-1+Pn第24頁(yè)/共169頁(yè)第二十四頁(yè)，共169頁(yè)。 若查找概率無(wú)法事先測(cè)定，則若查找概率無(wú)法事先

15、測(cè)定，則查找過(guò)程采取查找過(guò)程采取(ciq)的改進(jìn)辦法是，的改進(jìn)辦法是，在每次查找之后，將剛剛查找到的在每次查找之后，將剛剛查找到的記錄直接移至表尾的位置上。記錄直接移至表尾的位置上。在不等概率查找在不等概率查找(ch zho)的情況下，的情況下，ASLss 在在 PnPn-1P2P1時(shí)取極小值時(shí)取極小值第25頁(yè)/共169頁(yè)第二十五頁(yè)，共169頁(yè)。 上述順序查找表的查找算法簡(jiǎn)單，上述順序查找表的查找算法簡(jiǎn)單， 但平均查找長(zhǎng)度較大，但平均查找長(zhǎng)度較大，特別特別(tbi)不適用于表長(zhǎng)較大的查找表。不適用于表長(zhǎng)較大的查找表。 若以有序表表示靜態(tài)查找表，若以有序表表示靜態(tài)查找表，則查找過(guò)程則查找過(guò)程(g

16、uchng)可以基于可以基于“折折半半”進(jìn)行。進(jìn)行。二、有序查找二、有序查找(ch zho)表表第26頁(yè)/共169頁(yè)第二十六頁(yè)，共169頁(yè)。05 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 的查找的查找(ch zho)過(guò)程如下過(guò)程如下lowhighmidlow mid high midlow 指示查找區(qū)間的下界指示查找區(qū)間的下界(xi ji);high 指示查找區(qū)間的上界指示查找區(qū)間的上界;mid = (low+high)/2。第27頁(yè)/共169頁(yè)第二十七頁(yè)，共169頁(yè)

17、。int Search_Bin ( SSTable ST, KeyType key ) low = 1; high = ST.length; / 置區(qū)間初值置區(qū)間初值 while (low 50時(shí)，可得近似時(shí)，可得近似(jn s)結(jié)果結(jié)果 一般情況下，表長(zhǎng)為一般情況下，表長(zhǎng)為 n 的折半的折半查找的判定樹(shù)的深度和含有查找的判定樹(shù)的深度和含有 n 個(gè)個(gè)結(jié)點(diǎn)的完全結(jié)點(diǎn)的完全(wnqun)二叉樹(shù)的深二叉樹(shù)的深度相同。度相同。1) 1(log12112111nnnjnCnASLhjjniibs1) 1(log2nASLbs第30頁(yè)/共169頁(yè)第三十頁(yè)，共169頁(yè)。關(guān)鍵字關(guān)鍵字: A B C D E P

18、i: 0.2 0.3 0.05 0.3 0.15 Ci: 2 3 1 2 3 在不等概率查找的情況下，折半查找在不等概率查找的情況下，折半查找不是有序表最好不是有序表最好(zu ho)的查找方法的查找方法例如例如(lr):此時(shí)此時(shí)(c sh) ASL=20.2+30.3+10.05+20.3+30.15=2.4若改變?nèi)舾淖僀i的值的值 2 1 3 2 3則則 ASL=2 0.2+1 0.3+3 0.05+2 0.3+3 0.15=1.9三、靜態(tài)查找樹(shù)表三、靜態(tài)查找樹(shù)表第31頁(yè)/共169頁(yè)第三十一頁(yè)，共169頁(yè)。 使使 達(dá)最小的判定達(dá)最小的判定(pndng)樹(shù)稱(chēng)為最優(yōu)二叉樹(shù)，樹(shù)稱(chēng)為最優(yōu)二叉樹(shù)，其

19、中其中: 111niiCiqniiCipASL1111niiniiqp定義定義(dngy):第32頁(yè)/共169頁(yè)第三十二頁(yè)，共169頁(yè)。為計(jì)算為計(jì)算(j sun)方便，令方便，令 wi = pi選擇二叉樹(shù)的根結(jié)點(diǎn)，選擇二叉樹(shù)的根結(jié)點(diǎn)，使使 達(dá)最小達(dá)最小 111ijjhijjiwwP11)(iilhiswswswswP介紹介紹(jisho)一種次優(yōu)二叉樹(shù)的構(gòu)造方法一種次優(yōu)二叉樹(shù)的構(gòu)造方法:為便于計(jì)算，引入累計(jì)為便于計(jì)算，引入累計(jì)(li j)權(quán)值和權(quán)值和 并設(shè)并設(shè) wl-1 = 0 和和 swl-1 = 0，則推導(dǎo)可得則推導(dǎo)可得ijjiwsw1第33頁(yè)/共169頁(yè)第三十三頁(yè)，共169頁(yè)。j0123

20、4567wj02153435swjpjkeyA B C D E F G02381115 1823例如例如(lr):lh2118 124310 18h9608EC21Ah53lhG3013第34頁(yè)/共169頁(yè)第三十四頁(yè)，共169頁(yè)。ECGABDF所得所得(su d)次優(yōu)二叉樹(shù)如下所示次優(yōu)二叉樹(shù)如下所示: 查找比較查找比較(bjio)“總次數(shù)總次數(shù)” = 32+41+25+33 +14+33+25 = 52 查找比較查找比較(bjio)“總次數(shù)總次數(shù)” = 32+21+35+13 +34+23+35 = 59和折半查找相比較和折半查找相比較DBACFEG第35頁(yè)/共169頁(yè)第三十五頁(yè)，共169頁(yè)。

21、Status SecondOptimal(BiTree &T, ElemType R, float sw, int low, int high) / 由有序表由有序表Rlow.high及其累計(jì)權(quán)值表及其累計(jì)權(quán)值表sw / 遞歸構(gòu)造次優(yōu)查找樹(shù)遞歸構(gòu)造次優(yōu)查找樹(shù)T。 選擇選擇(xunz)最小的最小的Pi值值 if (!(T = (BiTree)malloc(sizeof(BiTNode) return ERROR; T-data = Ri; / 生成結(jié)點(diǎn)生成結(jié)點(diǎn)第36頁(yè)/共169頁(yè)第三十六頁(yè)，共169頁(yè)。if (i=low) T-lchild = NULL; / 左子樹(shù)空左子樹(shù)空else Seco

22、ndOptimal(T-lchild, R, sw, low, i-1); / 構(gòu)造構(gòu)造(guzo)左子樹(shù)左子樹(shù) if (i=high) T-rchild = NULL; / 右子樹(shù)空右子樹(shù)空 else SecondOptimal(T-rchild, R, sw, i+1, high); / 構(gòu)造構(gòu)造(guzo)右子樹(shù)右子樹(shù) return OK; / SecondOptimal第37頁(yè)/共169頁(yè)第三十七頁(yè)，共169頁(yè)。次優(yōu)查找樹(shù)采用次優(yōu)查找樹(shù)采用(ciyng)二叉鏈表的存儲(chǔ)結(jié)構(gòu)二叉鏈表的存儲(chǔ)結(jié)構(gòu)Status CreateSOSTre(SOSTree &T, SSTable ST) / 由有序

23、表由有序表 ST 構(gòu)造一棵次優(yōu)查找樹(shù)構(gòu)造一棵次優(yōu)查找樹(shù) T。 / ST 的數(shù)據(jù)元素的數(shù)據(jù)元素(yun s)含有權(quán)域含有權(quán)域 weight if (ST.length = 0) T = NULL; else FindSW(sw, ST); / 按照有序表按照有序表 ST 中各數(shù)據(jù)元素中各數(shù)據(jù)元素(yun s) / 的的 weight 值求累計(jì)權(quán)值表值求累計(jì)權(quán)值表 SecondOpiamal(T, ST.elem, sw, 1, ST.length); return OK; / CreatSOSTree第38頁(yè)/共169頁(yè)第三十八頁(yè)，共169頁(yè)。四、索引四、索引(suyn)順序表順序表以索引順序表

24、表示以索引順序表表示(biosh)(biosh)靜態(tài)靜態(tài)查找表，查找表，searchsearch操作可用分塊查找來(lái)操作可用分塊查找來(lái)實(shí)現(xiàn)。實(shí)現(xiàn)。分塊查找又稱(chēng)索引順序查找，這是順?lè)謮K查找又稱(chēng)索引順序查找，這是順序查找的一種改進(jìn)方法。在此查找方序查找的一種改進(jìn)方法。在此查找方法中，除表本身以外，尚需建立一個(gè)法中，除表本身以外，尚需建立一個(gè)“索引表索引表”。第39頁(yè)/共169頁(yè)第三十九頁(yè)，共169頁(yè)。例如(lr(lr) 表中含有1818個(gè)元素，可分成三個(gè)子表。對(duì)每個(gè)子表（或稱(chēng)塊）建立(jinl)(jinl)一個(gè)索引項(xiàng)，其中包括兩項(xiàng)內(nèi)容：關(guān)鍵字項(xiàng)（其值為該子表內(nèi)的最大關(guān)鍵字）和項(xiàng)指針（指示該子表的第一

25、個(gè)元素在表中位置）。索引索引(suyn)(suyn)表表最大關(guān)鍵字起始地址 22 48 8617 13221213 8 9 20334244382448605874498653第40頁(yè)/共169頁(yè)第四十頁(yè)，共169頁(yè)。 索引表按關(guān)鍵字有序，故表或者有 序 ， 或 者 分 塊 有 序 。 所 謂(suwi)“(suwi)“分塊有序” ” 是指一個(gè)子表中所有元素的關(guān)鍵字均大于前一個(gè)子表的最大關(guān)鍵字。 第41頁(yè)/共169頁(yè)第四十一頁(yè)，共169頁(yè)。1）由索引確定記錄所在）由索引確定記錄所在(suzi)區(qū)間；區(qū)間；2）在順序表的某個(gè)區(qū)間內(nèi)進(jìn)行）在順序表的某個(gè)區(qū)間內(nèi)進(jìn)行(jnxng)查找。查找。注意：索引

26、可以根據(jù)查找表的特點(diǎn)來(lái)構(gòu)造。注意：索引可以根據(jù)查找表的特點(diǎn)來(lái)構(gòu)造?？梢?jiàn)，可見(jiàn)， 索引順序查找索引順序查找的過(guò)程也是一個(gè)的過(guò)程也是一個(gè)“縮小區(qū)間縮小區(qū)間”的查找過(guò)程。的查找過(guò)程。第42頁(yè)/共169頁(yè)第四十二頁(yè)，共169頁(yè)。索引順序索引順序(shnx)查找的平均查找長(zhǎng)查找的平均查找長(zhǎng)度度 = 查找查找“索引索引”的平均查找長(zhǎng)度的平均查找長(zhǎng)度 + 查找查找“順序順序(shnx)表表”的平均的平均查找長(zhǎng)度查找長(zhǎng)度第43頁(yè)/共169頁(yè)第四十三頁(yè)，共169頁(yè)。第44頁(yè)/共169頁(yè)第四十四頁(yè)，共169頁(yè)。 (n) (1) (n) (1) (nlogn)綜合上一節(jié)討論的幾種查找綜合上一節(jié)討論的幾種查找(ch

27、zho)表的特性：表的特性：查找查找 插入插入(ch r) (ch r) 刪除刪除無(wú)序順序表無(wú)序順序表 無(wú)序線(xiàn)性鏈表無(wú)序線(xiàn)性鏈表有序順序表有序順序表 有序線(xiàn)性鏈表有序線(xiàn)性鏈表 靜態(tài)靜態(tài)(jngti)查找樹(shù)表查找樹(shù)表 (n) (n) (logn) (n) (logn) (1) (1) (n) (1) (nlogn)第45頁(yè)/共169頁(yè)第四十五頁(yè)，共169頁(yè)。1）從查找性能看，最好情況）從查找性能看，最好情況(qngkung)能達(dá)能達(dá) (logn)，此時(shí)要求表有序；，此時(shí)要求表有序；2）從插入和刪除的性能看，最好）從插入和刪除的性能看，最好 情況能達(dá)情況能達(dá)(1)，此時(shí)，此時(shí)(c sh)要求存儲(chǔ)要

28、求存儲(chǔ) 結(jié)構(gòu)是鏈表。結(jié)構(gòu)是鏈表。第46頁(yè)/共169頁(yè)第四十六頁(yè)，共169頁(yè)。ADT DynamicSearchTable 抽象數(shù)據(jù)類(lèi)型動(dòng)態(tài)查找抽象數(shù)據(jù)類(lèi)型動(dòng)態(tài)查找(ch zho)表的定義如下：表的定義如下：數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象(duxing)D：數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系R： 數(shù)據(jù)元素同屬數(shù)據(jù)元素同屬(tn sh)一個(gè)集合。一個(gè)集合。D是具有相同特性的數(shù)據(jù)是具有相同特性的數(shù)據(jù)元素的集合。元素的集合。每個(gè)數(shù)據(jù)元素含有類(lèi)型相同每個(gè)數(shù)據(jù)元素含有類(lèi)型相同的關(guān)鍵字，的關(guān)鍵字， 可唯一標(biāo)識(shí)數(shù)可唯一標(biāo)識(shí)數(shù)據(jù)元素。據(jù)元素。第47頁(yè)/共169頁(yè)第四十七頁(yè)，共169頁(yè)。InitDSTable(&DT)基本操作基本操作P：Des

29、troyDSTable(&DT)SearchDSTable(DT, key);InsertDSTable(&DT, e);DeleteDSTable(&T, key);TraverseDSTable(DT, Visit();nextADT DynamicSearchTable第48頁(yè)/共169頁(yè)第四十八頁(yè)，共169頁(yè)。操作操作(cozu)結(jié)果：結(jié)果：構(gòu)造一個(gè)構(gòu)造一個(gè)(y )空的動(dòng)態(tài)查找表空的動(dòng)態(tài)查找表DT。InitDSTable(&DT);第49頁(yè)/共169頁(yè)第四十九頁(yè)，共169頁(yè)。銷(xiāo)毀銷(xiāo)毀(xiohu)動(dòng)態(tài)查找表動(dòng)態(tài)查找表DT。DestroyDSTable(&DT);初始條件：初始條件： 操

30、作操作(cozu)結(jié)果：結(jié)果：動(dòng)態(tài)動(dòng)態(tài)(dngti)查找表查找表DT存在；存在；第50頁(yè)/共169頁(yè)第五十頁(yè)，共169頁(yè)。若若DT中存在中存在(cnzi)其關(guān)鍵其關(guān)鍵字等于字等于 key的數(shù)據(jù)元素，則的數(shù)據(jù)元素，則函數(shù)值為該元素的值或在表函數(shù)值為該元素的值或在表中的位置，否則為中的位置，否則為“空空”。SearchDSTable(DT, key);初始條件：初始條件：操作操作(cozu)結(jié)果：結(jié)果：動(dòng)態(tài)查找動(dòng)態(tài)查找(ch zho)表表DT存存在，在，key為和關(guān)鍵字類(lèi)型相同的給為和關(guān)鍵字類(lèi)型相同的給定值；定值；第51頁(yè)/共169頁(yè)第五十一頁(yè)，共169頁(yè)。動(dòng)態(tài)查找動(dòng)態(tài)查找(ch zho)表表DT

31、存在，存在， e 為待插入的數(shù)據(jù)元素；為待插入的數(shù)據(jù)元素；InsertDSTable(&DT, e);初始條件：初始條件：操作操作(cozu)結(jié)果：結(jié)果：若若DT中不存在其關(guān)鍵字中不存在其關(guān)鍵字等于等于 e.key 的的 數(shù)據(jù)數(shù)據(jù)(shj)元素，元素，則插入則插入 e 到到DT。第52頁(yè)/共169頁(yè)第五十二頁(yè)，共169頁(yè)。動(dòng)態(tài)動(dòng)態(tài)(dngti)查找表查找表DT存在，存在，key為和關(guān)鍵字類(lèi)型相同的給為和關(guān)鍵字類(lèi)型相同的給定值；定值；DeleteDSTable(&T, key);初始條件：初始條件：操作操作(cozu)結(jié)果：結(jié)果：若若DT中存在中存在(cnzi)其關(guān)鍵其關(guān)鍵字等于字等于key的數(shù)

32、據(jù)元素，則的數(shù)據(jù)元素，則刪刪除之。除之。第53頁(yè)/共169頁(yè)第五十三頁(yè)，共169頁(yè)。動(dòng)態(tài)動(dòng)態(tài)(dngti)查找表查找表DT存在，存在，Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)；是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)；TraverseDSTable(DT, Visit();初始條件：初始條件：操作操作(cozu)結(jié)果：結(jié)果：按某種次序按某種次序(cx)對(duì)對(duì)DT的每個(gè)結(jié)的每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)點(diǎn)調(diào)用函數(shù) Visit() 一次且至一次且至多一次。一旦多一次。一旦 Visit() 失敗，失敗，則操作失敗。則操作失敗。第54頁(yè)/共169頁(yè)第五十四頁(yè)，共169頁(yè)。一、二叉排序一、二叉排序(pi x)樹(shù)（二叉查找樹(shù)）樹(shù)（二叉查找樹(shù)）二、

33、二叉平衡二、二叉平衡(pnghng)樹(shù)樹(shù)三、三、B - 樹(shù)樹(shù)四、四、B+樹(shù)樹(shù)五、鍵五、鍵 樹(shù)樹(shù)第55頁(yè)/共169頁(yè)第五十五頁(yè)，共169頁(yè)。1定義定義(dngy)2查找查找(ch zho)算法算法3插入插入(ch r)算法算法4刪除算法刪除算法5查找性能的分析查找性能的分析一、二叉排序樹(shù)一、二叉排序樹(shù)（二叉查找樹(shù)）（二叉查找樹(shù)）第56頁(yè)/共169頁(yè)第五十六頁(yè)，共169頁(yè)。（1）若它的左子樹(shù)不空，則左子樹(shù)上）若它的左子樹(shù)不空，則左子樹(shù)上 所有所有(suyu)結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值； 二叉排序樹(shù)或者是一棵空樹(shù)；或者二叉排序樹(shù)或者是一棵空樹(shù)；或者是具有是具有(jyu)如下特

34、性的二叉樹(shù)：如下特性的二叉樹(shù)：（3）它的左、右子樹(shù)也都分別）它的左、右子樹(shù)也都分別(fnbi)是二叉是二叉 排序樹(shù)。排序樹(shù)。（2）若它的右子樹(shù)不空，則右子樹(shù)上）若它的右子樹(shù)不空，則右子樹(shù)上 所有所有結(jié)點(diǎn)的值結(jié)點(diǎn)的值均大于均大于根結(jié)點(diǎn)的值；根結(jié)點(diǎn)的值；1 1定義：定義：第57頁(yè)/共169頁(yè)第五十七頁(yè)，共169頁(yè)。503080209010854035252388例如例如(lr):是二叉排序是二叉排序(pi x)樹(shù)樹(shù)66不不第58頁(yè)/共169頁(yè)第五十八頁(yè)，共169頁(yè)。 通常，取二叉鏈表作為通常，取二叉鏈表作為(zuwi)二叉排序樹(shù)的存儲(chǔ)二叉排序樹(shù)的存儲(chǔ)結(jié)構(gòu)結(jié)構(gòu)typedef struct BiTNo

35、de / 結(jié)點(diǎn)結(jié)構(gòu) struct BiTNode *lchild, *rchild; / 左右孩子(hi zi)指針 BiTNode, *BiTree;TElemType data;第59頁(yè)/共169頁(yè)第五十九頁(yè)，共169頁(yè)。1）若給定）若給定(i dn)值等于根結(jié)值等于根結(jié)點(diǎn)的關(guān)鍵字，則查找成功；點(diǎn)的關(guān)鍵字，則查找成功；2）若給定）若給定(i dn)值小于根結(jié)值小于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在左子樹(shù)上進(jìn)點(diǎn)的關(guān)鍵字，則繼續(xù)在左子樹(shù)上進(jìn)行查找；行查找；3）若給定）若給定(i dn)值大于根結(jié)值大于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在右子樹(shù)上進(jìn)點(diǎn)的關(guān)鍵字，則繼續(xù)在右子樹(shù)上進(jìn)行查找。行查找。否則否則(fuz)若二叉

36、排序樹(shù)若二叉排序樹(shù)為空為空，則查找不成功；，則查找不成功；第60頁(yè)/共169頁(yè)第六十頁(yè)，共169頁(yè)。50308020908540358832例如例如(lr):二叉排序二叉排序(pi x)樹(shù)樹(shù)查找查找(ch zho)關(guān)鍵字關(guān)鍵字= 50 ,505035 ,503040355090 ,50809095 第61頁(yè)/共169頁(yè)第六十一頁(yè)，共169頁(yè)。從上述查找過(guò)程從上述查找過(guò)程(guchng)可見(jiàn)，可見(jiàn)，在查找過(guò)程在查找過(guò)程(guchng)中，生成了一條查找路徑中，生成了一條查找路徑: 從根結(jié)點(diǎn)出發(fā)，沿著左分支從根結(jié)點(diǎn)出發(fā)，沿著左分支(fnzh)或右或右分支分支(fnzh)逐層向下直至關(guān)鍵字等于給定逐

37、層向下直至關(guān)鍵字等于給定值的結(jié)點(diǎn)值的結(jié)點(diǎn);或者或者 從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支逐層向下直至指針指向空樹(shù)為止。逐層向下直至指針指向空樹(shù)為止。 查找成功查找成功 查找不成功查找不成功第62頁(yè)/共169頁(yè)第六十二頁(yè)，共169頁(yè)。算法算法(sun f)描述如下：描述如下：Status SearchBST (BiTree T, KeyType key, BiTree f, BiTree &p ) / 在根指針在根指針 T 所指二叉排序樹(shù)中遞歸地查所指二叉排序樹(shù)中遞歸地查找找(ch zho)其其 / 關(guān)鍵字等于關(guān)鍵字等于 key 的數(shù)據(jù)元素，若查找的數(shù)據(jù)元素，若查找(

38、ch zho)成功，成功， / 則返回指針則返回指針 p 指向該數(shù)據(jù)元素的結(jié)點(diǎn)，指向該數(shù)據(jù)元素的結(jié)點(diǎn)，并返回并返回 / 函數(shù)值為函數(shù)值為 TRUE; / SearchBST 否則表明查找不成功否則表明查找不成功(chnggng)，返回，返回 / 指針指針 p 指向查找路徑上訪(fǎng)問(wèn)的最后一個(gè)結(jié)點(diǎn)，指向查找路徑上訪(fǎng)問(wèn)的最后一個(gè)結(jié)點(diǎn)， / 并返回函數(shù)值為并返回函數(shù)值為FALSE, 指針指針 f 指向當(dāng)前訪(fǎng)問(wèn)指向當(dāng)前訪(fǎng)問(wèn) / 的結(jié)點(diǎn)的雙親，其初始調(diào)用值為的結(jié)點(diǎn)的雙親，其初始調(diào)用值為NULL第63頁(yè)/共169頁(yè)第六十三頁(yè)，共169頁(yè)。if (!T)else if ( EQ(key, T-data.key)

39、 ) else if ( LT(key, T-data.key) ) else p = f; return FALSE; / 查找查找(ch zho)不成功不成功 p = T; return TRUE; / 查找查找(ch zho)成功成功SearchBST (T-lchild, key, T, p ); / 在左子樹(shù)中繼續(xù)在左子樹(shù)中繼續(xù)(jx)查找查找SearchBST (T-rchild, key, T, p ); / 在右子樹(shù)中繼續(xù)查找在右子樹(shù)中繼續(xù)查找第64頁(yè)/共169頁(yè)第六十四頁(yè)，共169頁(yè)。30201040352523fT設(shè)設(shè) key = 48fTfT22pfTfTTTTfffp第

40、65頁(yè)/共169頁(yè)第六十五頁(yè)，共169頁(yè)。根據(jù)動(dòng)態(tài)(dngti)查找表的定義，“插入”操作在查找不成功時(shí)才進(jìn)行; 若二叉排序樹(shù)為空樹(shù)，則新插入的結(jié)點(diǎn)為新的根結(jié)點(diǎn)；否則，新插入的結(jié)點(diǎn)必為一個(gè)新的葉子結(jié)點(diǎn)，其插入位置(wi zhi)由查找過(guò)程得到。第66頁(yè)/共169頁(yè)第六十六頁(yè)，共169頁(yè)。Status Insert BST(BiTree &T, ElemType e) / 當(dāng)二叉排序樹(shù)中不存在關(guān)鍵字等于當(dāng)二叉排序樹(shù)中不存在關(guān)鍵字等于 e.key 的的 / 數(shù)據(jù)元素時(shí)，插入數(shù)據(jù)元素時(shí)，插入(ch r)元素值為元素值為 e 的結(jié)的結(jié)點(diǎn)，并返點(diǎn)，并返 / 回回 TRUE; 否則，不進(jìn)行插入否則，不進(jìn)行

41、插入(ch r)并返并返回回FALSE if (!SearchBST ( T, e.key, NULL, p ) else return FALSE; / Insert BST 第67頁(yè)/共169頁(yè)第六十七頁(yè)，共169頁(yè)。s = (BiTree) malloc (sizeof (BiTNode); / 為新結(jié)點(diǎn)分配為新結(jié)點(diǎn)分配(fnpi)空間空間s-data = e; s-lchild = s-rchild = NULL; if ( !p ) T = s; / 插入插入(ch r) s 為新的根結(jié)點(diǎn)為新的根結(jié)點(diǎn)else if ( LT(e.key, p-data.key) ) p-lchild

42、 = s; / 插入插入(ch r) *s 為為 *p 的左孩子的左孩子else p-rchild = s; / 插入插入(ch r) *s 為為 *p 的的右孩子右孩子return TRUE; / 插入成功插入成功第68頁(yè)/共169頁(yè)第六十八頁(yè)，共169頁(yè)。（1）被刪除）被刪除(shnch)的結(jié)點(diǎn)是葉子；的結(jié)點(diǎn)是葉子；（2）被刪除）被刪除(shnch)的結(jié)點(diǎn)只有左子樹(shù)或者只有右子樹(shù)；的結(jié)點(diǎn)只有左子樹(shù)或者只有右子樹(shù)；（3）被刪除）被刪除(shnch)的結(jié)點(diǎn)既有左子樹(shù)，也有右子樹(shù)。的結(jié)點(diǎn)既有左子樹(shù)，也有右子樹(shù)。可分三種情況可分三種情況(qngkung)討論：討論： 和插入相反，刪除和插入相反，刪

43、除(shnch)在查找成功之后進(jìn)在查找成功之后進(jìn)行，并且要求在刪除行，并且要求在刪除(shnch)二叉排序樹(shù)上某個(gè)二叉排序樹(shù)上某個(gè)結(jié)點(diǎn)之后，仍然保持二叉排序樹(shù)的特性。結(jié)點(diǎn)之后，仍然保持二叉排序樹(shù)的特性。第69頁(yè)/共169頁(yè)第六十九頁(yè)，共169頁(yè)。50308020908540358832（1）被刪除的結(jié)點(diǎn)）被刪除的結(jié)點(diǎn)(ji din)是葉子結(jié)點(diǎn)是葉子結(jié)點(diǎn)(ji din)例如例如(lr):被刪關(guān)鍵字被刪關(guān)鍵字 = 2088其雙親其雙親(shungqn)結(jié)點(diǎn)中相應(yīng)指針域的值改為結(jié)點(diǎn)中相應(yīng)指針域的值改為“空空”第70頁(yè)/共169頁(yè)第七十頁(yè)，共169頁(yè)。50308020908540358832（2）被刪

44、的結(jié)點(diǎn)）被刪的結(jié)點(diǎn)(ji din)只有左子樹(shù)或只有只有左子樹(shù)或只有右子樹(shù)右子樹(shù) 其雙親其雙親(shungqn)結(jié)點(diǎn)的相應(yīng)指針域的值結(jié)點(diǎn)的相應(yīng)指針域的值改為改為 “指向被刪除結(jié)點(diǎn)的左子樹(shù)或右子樹(shù)指向被刪除結(jié)點(diǎn)的左子樹(shù)或右子樹(shù)”。被刪關(guān)鍵字被刪關(guān)鍵字 = 4080第71頁(yè)/共169頁(yè)第七十一頁(yè)，共169頁(yè)。50308020908540358832（3）被刪除）被刪除(shnch)的結(jié)點(diǎn)既有左子樹(shù)，也有右子樹(shù)的結(jié)點(diǎn)既有左子樹(shù)，也有右子樹(shù)4040以其前驅(qū)替代之，然以其前驅(qū)替代之，然后再刪除后再刪除(shnch)該前驅(qū)結(jié)點(diǎn)該前驅(qū)結(jié)點(diǎn)被刪結(jié)點(diǎn)被刪結(jié)點(diǎn)(ji din)前驅(qū)結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn)被刪關(guān)鍵字被刪關(guān)鍵字 =

45、 50以中序遍歷排好，20-30-32-35-40-50-80-85-88-90第72頁(yè)/共169頁(yè)第七十二頁(yè)，共169頁(yè)。Status DeleteBST (BiTree &T, KeyType key ) / 若二叉排序樹(shù)若二叉排序樹(shù) T 中存在其關(guān)鍵字等于中存在其關(guān)鍵字等于 key 的的 / 數(shù)據(jù)數(shù)據(jù)(shj)元素，則刪除該數(shù)據(jù)元素，則刪除該數(shù)據(jù)(shj)元素結(jié)點(diǎn)，并返回元素結(jié)點(diǎn)，并返回 / 函數(shù)值函數(shù)值 TRUE，否則返回函數(shù)值，否則返回函數(shù)值 FALSE if (!T) return FALSE; / 不存在關(guān)鍵字等于不存在關(guān)鍵字等于key的數(shù)據(jù)的數(shù)據(jù)(shj)元素元素 else /

46、 DeleteBST算法算法(sun f)描述如下：描述如下： 第73頁(yè)/共169頁(yè)第七十三頁(yè)，共169頁(yè)。if ( EQ (key, T-data.key) ) / 找到關(guān)鍵字等于找到關(guān)鍵字等于key的數(shù)據(jù)的數(shù)據(jù)(shj)元素元素else if ( LT (key, T-data.key) ) else Delete (T); return TRUE; DeleteBST ( T-lchild, key ); / 繼續(xù)繼續(xù)(jx)在左子樹(shù)中進(jìn)行查找在左子樹(shù)中進(jìn)行查找DeleteBST ( T-rchild, key ); / 繼續(xù)繼續(xù)(jx)在右子樹(shù)中進(jìn)行查找在右子樹(shù)中進(jìn)行查找第74頁(yè)/共1

47、69頁(yè)第七十四頁(yè)，共169頁(yè)。void Delete ( BiTree &p ) / 從二叉排序從二叉排序(pi x)樹(shù)中刪除結(jié)點(diǎn)樹(shù)中刪除結(jié)點(diǎn) p， / 并重接它的左子樹(shù)或右子樹(shù)并重接它的左子樹(shù)或右子樹(shù) if (!p-rchild) else if (!p-lchild) else / Delete其中其中(qzhng)刪除操作過(guò)程如下所描述：刪除操作過(guò)程如下所描述： 第75頁(yè)/共169頁(yè)第七十五頁(yè)，共169頁(yè)。 / 右子樹(shù)為空樹(shù)則只需重接它的左子樹(shù)右子樹(shù)為空樹(shù)則只需重接它的左子樹(shù)q = p; p = p-lchild; free(q);pp此處p應(yīng)該(ynggi)換為f的左孩子或右，根據(jù)p為

48、f左還是右而定第76頁(yè)/共169頁(yè)第七十六頁(yè)，共169頁(yè)。/ 左子樹(shù)為空樹(shù)只需重接它的右子樹(shù)左子樹(shù)為空樹(shù)只需重接它的右子樹(shù)q = p; p = p-rchild; free(q);pp第77頁(yè)/共169頁(yè)第七十七頁(yè)，共169頁(yè)。q = p; s = p-lchild;while (!s-rchild) q = s; s = s-rchild; / s 指向被刪結(jié)點(diǎn)指向被刪結(jié)點(diǎn)(ji din)的前驅(qū)的前驅(qū)/ 左右左右(zuyu)子樹(shù)均不空子樹(shù)均不空p-data = s-data;if (q != p ) q-rchild = s-lchild; else q-lchild = s-lchild;

49、 / 重接重接*q的左子樹(shù)的左子樹(shù)free(s);pqs第78頁(yè)/共169頁(yè)第七十八頁(yè)，共169頁(yè)。 對(duì)于每一棵特定的二叉排序樹(shù)，均可按照平均查找對(duì)于每一棵特定的二叉排序樹(shù)，均可按照平均查找(ch zho)長(zhǎng)長(zhǎng)度的定義來(lái)求它的度的定義來(lái)求它的 ASL 值，顯然，由值相同的值，顯然，由值相同的 n 個(gè)關(guān)鍵字，構(gòu)造所得的個(gè)關(guān)鍵字，構(gòu)造所得的不同形態(tài)的各棵二叉排序樹(shù)的平均查找不同形態(tài)的各棵二叉排序樹(shù)的平均查找(ch zho)長(zhǎng)長(zhǎng) 度的值不同，甚至可度的值不同，甚至可能差別很大。能差別很大。第79頁(yè)/共169頁(yè)第七十九頁(yè)，共169頁(yè)。由關(guān)鍵字序列由關(guān)鍵字序列(xli) 3，1，2，5，4構(gòu)造而得的二叉

50、排序樹(shù)構(gòu)造而得的二叉排序樹(shù)由關(guān)鍵字序列由關(guān)鍵字序列 1，2，3，4，5構(gòu)造構(gòu)造(guzo)而得的二叉排序而得的二叉排序樹(shù)，樹(shù)，2134535412ASL =（1+2+3+4+5）/ 5 = 3ASL =（1+2+3+2+3）/ 5 = 2.2第80頁(yè)/共169頁(yè)第八十頁(yè)，共169頁(yè)。 下面(xi mian)討論平均情況: 不失一般性，假設(shè)長(zhǎng)度不失一般性，假設(shè)長(zhǎng)度(chngd)為為 n 的序列中有的序列中有 k 個(gè)關(guān)鍵字小于第一個(gè)關(guān)鍵個(gè)關(guān)鍵字小于第一個(gè)關(guān)鍵字，則必有字，則必有 n-k-1 個(gè)關(guān)鍵字大于第一個(gè)個(gè)關(guān)鍵字大于第一個(gè)關(guān)鍵字關(guān)鍵字,由它構(gòu)造的二叉排序樹(shù)由它構(gòu)造的二叉排序樹(shù)n-k-1k的平均

51、的平均(pngjn)查找長(zhǎng)度是查找長(zhǎng)度是 n 和和 k 的函數(shù)的函數(shù)P(n, k) ( 0 k n-1 )第81頁(yè)/共169頁(yè)第八十一頁(yè)，共169頁(yè)。 假設(shè)假設(shè) n n 個(gè)關(guān)鍵字可能出現(xiàn)的個(gè)關(guān)鍵字可能出現(xiàn)的 n! n! 種排列種排列的可能性相同，則含的可能性相同，則含 n n 個(gè)關(guān)鍵字的二叉排個(gè)關(guān)鍵字的二叉排序樹(shù)的平均序樹(shù)的平均(pngjn)(pngjn)查找長(zhǎng)度查找長(zhǎng)度10),(1)(nkknPnnPASLniiniiiCnCpknP111),(在等概率查找在等概率查找(ch zho)(ch zho)的情況下，的情況下，第82頁(yè)/共169頁(yè)第八十二頁(yè)，共169頁(yè)。RiLirootniiCCC

52、nCnknP11),(1)1)1()(1()1)(11knPknkPkn)1()1()(11knPknkPkn第83頁(yè)/共169頁(yè)第八十三頁(yè)，共169頁(yè)。由此可類(lèi)似于解差分可類(lèi)似于解差分(ch fn)方程，此遞歸方程有解：方程，此遞歸方程有解：CnnnnPlog12)(10) 1() 1()(111)(nkknPknkPknnnP112)(21nkkPkn第84頁(yè)/共169頁(yè)第八十四頁(yè)，共169頁(yè)。何謂何謂(hwi)“二叉平衡二叉平衡樹(shù)樹(shù)”？ 二叉平衡樹(shù)的查找二叉平衡樹(shù)的查找(ch zho)性能分析性能分析 如何如何(rh)構(gòu)造構(gòu)造“二叉平衡樹(shù)二叉平衡樹(shù)”二、二叉平衡樹(shù)第85頁(yè)/共169頁(yè)第八

53、十五頁(yè)，共169頁(yè)。 二叉平衡樹(shù)是二叉查找樹(shù)的另一種二叉平衡樹(shù)是二叉查找樹(shù)的另一種(y zhn)形式，其特點(diǎn)為：形式，其特點(diǎn)為： 樹(shù)中每個(gè)結(jié)點(diǎn)樹(shù)中每個(gè)結(jié)點(diǎn)(ji din)的左、右子樹(shù)的左、右子樹(shù)深度之差的絕對(duì)值不大于深度之差的絕對(duì)值不大于1 。例如例如(lr):1RLhh548254821是平衡樹(shù)是平衡樹(shù)不是平衡樹(shù)不是平衡樹(shù)第86頁(yè)/共169頁(yè)第八十六頁(yè)，共169頁(yè)。 構(gòu)造二叉平衡（查找）樹(shù)的方法是：構(gòu)造二叉平衡（查找）樹(shù)的方法是：在插入過(guò)程中，采用平衡旋轉(zhuǎn)在插入過(guò)程中，采用平衡旋轉(zhuǎn)(xunzhun)技術(shù)。技術(shù)。例如例如:依次依次(yc)插入的關(guān)鍵字為插入的關(guān)鍵字為5, 4, 2, 8, 6,

54、 95424258665842向右旋轉(zhuǎn)向右旋轉(zhuǎn)(xunzhun)一次一次先向右旋轉(zhuǎn)先向右旋轉(zhuǎn)再向左旋轉(zhuǎn)再向左旋轉(zhuǎn)第87頁(yè)/共169頁(yè)第八十七頁(yè)，共169頁(yè)。426589642895向左旋轉(zhuǎn)(xunzhun)一次繼續(xù)繼續(xù)(jx)插入關(guān)鍵插入關(guān)鍵字字 9第88頁(yè)/共169頁(yè)第八十八頁(yè)，共169頁(yè)。 在 平 衡 樹(shù) 上 進(jìn) 行 查 找 的 過(guò) 程在 平 衡 樹(shù) 上 進(jìn) 行 查 找 的 過(guò) 程(guchng)和二叉排序樹(shù)相同，因此，和二叉排序樹(shù)相同，因此，查找過(guò)程查找過(guò)程(guchng)中和給定值進(jìn)行比中和給定值進(jìn)行比較的關(guān)鍵字的個(gè)數(shù)不超過(guò)平衡較的關(guān)鍵字的個(gè)數(shù)不超過(guò)平衡 樹(shù)的深樹(shù)的深度。度。平衡平衡(

55、pnghng)樹(shù)的查找性能分析：樹(shù)的查找性能分析： 問(wèn)：含 n 個(gè)關(guān)鍵字的二叉平衡樹(shù)可能達(dá)到(d do)的最大深度是多少？第89頁(yè)/共169頁(yè)第八十九頁(yè)，共169頁(yè)。n = 0空樹(shù)最大深度最大深度(shnd)(shnd)為為 0 0n = 1最大深度最大深度(shnd)為為 1n = 2最大深度最大深度(shnd)(shnd)為為 2 2n = 4最大深度為最大深度為 3n = 7最大深度為最大深度為 4先看幾個(gè)具體情況:第90頁(yè)/共169頁(yè)第九十頁(yè)，共169頁(yè)。反過(guò)來(lái)問(wèn)，深度為反過(guò)來(lái)問(wèn)，深度為 h 的二叉平衡樹(shù)中所的二叉平衡樹(shù)中所含結(jié)點(diǎn)含結(jié)點(diǎn)(ji din)的最小值的最小值 Nh 是多少？是

56、多少？h = 0N0 = 0h = 1h = 2h = 3一般一般(ybn)情況下，情況下，N1 = 1N2 = 2N3 = 4Nh = Nh-1 + Nh-2 + 1利用利用(lyng)歸納法可證得，歸納法可證得，Nh = Fh+2 - 1第91頁(yè)/共169頁(yè)第九十一頁(yè)，共169頁(yè)。 因此，在二叉平衡樹(shù)上進(jìn)行查找時(shí)，因此，在二叉平衡樹(shù)上進(jìn)行查找時(shí)，查找過(guò)程查找過(guò)程(guchng)中和給定值進(jìn)行比中和給定值進(jìn)行比較的關(guān)鍵字的個(gè)數(shù)和較的關(guān)鍵字的個(gè)數(shù)和 log(n) 相當(dāng)。相當(dāng)。 由 此 推 得 ， 深 度 為由 此 推 得 ， 深 度 為 h 的 二 叉 平 衡的 二 叉 平 衡(pnghng)

57、樹(shù)中所含結(jié)點(diǎn)的最小值樹(shù)中所含結(jié)點(diǎn)的最小值 Nh = h+2/5 - 1 反之，含有反之，含有 n 個(gè)結(jié)點(diǎn)的二叉平衡樹(shù)能達(dá)到個(gè)結(jié)點(diǎn)的二叉平衡樹(shù)能達(dá)到(d do)的最大深度的最大深度 hn = log(5 (n+1) - 2 第92頁(yè)/共169頁(yè)第九十二頁(yè)，共169頁(yè)。1定義定義(dngy)2查找查找(ch zho)過(guò)程過(guò)程3插入插入(ch r)操作操作4刪除操作刪除操作5查找性能的分析查找性能的分析三、三、 B - 樹(shù)樹(shù)第93頁(yè)/共169頁(yè)第九十三頁(yè)，共169頁(yè)。1B-樹(shù)的定義樹(shù)的定義(dngy)B-樹(shù)是一種樹(shù)是一種 平衡平衡(pnghng) 的的 多路多路 查找查找 樹(shù)：樹(shù)： root 50

58、15 71 84 3 8 20 26 43 56 62 78 89 96第94頁(yè)/共169頁(yè)第九十四頁(yè)，共169頁(yè)。 在在 m 階的階的B-樹(shù)上，每個(gè)非終端結(jié)點(diǎn)可能含樹(shù)上，每個(gè)非終端結(jié)點(diǎn)可能含有：有： n 個(gè)關(guān)鍵字個(gè)關(guān)鍵字 Ki（1 in） nm n 個(gè)指向個(gè)指向(zh xin)記錄的指針記錄的指針 Di（1in） n+1 個(gè)指向個(gè)指向(zh xin)子樹(shù)的指針子樹(shù)的指針 Ai（0in）;多叉樹(shù)的特性(txng)第95頁(yè)/共169頁(yè)第九十五頁(yè)，共169頁(yè)。typedef struct BTNode int keynum; / 結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)，結(jié)點(diǎn)大小結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)，結(jié)點(diǎn)大小 struct

59、BTNode *parent; / 指向雙親結(jié)點(diǎn)的指針指向雙親結(jié)點(diǎn)的指針 KeyType keym+1; / 關(guān)鍵字（關(guān)鍵字（0號(hào)單元不用號(hào)單元不用(byng)） struct BTNode *ptrm+1; / 子樹(shù)指針向量子樹(shù)指針向量 Record *recptrm+1; / 記錄指針向量記錄指針向量 BTNode, *BTree; / B樹(shù)結(jié)點(diǎn)和樹(shù)結(jié)點(diǎn)和B樹(shù)的類(lèi)型樹(shù)的類(lèi)型B-樹(shù)結(jié)構(gòu)的樹(shù)結(jié)構(gòu)的C語(yǔ)言描述語(yǔ)言描述(mio sh)如下如下:第96頁(yè)/共169頁(yè)第九十六頁(yè)，共169頁(yè)。非葉結(jié)點(diǎn)中的多個(gè)非葉結(jié)點(diǎn)中的多個(gè)(du (du )關(guān)鍵字關(guān)鍵字均自小至大有序排列，即：均自小至大有序排列，即：K

60、1 K2 K1 K2 Kn; keynum; i=Search(p, K); / 在p-key1.keynum中查找 i ， / p-keyi=Kkeyi+1 if (i0 & p-keyi=K) found=TRUE; else q=p; p=p-ptri; / q 指示 p 的雙親(shungqn) if (found) return (p,i,1); / 查找成功 else return (q,i,0); / 查找不成功第102頁(yè)/共169頁(yè)第一百零二頁(yè)，共169頁(yè)。在查找不成功之后(zhhu)，需進(jìn)行插入。顯然，關(guān)鍵字插入的位置必定在最下層的非葉結(jié)點(diǎn)，有下列幾種情況：3插入插入(ch