數(shù)據(jù)結(jié)構(gòu)講義第9章

1、9.1靜態(tài)查找表9.2動態(tài)查找表9.3哈希表,目錄,第 九 章 查找,查找的基本概念,查找表(Search Table)： 是由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合。由于“集合”中的數(shù)據(jù)元素之間存在著完全松散的關(guān)系,因此查找表是一種非常靈便的數(shù)據(jù)結(jié)構(gòu)。,查找表的操作：1、查詢某個“特定的”數(shù)據(jù)元素是否在查找表中。2、檢索某個“特定的”數(shù)據(jù)元素的各種屬性。3、在查找表中插入一個數(shù)據(jù)元素；4、從

2、查找表中刪去某個數(shù)據(jù)元素。 靜態(tài)查找表： 對查找表只作前兩種操作，這兩種操作統(tǒng)稱為“查找”的操作，則稱此類查找表為靜態(tài)查找表。 動態(tài)查找表： 在查找過程中同時插入查找表中不存在的數(shù)據(jù)元素，或者從查找表中刪除已存在的某個元素（也即元素集合可以根據(jù)情況動態(tài)改變），則稱此類表為動態(tài)查找表。,在日常生活中，人們幾乎每天都要進(jìn)行“查找”工作。例如，在電話號碼簿中查閱“某單位”或“某人”的電話號碼；在字典中查閱“某個詞”的讀單和含義等

3、等。其中“電話號碼簿”和“字典”都可視作是一張查找表。查找： 根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等于給定的記錄或數(shù)據(jù)元素。若表中存在這樣的一個記錄，則稱查找是成功的，此時查找的結(jié)果為給出整個記錄的信息，或指示該記錄在查找表中的位置；若表中不存在關(guān)鍵字等于給定值的記錄，則稱查找不成功。 關(guān)鍵字（關(guān)鍵碼）、主關(guān)鍵字、次關(guān)鍵字。 舉例：P214頁書，（查找學(xué)生的高考成績）,如何進(jìn)行查找呢？

4、 其實(shí)，在一個結(jié)構(gòu)中查找某個數(shù)據(jù)元素的過程依賴于這個數(shù)據(jù)元素在結(jié)構(gòu)中所處的地位。因此，對表進(jìn)行查找的方法取決于表中數(shù)據(jù)元素依何種關(guān)系（這個關(guān)系是人為地加上的）組織在一起的。舉例：查電話號碼時，由于電話號碼簿是按用戶（集體或個人）的名稱（或姓名）分類且依筆劃順序編排，則查找的方法就是先順序查找待查用戶的所屬類別，然后在此類中順序查找，直到找到該用戶的電話號碼為止。 又如，查閱英文單詞時，由于字典是按單詞的字母在字

5、母表中的次序編排的，因此查找時不需要從字典中第一個單詞比較起，而只要根據(jù)待查單詞中每個字母在字母表中的位置查到該單詞。,同樣，在計(jì)算機(jī)中進(jìn)行查找的方法也隨數(shù)據(jù)結(jié)構(gòu)不同而不同。 但前面我們又說到查找表中的數(shù)據(jù)元素之間存在著完全松散的關(guān)系，這給我們查找?guī)聿槐?。為此，需在數(shù)據(jù)元素之間人為地加上一些關(guān)系，以例按某種規(guī)則進(jìn)行查找，即以另一種數(shù)據(jù)結(jié)構(gòu)來表示查找表。,一些約定：典型的關(guān)鍵字類型說明： typedef float

6、KeyType;//實(shí)型 typedef int KeyType;//整型typedef char *KeyType;//字符串型,數(shù)據(jù)元素類型定義為： typedef struct{ KeyType key; // 關(guān)鍵字域 . ..}ElemType;,,對兩個關(guān)鍵字的比較約定為如下的宏定義： 對數(shù)值型關(guān)鍵字#define EQ(a,b) ((a)==(b))#define LT(a,b)

7、((a)<(b))#define LQ(a,b) ((a)<=(b))對字符串型關(guān)鍵字#define EQ(a,b) (!strcmp((a),(b)))#define LT(a,b) (strcmp((a),(b))<0)#define LQ(a,b) (strcmp((a),(b))<=0),靜態(tài)查找表,靜態(tài)查找表的抽象數(shù)據(jù)類型定義：ADT StaticSearchTable{數(shù)據(jù)對象D：D

8、是具有相同特性的數(shù)據(jù)元素的集合。各個數(shù)據(jù)元素均含有類型相同，可唯一標(biāo)識數(shù)據(jù)元素的關(guān)鍵字。數(shù)據(jù)關(guān)系R：數(shù)據(jù)元素同屬一個集合?；静僮鱌：Create(&ST,n);操作結(jié)果：構(gòu)造一個含n個數(shù)據(jù)元素的靜態(tài)查找表ST。Destroy(&ST);初始條件：靜態(tài)查找表ST存在。操作結(jié)果：銷毀表ST。,9.1靜態(tài)查找法,Search(ST,key);初始條件：靜態(tài)查找表ST存在，key為和關(guān)鍵字類型相同的給定值

9、。操作結(jié)果：若ST中在在其關(guān)鍵字等于key的數(shù)據(jù)元素，則函數(shù)值為該元素的值或在表中的位置，否則為“空”。Traverse(ST,Visit());初始條件：靜態(tài)查找表ST存在，Visit是對元素操作的應(yīng)用函數(shù)。操作結(jié)果：按某種次序?qū)T的每個元素調(diào)用函數(shù)visit()一次且僅一次。一旦visit()失敗，則操作失敗。}ADT StaticSearchTable,順序表的查找,以順序表或線性鏈表表示靜態(tài)查找表，則Search

10、函數(shù)可用順序查找來實(shí)現(xiàn)。靜態(tài)查找表的順序存儲結(jié)構(gòu)typedef struct { ElemType *elem; //ElemType elem[100]; int length;}SSTable;順序查找：從表中最后一個記錄開始，逐個進(jìn)行記錄的關(guān)鍵字和給定值的比較，若某個記錄的關(guān)鍵字和給定值比較相等，則查找成功，找到所查記錄；反之，查找不成功。int Search_Seq(SSTable S

11、T,KeyType key){ ST.elme[0].key=key; for(i=ST.length; !EQ(ST.elem[i].key,key); --i); return i;} 演示！！,查找操作的性能分析： 查找算法中的基本操作是將記錄的關(guān)鍵字和給定值進(jìn)行比較，通常以“其關(guān)鍵字和給定值進(jìn)行過比較的記錄

12、個數(shù)的平均值”作為衡量依據(jù)。平均查找長度： 為確定記錄在查找表中的位置，需用和給定值進(jìn)行比較的關(guān)鍵字個數(shù)的期望值稱為查找算法在查找成功時的平均查找長度(Average Search Length)。,其中：Pi為查找表中第i個記錄的概率，且 ；Ci為找到表中其關(guān)鍵字與給定值相等的第i個記錄時，和給定值已進(jìn)行過比較的關(guān)鍵字個數(shù)。,對于含有n個記錄的表，查找成功時的平均查找長度為：,假設(shè)

13、每個記錄的查找概率相等，即 Pi=1/n則在等概率情況下順序查找的平均查找長度為：,假設(shè)查找成功與不成功的概率相同：,從順序查找的過程可見，Ci取決于所查記錄在表中的位置。如：查找表中最后一個記錄時，僅需比較一次；而查找表中第一個記錄時，則需比較n次。一般情況下Ci=n-i+1; 假設(shè)n=ST.length，則順序查找的平均查找長度為： ASL=n

14、P1+(n-1)P2+…..+2Pn-1+Pn,,前面總假設(shè)各個記錄的查找概率并不相等。但實(shí)際常常情況不是這樣，如果能預(yù)先知道每個記錄的查找概率，則應(yīng)先對記錄的查找概率進(jìn)行排序，使表中記錄按查找概率由小至大重新排列，以便提高查找效率。 但是，在一般情況下，記錄的查找概率預(yù)先無法測定。為了提高查找效率，我們可以在每個記錄中附設(shè)一個訪問頻度域，并使順序表中的記錄始終不斷往后移，以例在以后的逐次查找中減少比較次數(shù)?；蛘咴诿看?/p>

15、查找之后都將剛查找到的記錄直接移至表尾。,有序表的查找（可以采用折半查找來實(shí)現(xiàn)）,以有序表表示靜態(tài)查找表時，Search函數(shù)可用折半查找來實(shí)現(xiàn)。 折半查找（Binary Search）的查找過程是：先確定待查記錄所在的范圍（區(qū)間），然后逐步縮小范圍直到找到或找不到該記錄為止。,見演示??！,折半查找的查找實(shí)現(xiàn)int Search_Bin(SSTable ST,KeyType key){ low=1;high=ST.le

16、ngth; while(low<=high) { mid=(low+high)/2; if EQ(key,ST.elem[mid].key) return mid; else if LT(key,ST.elem[mid].key)

17、 high=mid -1; else low=mid +1 ; } return 0;}//Search_Bin;,折半查找的性能分析 看書中的一個具體的情況，假設(shè)：n=11i 12 3 4 5 6 7 8 9 10 11Ci 3 4 2 3 4

18、 1 3 4 2 3 4 現(xiàn)構(gòu)造一棵二叉樹，將Ci=i的結(jié)點(diǎn)放在這棵樹的第i層該二叉樹可用以描述折半查找的過程，稱之謂“折半查找的判定樹”,折半查找在查找成功時和給定值進(jìn)行比較的關(guān)鍵字個數(shù)至多為：,例如: 折半查找在n=11 時的判定樹如下,一般情況下，表長為n的折半查找的判定樹的深度和含有n個結(jié)點(diǎn)的完全二叉樹的深度相同,那末，折半查找的平均查找長度是多少呢

19、？ 假設(shè) n=2h-1 （反之，h=log2(n+1)）并且查找概率相等則：,在n>50時，可得近似結(jié)果,可見，折半查找的效率比順序查找高，但折半查找只能適用于有序表，且限于順序存儲結(jié)構(gòu)（對線性鏈表無法進(jìn)行折半查找）。,索引順序表的查找 若以索引順序表表示靜態(tài)查找表，則Search函數(shù)可用分塊查找來實(shí)現(xiàn)。 分塊查找又稱索引順序查找，這是順序查找的一種改進(jìn)方法。在此查找法中

20、，除表本身以外，尚需建立一個“索引表”。,22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 49 86 53,,,,,,,,,,,,,,,,,,48 861 7 13,,,,索引表,最大關(guān)鍵字 起始地址,,,,整個表中含有18個記錄，可分為三個子表（R1,R2,…,R6）、(R7,…,R1

21、2)、(R13,…,R18)對每個子表（或稱塊）建立一個索引項(xiàng)，其中包括兩項(xiàng)內(nèi)容：最大關(guān)鍵字項(xiàng) 該子表的起始地址,對索引表按關(guān)鍵字有序，則表或者有序或者分塊有序。P225頁書劃上概念！,由于由索引項(xiàng)組成的索引表按關(guān)鍵字

22、有序，則確定塊的查找可以用順序查找，亦可用折半查找，而塊中記錄是任意排列的，則在塊中只能是順序查找。 由此，分塊查找的算法即為這兩種查找算法的簡單合成。分塊查找的平均查找長度為： ASLbs=Lb+ Lw其中： Lb為查找索引表確定所在塊的平均查找長度， Lb為在塊中查找元素的平均查找長度。 一般情況下，為進(jìn)行分塊查找，可以將長度為n的表均勻地分成b塊，每塊

23、含有s個記錄，即b=[n/s]；又假定表中每個記錄的查找概率相等，則每塊查找的概率為1/b，塊中每個記錄的查找概率為1/s。若用順序查找確定所在塊，則分塊查找的平均查找長度為：,1.索引順序表： 存儲數(shù)據(jù)的表+索引；2.存儲方法： 數(shù)據(jù)分塊存放，且塊內(nèi)無序，但塊間有序； 每塊一個索引項(xiàng)，包括塊地址和塊中最大數(shù)據(jù)值。3.查找方法： 首先在索引表中查找，索引是有序順序表，可以采

24、用折半查找方法；然后在 塊內(nèi)查找進(jìn)行（只能）是順序查找。,總結(jié)：,9.2動態(tài)查找法,動態(tài)查找表的定義 動態(tài)查找表的特點(diǎn)是： 表結(jié)構(gòu)本身是在查找過程中動態(tài)生成的，即對于給定值key,若表中存在其關(guān)鍵字等于key的記錄，則查找成功返回，否則插入關(guān)鍵字等于key的記錄。以下是動態(tài)查找表抽象數(shù)據(jù)類型的定義：,ADT DymanicSearchTable{ 數(shù)據(jù)對象Ｄ：Ｄ是具有相同特性的數(shù)據(jù)元素

25、的集合。各個數(shù)據(jù)元素均含有類型相同，可唯一標(biāo)識數(shù)據(jù)元素的關(guān)鍵字。 數(shù)據(jù)關(guān)系Ｒ：數(shù)據(jù)元素同屬一個集合。,特點(diǎn)：用于頻繁進(jìn)行插入、刪除、查找的所謂動態(tài)查找表。,基本操作Ｐ：InitDSTable(&DT);操作結(jié)果：構(gòu)造一個空的動態(tài)查找表DT。DestroyDSTable(&DT);初始條件：動態(tài)查找表DT存在；操作結(jié)果：銷毀動態(tài)查找表DT。SearchDSTable(DT, key);初始條件：動態(tài)查找

26、表DT存在，key為和關(guān)鍵字類型相同的給定值；操作結(jié)果：若DT中存在其關(guān)鍵字等于key的數(shù)據(jù)元素，則函數(shù)值為該元素的值或在表中的位置，否則為“空”。InsertDSTable(&DT, e);初始條件：動態(tài)查找表DT存在，e為待插入的數(shù)據(jù)元素；操作結(jié)果：若DT中不存在其關(guān)鍵字等于e.key的數(shù)據(jù)元素，則插入e到DT。,DeleteDSTable(&T, key);初始條件：動態(tài)查找表DT存在，key為和關(guān)鍵字類

27、型相同的給定值；操作結(jié)果：若DT中存在其關(guān)鍵字等于key的數(shù)據(jù)元素，則刪除之。TraverseDSTable(DT, Visit());初始條件：動態(tài)查找表DT存在，Visit是對結(jié)點(diǎn)操作的應(yīng)用函數(shù)；操作結(jié)果：按某種次序?qū)T的每個結(jié)點(diǎn)調(diào)用函數(shù)visit()一次且至多一次。一旦visit()失敗，則操作失敗。} ADT DynamicSearchTable,二叉排序樹及其查找過程 什么是二叉排序樹？ 二叉排序樹

28、（Binary Sort Tree）或者是一棵空樹； 或者是具有下列性質(zhì)的二叉樹：１、若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；２、若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；３、它的左、右子樹了分別為二叉排序樹。,122,250,300,110,200,99,,,,,,L,N,P,

29、E,M,C,,,,,,Y,,105,,230,,216,,通常，取二叉鏈表作為二叉排序樹的存儲結(jié)構(gòu),二叉排序樹又稱二叉查找樹,也可以稱為二叉分類樹,1、分割式查找法： 查找步驟：若根結(jié)點(diǎn)的關(guān)鍵字值等于查找的關(guān)鍵字，成功。否則，若小于根結(jié)點(diǎn)的關(guān)鍵字值，查其左子樹。大于根結(jié)點(diǎn)的關(guān)鍵字值，查其右子樹。在左右子樹上的操作類似。,122,250,300,110,200,99,,,,,,105,,230,,216,,,BiTree

30、 SearchBST ( BiTree T, KeyType key ) // 在二叉分類樹查找關(guān)鍵字之值為 key 的結(jié)點(diǎn)，找到返回該結(jié) // 點(diǎn)的地址，否則返回空。T 為二叉分類樹的根結(jié)點(diǎn)的地址。 { if ( ( !T) || EQ( key, T ->data. key ) ) return ( T ) ; else if ( LT( key , T ->dat

31、a. key ) ) return (SearchBST ( T -> lchild, key )); else return (SearchBST ( T -> rchild, key )); } // SearchBST,表示：typedef struct BiTNode { ElemType d

32、ata; struct BiTNode * lchild, *rchild; } BiTNode; *BiTree;,見演示!,2、插入算法： 首先執(zhí)行查找算法，找出被插結(jié)點(diǎn)的父親結(jié)點(diǎn)。 判斷被插結(jié)點(diǎn)是其父親結(jié)點(diǎn)的左、右兒子。將被 插結(jié)點(diǎn)作為葉子結(jié)點(diǎn)插入。 若二叉樹為空。則首先單獨(dú)生成根結(jié)點(diǎn)。注意：新插入的結(jié)點(diǎn)總是葉子結(jié)點(diǎn)。,e、g：將數(shù)的序列：122、99

33、、250、110、300、280 作為二叉排序樹的結(jié) 點(diǎn)的關(guān)鍵字值，生成二叉排序樹。,2、插入算法： 首先執(zhí)行查找算法，找出被插結(jié)點(diǎn)的父親結(jié)點(diǎn)。 判斷被插結(jié)點(diǎn)是其父親結(jié)點(diǎn)的左、右兒子。將被 插結(jié)點(diǎn)作為葉子結(jié)點(diǎn)插入。 若二叉樹為空。則首先單獨(dú)生成根結(jié)點(diǎn)。注意：新插入的結(jié)點(diǎn)總是葉子結(jié)點(diǎn)。,e、g：將數(shù)的序列：122、99、250、110、300、280 作為二叉排序樹的結(jié) 點(diǎn)的關(guān)鍵字值，生成二叉排序樹。,

34、122,2、插入算法： 首先執(zhí)行查找算法，找出被插結(jié)點(diǎn)的父親結(jié)點(diǎn)。 判斷被插結(jié)點(diǎn)是其父親結(jié)點(diǎn)的左、右兒子。將被 插結(jié)點(diǎn)作為葉子結(jié)點(diǎn)插入。 若二叉樹為空。則首先單獨(dú)生成根結(jié)點(diǎn)。注意：新插入的結(jié)點(diǎn)總是葉子結(jié)點(diǎn)。,e、g：將數(shù)的序列：122、99、250、110、300、280 作為二叉排序樹的結(jié) 點(diǎn)的關(guān)鍵字值，生成二叉排序樹樹。,122,122,99,,2、插入算法： 首先執(zhí)行查找算法，找出被插結(jié)點(diǎn)的父親結(jié)點(diǎn)。

35、判斷被插結(jié)點(diǎn)是其父親結(jié)點(diǎn)的左、右兒子。將被 插結(jié)點(diǎn)作為葉子結(jié)點(diǎn)插入。 若二叉樹為空。則首先單獨(dú)生成根結(jié)點(diǎn)。注意：新插入的結(jié)點(diǎn)總是葉子結(jié)點(diǎn)。,e、g：將數(shù)的序列：122、99、250、110、300、280 作為二叉排序樹的結(jié) 點(diǎn)的關(guān)鍵字值，生成二叉排序樹。,122,122,99,,122,250,99,,,2、插入算法： 首先執(zhí)行查找算法，找出被插結(jié)點(diǎn)的父親結(jié)點(diǎn)。 判斷被插結(jié)點(diǎn)是其父親結(jié)點(diǎn)的左、右兒子。將被

36、插結(jié)點(diǎn)作為葉子結(jié)點(diǎn)插入。 若二叉樹為空。則首先單獨(dú)生成根結(jié)點(diǎn)。注意：新插入的結(jié)點(diǎn)總是葉子結(jié)點(diǎn)。,e、g：將數(shù)的序列：122、99、250、110、300、280 作為二叉排序樹的結(jié) 點(diǎn)的關(guān)鍵字值，生成二叉排序樹。,122,122,99,,122,250,99,,,122,250,110,99,,,,2、插入算法： 首先執(zhí)行查找算法，找出被插結(jié)點(diǎn)的父親結(jié)點(diǎn)。 判斷被插結(jié)點(diǎn)是其父親結(jié)點(diǎn)的左、右兒子。將被 插結(jié)點(diǎn)作為葉

37、子結(jié)點(diǎn)插入。 若二叉樹為空。則首先單獨(dú)生成根結(jié)點(diǎn)。注意：新插入的結(jié)點(diǎn)總是葉子結(jié)點(diǎn)。,e、g：將數(shù)的序列：122、99、250、110、300、280 作為二叉排序樹的結(jié) 點(diǎn)的關(guān)鍵字值，生成二叉排序樹。,122,122,99,,122,250,99,,,122,250,110,99,,,,122,250,300,110,99,,,,,2、插入算法： 首先執(zhí)行查找算法，找出被插結(jié)點(diǎn)的父親結(jié)點(diǎn)。 判斷被插結(jié)點(diǎn)是其父親結(jié)點(diǎn)的

38、左、右兒子。將被 插結(jié)點(diǎn)作為葉子結(jié)點(diǎn)插入。 若二叉樹為空。則首先單獨(dú)生成根結(jié)點(diǎn)。注意：新插入的結(jié)點(diǎn)總是葉子結(jié)點(diǎn)。,122,250,300,110,280,99,,,,,,e、g：將數(shù)的序列：122、99、250、110、300、280 作為二叉排序樹的結(jié) 點(diǎn)的關(guān)鍵字值，生成二叉排序樹。,122,122,99,,122,250,99,,,122,250,110,99,,,,122,250,300,110,99,,,,,

39、2、插入算法：,Status SearchBST ( BiTree T，KeyType key， BiTree f，BiTree &p ) // 在二叉排序樹 T 查找關(guān)鍵字之值為 key 的結(jié)點(diǎn)。初始時 f 為 NULL。 // 如樹空，返回 p 為 NULL及 FALSE。如樹非空且查找成功，返回 p = T 及 TRUE。 // 如樹非空且查不成功，返回 p = f 及 FALS

40、E。f 為待插入結(jié)點(diǎn)的的父親結(jié)點(diǎn)的地址。 { if ( ( !T) { p = f; return FALSE; } else if ( EQ( key, T ->data. key ) ) { p = T; return TRUE; } else if ( LT( key , T ->data. key ) ) return (SearchBST ( T -> lchild, key

41、, T, p )); else return (SearchBST ( T -> rchild, key , T, p )); } // SearchBST,程序?qū)崿F(xiàn)：,122,250,300,110,99,,,,,,,T,p,f:null,f: T 的父親結(jié)點(diǎn)p: 指向最后一個結(jié)點(diǎn)，TRUE 找到；FALSE 葉子的父親結(jié)點(diǎn)。如：插入 280 的過程。,280,,2、插入算法：,執(zhí)行實(shí)

42、例：插入值為 280 的結(jié)點(diǎn),2、插入算法：,Status Inset BST ( BiTree &T， ElemType e ) // 在二叉排序樹中不存在 e.key 時，插入并返回 TRUE，否則返回 FALSE。 { if ( ! SearchBST ( T，e.key，NULL，p ) { s = ( Bitree ) malloc ( sizeof ( BitNode ) ); s-&

43、gt;data = e; s->lchild = s->rchild = NULL; if ( ! p ) T = s; else if ( LT( e.key , p ->data. key ) ) p -> lchild = s; else p -> rchild = s; return TRUE; } return

44、FALSE; } // Insert BST,程序?qū)崿F(xiàn)：,122,250,300,110,99,,,,,,,T,p,f: T 的父親結(jié)點(diǎn)p: 指向最后一個結(jié)點(diǎn)，TRUE 找到；FALSE 葉子的父親結(jié)點(diǎn)。如：插入 280 的過程。,280,,f:null,,,15,60,70,30,20,,,,,50,,3、二叉排序樹的查找分析,平均情況分析（在成功查找兩種的情況下）,e.g: 下述兩種情況下的成功的平均查找長度 ASL

45、,15,60,70,30,20,,,,,50,,ASL=(1+2+2+3+3+3)/6=14/6,ASL=(1+2+3+4+5+6)/6=21/6,,,3、二叉排序樹的查找分析,平均情況分析（在成功查找兩種的情況下）,在一般情況下，設(shè) P（n，i）且它的左子樹的結(jié)點(diǎn)個數(shù)為 i 時的平均查找長度。右圖的結(jié)點(diǎn)個數(shù)為 n = 6 且 i = 3; 則 P（n,i）= P（6, 3） = [ 1+ ( P(3) + 1) * 3 + (

46、 P(2) + 1) * 2 ] / 6 = [ 1+ ( 5/3 + 1) * 3 + ( 3/2 + 1) * 2 ] / 6注意：這里 P(3)、P(2) 是具有 3 個結(jié)點(diǎn)、2 個結(jié)點(diǎn)的二叉排序樹的平均查找 長度。 在一般情況下，P（i）為具有 i 個結(jié)點(diǎn)二叉排序樹的平均查找 長度。 P(3

47、) ＝ （1+2+2）/ 3 = 5/3 P(2) ＝ （1+2）/ 2 = 3/2∴ P（n,i）= [ 1+ ( P(i) + 1) * i + ( P(n-i-1) + 1) * (n-i-1) ] / n∴ n-1 P（n）= ∑ P（n,i）/ n i=0 = 1.465log2

48、n,15,60,70,30,20,,,,,50,,,,,左子樹0到n-1個結(jié)點(diǎn),右子樹n-1到0個結(jié)點(diǎn),,,4、二叉排序樹的刪除操作,葉子結(jié)點(diǎn)：直接刪除，更改它的父親結(jié)點(diǎn)的相應(yīng)指針為空。如：刪除數(shù)據(jù)場為 15、70 的結(jié)點(diǎn)。,15,60,70,30,20,,,,,50,,60,30,20,,,,50,,,,子樹的根結(jié)點(diǎn)：通常的做法：選取“ 替身”取代被刪結(jié)點(diǎn)。有資格充當(dāng)該替身的是誰哪？ 左子樹中最大的結(jié)點(diǎn) 或 右子樹中

49、最小的結(jié)點(diǎn)，參看下圖。 要點(diǎn)：維持二叉排序樹的特性不變。在中序遍歷 中緊靠著被刪結(jié)點(diǎn)的結(jié)點(diǎn) 才有資格作為“替身”。,,4、二叉排序樹的刪除操作,,,,,122,250,300,110,200,99,,,,,105,,230,,216,,,400,450,500,,,子樹的根結(jié)點(diǎn)：

50、若被刪結(jié)點(diǎn)的左兒子為空或者右兒子為空。如下圖所示，刪除結(jié)點(diǎn)的數(shù)據(jù)場的關(guān)鍵字值為為 99 、300 的結(jié)點(diǎn)。,被刪結(jié)點(diǎn),,,122,250,300,200,,,,230,,216,,,400,450,500,,110,105,,,刪除,99,,4、二叉排序樹的刪除操作,,,,,122,250,300,110,200,99,,,,,105,,330,,316,,,400,450,500,,,被刪結(jié)點(diǎn),,,122,250,330,,,230

51、,216,,,400,450,500,,,刪除,300,110,99,,,105,,子樹的根結(jié)點(diǎn)：若被刪結(jié)點(diǎn)的左兒子為空或者右兒子為空。如下圖所示，刪除結(jié)點(diǎn)的數(shù)據(jù)場的關(guān)鍵字值為為 99 、300 的結(jié)點(diǎn)。,316,,,,4、二叉排序樹的刪除操作,,,,,,122,250,300,110,200,99,,,,,105,,330,,316,,,400,450,500,,,,被刪結(jié)點(diǎn),結(jié)論：·將被刪結(jié)點(diǎn)的另一兒子作為它的父

52、 親結(jié)點(diǎn)的兒子，究竟是作為左兒子 還是右兒子依原替身結(jié)點(diǎn)和其父親 結(jié)點(diǎn)的關(guān)系而定。 ·釋放被刪結(jié)點(diǎn)的空間。,被刪結(jié)點(diǎn),子樹的根結(jié)點(diǎn)：若被刪結(jié)點(diǎn)的左兒子為空或者右兒子為空。如下圖所示，刪除結(jié)點(diǎn)的數(shù)據(jù)場的關(guān)鍵字值為為 99 、300 的結(jié)點(diǎn)。,,,,4、二叉排序樹的刪除操作,子樹的根結(jié)點(diǎn)：若被刪結(jié)點(diǎn)的左、右子樹皆不空，則： 通常的做

53、法：選取“替身”取代被刪結(jié)點(diǎn)。有資格充當(dāng)該替身的是誰哪？ 左子樹中最大的結(jié)點(diǎn)(被刪結(jié)點(diǎn)的左子樹中的最右的結(jié)點(diǎn)，其右兒子指針場為空) 或 右子樹中最小的 結(jié)點(diǎn)(被刪結(jié)點(diǎn)的右子樹中的最左的結(jié)點(diǎn)，其左兒子指針場為空) ，參看下圖。 要點(diǎn)：維持二叉分類樹的特性不變。在中序周游中緊靠著被刪 結(jié)點(diǎn)的結(jié)點(diǎn)才有資格作為“替身”。,,,,,,122,250,300,110,200

54、,99,,,,,105,,330,316,,,400,450,500,,,,,被刪結(jié)點(diǎn),替身,替身,,,,110,250,300,105,200,99,,,,,330,,316,,,400,450,500,,做法：將替身的數(shù)據(jù)場復(fù)制到被刪結(jié) 點(diǎn)的數(shù)據(jù)場。 將結(jié)點(diǎn) 的左兒子作為 的父結(jié)點(diǎn)

55、 的右兒子。,110,110,99,注意：結(jié)點(diǎn) 右兒子必為空 結(jié)點(diǎn) 的父結(jié)點(diǎn)為,110,110,99,,,4、二叉排序樹的刪除操作,,,,,,,122,250,300,110,200,99,,,,,105,,330,,316,,,400,450,500,,,,,被刪結(jié)點(diǎn),替身,替身,,,,200,250,300,110,99,,,,105,,216,,40

56、0,450,500,,子樹的根結(jié)點(diǎn)：若被刪結(jié)點(diǎn)的左、右子樹皆不空，則： 通常的做法：選取“替身”取代被刪結(jié)點(diǎn)。有資格充當(dāng)該替身的是誰哪？ 左子樹中最大的結(jié)點(diǎn)(被刪結(jié)點(diǎn)的左子樹中的最右的結(jié)點(diǎn)，其右兒子指針場為空) 或 右子樹中最小的 結(jié)點(diǎn)(被刪結(jié)點(diǎn)的右子樹中的最左的結(jié)點(diǎn)，其左兒子指針場為空) ，參看下圖。 要點(diǎn)：維持二叉分類樹的特性不變。在中序周游中緊靠著

57、被刪 結(jié)點(diǎn)的結(jié)點(diǎn)才有資格作為“替身”。,做法：將替身的數(shù)據(jù)場復(fù)制到被刪結(jié) 點(diǎn)的數(shù)據(jù)場。 將結(jié)點(diǎn) 的右兒子作為 的父結(jié)點(diǎn) 的左兒子。,注意：結(jié)點(diǎn) 左兒子必為空 結(jié)點(diǎn) 的父結(jié)點(diǎn)為,200,200,200,2

58、00,250,330,,316,,,,4、二叉排序樹的刪除操作,,,,,,,122,250,300,110,200,99,,,,,105,,230,,216,,,400,450,500,,,,,被刪結(jié)點(diǎn),替身,替身,子樹的根結(jié)點(diǎn)：若被刪結(jié)點(diǎn)的左、右子樹皆不空，則： 通常的做法：選取“替身”取代被刪結(jié)點(diǎn)。有資格充當(dāng)該替身的是誰哪？ 左子樹中最大的結(jié)點(diǎn)(被刪結(jié)點(diǎn)的左子樹中的最右的結(jié)點(diǎn)，其右兒子指針場為空) 或 右子樹中最

59、小的 結(jié)點(diǎn)(被刪結(jié)點(diǎn)的右子樹中的最左的結(jié)點(diǎn)，其左兒子指針場為空) ，參看下圖。 要點(diǎn)：維持二叉分類樹的特性不變。在中序周游中緊靠著被刪 結(jié)點(diǎn)的結(jié)點(diǎn)才有資格作為“替身”。,結(jié)論：·先將替身的數(shù)據(jù)場復(fù)制到被刪結(jié)點(diǎn) ·將原替身的另一兒子作為它的父親 結(jié)點(diǎn)的兒子，究竟是作為左兒子還 是

60、右兒子依原替身結(jié)點(diǎn)和其父親結(jié) 點(diǎn)的關(guān)系而定。 ·釋放原替身結(jié)點(diǎn)的空間。,,4、二叉排序樹的刪除操作,,,,,F,S,,,C,,,,Q,,QL,,SL,,,,F,,C,,,,Q,,QL,,S,,SL,,F,,PL、PR皆 空， 直接刪除 。,PL或PR為空，,PL為空，刪除后的情況。,1.刪除法,2.刪除法,Status DeleteBST ( BiTree &T，Ke

61、yType key ) // 若二叉排序樹 T 中存在關(guān)鍵字為 key 的結(jié)點(diǎn)時，則刪除該結(jié)點(diǎn)，并返回 TRUE； // 否則返回 FALSE。 { if ( ( !T) return FALSE; // 二叉排序樹 T 中不存在關(guān)鍵字為 key 的結(jié)點(diǎn) else if ( EQ( key, T ->data. key ) ) Delete (T); // 存在關(guān)鍵字為 key 的

62、結(jié)點(diǎn)，進(jìn)行刪除 else if ( LT( key , T ->data. key ) ) DeleteBST ( T -> lchild, key ); else DeleteBST ( T -> rchild, key ); return TRUE; } // DeleteBST,程序?qū)崿F(xiàn)：,4、二叉排序樹的刪除操作,Status Delete

63、( BiTree &p ) // 在二叉排序樹中刪除地址為 p 的結(jié)點(diǎn)，并保持二叉排序樹的性質(zhì)不變。 { if ( ! p-> rchild ) { q = p; p = p->lchild ; free(q); } // 參考下頁 else if ( ! p-> lchild ) { q = p; p = p->rchild ; free(q); }

64、else { q = p; s = p-> lchild; while ( s->rchild ) { q = s; s = s->rchild; } p->data = s->data; if ( q != p ) q->rchild = s->lchild;

65、 else q->lchild = s->lchild; free(s); } } // DeleteBST,程序?qū)崿F(xiàn)：,4、二叉排序樹的刪除操作,注意：刪除根結(jié)點(diǎn)而相應(yīng)的二叉樹沒有另增的頭結(jié)點(diǎn)的情況。,,,被刪結(jié)點(diǎn) P,,,若：P -> rchild == NULL,,,被刪結(jié)點(diǎn) f,,原 f->lchild 即為 P ；現(xiàn) p=p-&g

66、t;lchild故 f->lchild 即為 PL,二叉排序樹的插入,二叉排序樹是一種動態(tài)樹表，其特點(diǎn)是，樹的結(jié)構(gòu)通常不是一次生成的，而是在查找過程中，當(dāng)樹中不存在關(guān)鍵字等于給定值的結(jié)點(diǎn)時再進(jìn)行插入。新插入的結(jié)點(diǎn)一定是一個新添加的葉子結(jié)點(diǎn)，并且是查找不成功時查找路徑上訪問的最后一個結(jié)點(diǎn)的左孩子或右孩子結(jié)點(diǎn)。,Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree &p)

67、{ if(!T) {p=f;return FALSE;} else if EQ(key,T->data.key) { p=T;return TRUE;} else if LT(key,T->data.key)

68、 SearchBsT(T->lchild,key,T,p); else SearchBST(T->rchild,key,T,p);}//SearchBST,見演示??！,插入算法：Status InsertBST(BiTree &T,ElemType e){ if(!SearchBST(T,e.key,NUL

69、L,p) { s=(BiTree)malloc(sizeof(BiTNode)); s->data=e;s->lchild=s->rchild=NULL; if(!p) T=s; else if (LT(e.key,p-