《《算法與數(shù)據(jù)結(jié)構(gòu)》教學(xué)課件第6章 字典和高級(jí)字典C語(yǔ)言描述（第2版）張乃孝編著》由會(huì)員分享，可在線閱讀，更多相關(guān)《《算法與數(shù)據(jù)結(jié)構(gòu)》教學(xué)課件第6章 字典和高級(jí)字典C語(yǔ)言描述（第2版）張乃孝編著（96頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、6.1 集合及其抽象數(shù)據(jù)類型*6.2 集合的實(shí)現(xiàn)*6.3 字典及其抽象數(shù)據(jù)類型6.4 字典的順序表示6.5 字典的散列表示6.3 字典及其抽象數(shù)據(jù)類型6.3.1 基本概念 字典：是一種集合，其中每個(gè)元素由兩部分組成，分別稱為關(guān)鍵碼和屬性。這種包含關(guān)鍵碼和屬性得二元組稱作關(guān)聯(lián)。 對(duì)字典進(jìn)行的操作主要有：檢索、插入元素和刪除元素。字典中最主要的運(yùn)算是進(jìn)行檢索。 靜態(tài)字典：一經(jīng)建立就基本保持不變； 動(dòng)態(tài)字典：經(jīng)常需要改動(dòng)。 存儲(chǔ)方法存儲(chǔ)方法：順序法、散列法、二叉樹(shù)法和B樹(shù)。 存儲(chǔ)方法的選擇：考慮檢索效率、元素的插入和刪除是否簡(jiǎn)便。 檢索效率的標(biāo)準(zhǔn)檢索效率的標(biāo)準(zhǔn)：檢索過(guò)程中和關(guān)鍵碼的平均比較次數(shù)，即平

2、均檢索長(zhǎng)度ASL，定義為： ASL = pici 每個(gè)元素的檢索概率相等時(shí)， pi=1/n。ni=16.3.2 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型ADT6.2 字典的抽象數(shù)據(jù)類型字典的抽象數(shù)據(jù)類型ADT dictionary isoperation Dictionary createEmptyDictionary(void) int search(Dictionary dic,KeyType key,Position p) int insert(Dictionary dic,DicElement ele) int delete(Dictionary dic,KeyType key)end ADT dic

3、tionary字典的順序表示定義如下typedef int KeyType;typedef int DataType;typedef struct KeyType key; /* 字典元素的關(guān)鍵碼字段字典元素的關(guān)鍵碼字段*/DataType value; /* 字典元素的屬性字段字典元素的屬性字段*/DicElement;typedef struct int MAXNUM;int n; /*字典中元素的個(gè)數(shù)字典中元素的個(gè)數(shù) */ DicElement *element; SeqDictionary; 6.4.1 6.4.1 存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)算法算法6.11 順序檢索算法順序檢索算法int se

4、qSearch(SeqDictionary *pdic, KeyType key, int &position) /*在字典中順序檢索關(guān)鍵碼為在字典中順序檢索關(guān)鍵碼為key的元素的元素*/int i; for(i=0; in; i+) /* 從頭開(kāi)始向后掃描從頭開(kāi)始向后掃描*/ if(pdic-elementi.key=key) position=i; return(1); /* 檢索成功檢索成功 */ position=pdic-n;return(0); /* 檢索失敗檢索失敗 */6.4.2 6.4.2 算法的實(shí)現(xiàn)算法的實(shí)現(xiàn)l算法算法6.11 6.11 順序檢索算法順序檢索算法ASL =

5、1*p1 +2* p2 + +n* pn = (1+2+n)/n (pi=1/n) = (n+1)/2=O(n) 優(yōu)點(diǎn)是算法簡(jiǎn)單且適應(yīng)面廣，無(wú)論字典中元素是否有序均可使用。缺點(diǎn)是平均檢索長(zhǎng)度較大，特別是當(dāng)n很大時(shí)，檢索效率較低。6.4.2 6.4.2 算法的實(shí)現(xiàn)算法的實(shí)現(xiàn)6.4.3 有序順序表與二分法檢索 按照關(guān)鍵碼大小排序的順序表稱為有序順序表。 二分法檢索又稱折半檢索。要求字典的元素在順序表中按關(guān)鍵碼排序（從小到大）。 05,10,18,25,27,32,41,51,68,73,99 05,10,18,25,27,32,41,51,68,73,99 05,10,18,25,27,32,41

6、,51,68,73,99檢索關(guān)鍵碼2505,10,18,25,27,32,41,51,68,73,9905,10,18,25,27,32,41,51,68,73,9905,10,18,25,27,32,41,51,68,73,9905,10,18,25,27,32,41,51,68,73,99檢索關(guān)鍵碼75l算法算法6.12 6.12 二分法檢索算法二分法檢索算法 條件：字典中的元素按關(guān)鍵碼排序。 優(yōu)點(diǎn)是比較次數(shù)少，檢索速度快。缺點(diǎn)是要將字典按關(guān)鍵碼排序，且只適用于順序存儲(chǔ)結(jié)構(gòu)。算法算法6.12二分法檢索算法二分法檢索算法int binarySearch(SeqDictionary * pdi

7、c, KeyType key, int &position) /* 在字典中用二分法查找關(guān)鍵碼為在字典中用二分法查找關(guān)鍵碼為key的元素的元素 */ int low, mid, high; low=0; high=pdic-n-1; while(lowelementmid.key=key) /* 檢索成功檢索成功 */ position=mid; return(1); else if(pdic-elementmid.keykey) high=mid-1; else low=mid+1; /* 要檢索的元素在右半?yún)^(qū)要檢索的元素在右半?yún)^(qū) */ position=low; return(0); /*

8、 檢索失敗檢索失敗 */折半查找的判定樹(shù)l用一棵二叉樹(shù)來(lái)描述折半用一棵二叉樹(shù)來(lái)描述折半查找過(guò)程：二叉樹(shù)結(jié)點(diǎn)中查找過(guò)程：二叉樹(shù)結(jié)點(diǎn)中的數(shù)值表示有序表記錄中的數(shù)值表示有序表記錄中的序號(hào)。的序號(hào)。虛黑線虛黑線表示查找表示查找2525比較過(guò)的記錄，比較過(guò)的記錄，虛紅線虛紅線表示查找表示查找7575經(jīng)過(guò)的記錄。經(jīng)過(guò)的記錄。記錄在判定樹(shù)上的層次恰記錄在判定樹(shù)上的層次恰為找到此記錄時(shí)所需比較為找到此記錄時(shí)所需比較的次數(shù)。的次數(shù)。l設(shè)每個(gè)記錄查找概率相等，設(shè)每個(gè)記錄查找概率相等，查找成功的平均查找長(zhǎng)度：查找成功的平均查找長(zhǎng)度：ASL（12233334+4+4+4)/11=33/11=3321868254173

9、515992710 05,10,18,25,27,32,41,51,68,73,996.5 6.5 字典的散列表示字典的散列表示 前面介紹的查找方法都是建立在前面介紹的查找方法都是建立在“比較比較”的基礎(chǔ)的基礎(chǔ)上，查找的效率依賴于查找過(guò)程中所進(jìn)行比較的次數(shù)。上，查找的效率依賴于查找過(guò)程中所進(jìn)行比較的次數(shù)。 理想的情況理想的情況是希望不進(jìn)行任何比較，一次存取便能得是希望不進(jìn)行任何比較，一次存取便能得到所查記錄。這樣就需要在關(guān)鍵碼和記錄的存儲(chǔ)位置到所查記錄。這樣就需要在關(guān)鍵碼和記錄的存儲(chǔ)位置之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系. key 存儲(chǔ)地址存儲(chǔ)地址h 6.5.1 基本概念 6

10、.5.2 散列函數(shù) 6.5.3 碰撞的處理 6.5.4 散列文件散列函數(shù)散列函數(shù)： 使每個(gè)關(guān)鍵碼都和結(jié)構(gòu)中存儲(chǔ)位置對(duì)應(yīng)使每個(gè)關(guān)鍵碼都和結(jié)構(gòu)中存儲(chǔ)位置對(duì)應(yīng),這樣的一這樣的一個(gè)對(duì)應(yīng)關(guān)系稱為個(gè)對(duì)應(yīng)關(guān)系稱為散列（哈希散列（哈希Hash）函數(shù)）函數(shù)。 關(guān)鍵碼關(guān)鍵碼 存儲(chǔ)地址存儲(chǔ)地址碰撞碰撞：若：若key1 key2 ,h(key1)=h(key2). key1和和key2稱為稱為同義詞同義詞。h(key)的值域所對(duì)應(yīng)的的值域所對(duì)應(yīng)的地址空間稱為地址空間稱為基本區(qū)域基本區(qū)域。發(fā)生碰撞時(shí)，發(fā)生碰撞時(shí)，同義詞可以存放在同義詞可以存放在基本區(qū)域中未被占基本區(qū)域中未被占用的單元，也用的單元，也可以存放到另開(kāi)的可以

11、存放到另開(kāi)的區(qū)域中。區(qū)域中。負(fù)載因子負(fù)載因子： 散列表中結(jié)點(diǎn)數(shù)散列表中結(jié)點(diǎn)數(shù) 基本區(qū)域能容納的結(jié)點(diǎn)數(shù)基本區(qū)域能容納的結(jié)點(diǎn)數(shù)6.5.1 基本概念h = 關(guān)鍵碼關(guān)鍵碼經(jīng)過(guò)經(jīng)過(guò)散列函數(shù)散列函數(shù)得到一個(gè)隨機(jī)地址，得到一個(gè)隨機(jī)地址，以便使一組關(guān)鍵碼的散列地址均勻地分布在以便使一組關(guān)鍵碼的散列地址均勻地分布在逐個(gè)地址區(qū)間中，從而減少?zèng)_突。逐個(gè)地址區(qū)間中，從而減少?zèng)_突。 常用的散列函數(shù)有：常用的散列函數(shù)有：1 1 數(shù)字分析法數(shù)字分析法2 2 折疊法折疊法 3. 3. 中平方法中平方法 4. 4. 基數(shù)轉(zhuǎn)換法基數(shù)轉(zhuǎn)換法 5. 5. 除余法除余法6.5.2 散列函數(shù)1. 數(shù)字分析法數(shù)字分析法 假設(shè)關(guān)鍵碼是以假設(shè)

12、關(guān)鍵碼是以r為基的數(shù)，并且哈希表中可為基的數(shù)，并且哈希表中可能現(xiàn)的關(guān)鍵碼都是事先知道的，則可取關(guān)鍵碼的能現(xiàn)的關(guān)鍵碼都是事先知道的，則可取關(guān)鍵碼的若干數(shù)位組成散列地址。若干數(shù)位組成散列地址。 Key h(key) 000319426 326 000718309 709 000629443 643 000758615 715 000919697 997 000310329 3292. 折疊法折疊法 將關(guān)鍵碼分割成幾部分，然后取這幾部分的疊加和將關(guān)鍵碼分割成幾部分，然后取這幾部分的疊加和作為地址。作為地址。 key=582422241 58 | 2422 | 241 58 | 2422 | 241

13、8 5 5 8 1 4 2 2 4 1 2 4 2 2 2 4 2 2 1 1 0 6 4 2 7 2 13. 中平方法中平方法 先求出關(guān)鍵碼的平方，然后取中間幾位作為地址。先求出關(guān)鍵碼的平方，然后取中間幾位作為地址。 key=4731 (4731)2 = 22382361 h(key)=3824. 基數(shù)轉(zhuǎn)換法基數(shù)轉(zhuǎn)換法 把關(guān)鍵碼看成基數(shù)為把關(guān)鍵碼看成基數(shù)為r1的數(shù)，將它轉(zhuǎn)換成基數(shù)為的數(shù)，將它轉(zhuǎn)換成基數(shù)為r2的數(shù)，用數(shù)字分析法取中間幾位作為散列地址。的數(shù)，用數(shù)字分析法取中間幾位作為散列地址。r1和和r2最好互素。例如，最好互素。例如，key=236075, r1=13, r2=10, (236

14、075)13=2*135+3*134+6*133+7*13+5 =(841547)10 h(key)=41545. 除余法除余法 取關(guān)鍵碼被某個(gè)不大于散列表長(zhǎng)度取關(guān)鍵碼被某個(gè)不大于散列表長(zhǎng)度m的數(shù)的數(shù)p除后所得余數(shù)為散列地址。數(shù)除后所得余數(shù)為散列地址。數(shù)p的選?。阂话愕倪x取：一般可選它為質(zhì)數(shù)。可選它為質(zhì)數(shù)。 h(key)=key % p; m=128, 256, 512, 1024 p=127, 251, 503, 1019實(shí)際工作中需視情況的不同而采用不同的散列函實(shí)際工作中需視情況的不同而采用不同的散列函數(shù)，通常需要考慮的因素有：數(shù)，通常需要考慮的因素有： A. 計(jì)算哈希函數(shù)所需時(shí)間計(jì)算哈希

15、函數(shù)所需時(shí)間; B. 關(guān)鍵碼的長(zhǎng)度關(guān)鍵碼的長(zhǎng)度; C. 哈希表的大小哈希表的大小; D. 關(guān)鍵碼的分布情況關(guān)鍵碼的分布情況; E. 記錄的查找頻率。記錄的查找頻率。總之，是總之，是“雜湊雜湊”出來(lái)的。出來(lái)的。 開(kāi)地址法開(kāi)地址法在在基本區(qū)域基本區(qū)域內(nèi)形成一個(gè)內(nèi)形成一個(gè)探查序列探查序列 Hi = (H(key) + di)MOD m, i = 1, 2, , k ( k m-1)其中：其中：m為表長(zhǎng)，為表長(zhǎng)，di為增量序列，可有多種取法：為增量序列，可有多種取法： A. di = 1, 2, 3, , m-1, 稱稱線性探查序列線性探查序列; B. di = i*h2(key), h2(key)是

16、另一個(gè)是另一個(gè)散列函數(shù)，稱散列函數(shù)，稱 雙散列探查序列雙散列探查序列; C. di = 12, -12, 22, -22, , k2, -k2 (k m/2)稱為稱為二次探查序列二次探查序列； D. di = 偽隨機(jī)數(shù)序列，稱偽隨機(jī)數(shù)序列，稱偽隨機(jī)探查序列偽隨機(jī)探查序列。 當(dāng)發(fā)生碰撞時(shí)，則沿探查序列進(jìn)行查找，當(dāng)發(fā)生碰撞時(shí)，則沿探查序列進(jìn)行查找， 插插入時(shí)，直到找到一個(gè)空單元；查找時(shí)，或查找到入時(shí)，直到找到一個(gè)空單元；查找時(shí)，或查找到關(guān)健碼為關(guān)健碼為key的元素或查找到達(dá)一個(gè)空單元。例如：的元素或查找到達(dá)一個(gè)空單元。例如： K=18, 73, 10, 05, 68, 99, 27, 41, 51

17、, 32, 25 5, 8, 10, 5, 3, 8, 1, 2, 12, 6, 12 h(key)=key%13; 地址 0 1 2 3 4 5 6 7 8 9 10 11 12 關(guān)鍵碼 1873100568992741513225 采用采用線性探測(cè)序列線性探測(cè)序列，容易出現(xiàn)，容易出現(xiàn)堆積堆積現(xiàn)象，即在處現(xiàn)象，即在處理同義詞的過(guò)程中又添加了非同義詞的沖突。理同義詞的過(guò)程中又添加了非同義詞的沖突。存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)typedef int KeyTypetypedef int DataType;typedef struct KeyType key; DataType value;DicElemen

18、t;typedef struct int m; DicElement *element;HashDictionary;typedef HashDictionary *PHashDictionary;（教材缺）（教材缺）算法算法6.13 6.13 創(chuàng)建空散列表創(chuàng)建空散列表PHashDictionary createEmptyDictionary(intPHashDictionary createEmptyDictionary(int m) m) PHashDictionary phd PHashDictionary phd = = new HashDictionarynew HashDictio

19、nary; ; if (phd if (phd!=NULL)!=NULL) phd phd-element = -element = new DicElementmnew DicElementm; if(phd if(phd-element)-element) phd phd-m = m;-m = m; for( for(intint i=0; im; i+) i=0; ielementi phd-elementi.key.key = 0; = 0; return phd return phd; ; else else deletedelete phd phd; ; cout“Out of s

20、pace!”endl cout“Out of space!”endl; ; return NULL; return NULL; 在散列表上進(jìn)行查找和構(gòu)造散列表的過(guò)程基本一在散列表上進(jìn)行查找和構(gòu)造散列表的過(guò)程基本一致。給定致。給定key值，根據(jù)散列函數(shù)求得散列地址，若表值，根據(jù)散列函數(shù)求得散列地址，若表中沒(méi)有記錄，則查找不成功；否則比較關(guān)鍵碼，若中沒(méi)有記錄，則查找不成功；否則比較關(guān)鍵碼，若和給定值相等，則查找成功；否則根據(jù)造表時(shí)設(shè)定和給定值相等，則查找成功；否則根據(jù)造表時(shí)設(shè)定的沖突處理方法找的沖突處理方法找“下一地址下一地址”，直到散列表某個(gè)，直到散列表某個(gè)位置為空或表中所填記錄的關(guān)鍵碼等于給定

21、值時(shí)為位置為空或表中所填記錄的關(guān)鍵碼等于給定值時(shí)為止。止。 算法算法6.14 散列表的檢索散列表的檢索算法算法6.15 散列表的插入散列表的插入散列表的查找散列表的查找算法算法6.14 散列表的檢索算法散列表的檢索算法用線性探查法解決碰撞用線性探查法解決碰撞int linearSearch(HashDictionary *phash, KeyType key, int *position) int d, inc; d=h(key);/* d為散列地址，散列函數(shù)為為散列地址，散列函數(shù)為h(key) */ for(inc=0; incm; inc+) if(phash-elementd.key=k

22、ey) *position=d; return(1); /* 檢索成功檢索成功 */ else if(phash-elementd.key=0) *position=d; return(0); /檢索失敗，找到插入位置檢索失敗，找到插入位置 d=(d+1)%phash-m; *position = -1;/* 散列表溢出散列表溢出 */ return(0);算法算法6.15 散列表的插入算法散列表的插入算法用線性探查法解決碰撞用線性探查法解決碰撞int linearInsert(HashDictionary *phash, DicElement ele) int position; if(li

23、nearSearch(phash, ele.key, &position) = 1 ) /* 散列表中已有關(guān)鍵碼為散列表中已有關(guān)鍵碼為key 的結(jié)點(diǎn)的結(jié)點(diǎn) */ printf(“Findn”); else if(position!=-1) phash-elementposition = ele; /* 插入結(jié)點(diǎn)，忽略對(duì)插入結(jié)點(diǎn)，忽略對(duì)value字段的賦值字段的賦值 */ else return(0); /* 散列表溢出散列表溢出 */ return(1); K=18, 73, 10, 05, 68, 99, 27, 41, 51, 32, 25 5, 8, 10, 5, 3, 8, 1, 2,

24、 12, 6, 12 h1(key)=key%13; h2(key)=key%11+1；187310 05689927 415132 25h1(25)=25%13=12;h1(25)+h2(25)=25%13+(25%11+1)=12+4=16;h1(25)+2*h2(25)=25%13+2*(25%11+1)=12+8=20;雙散列函數(shù)法雙散列函數(shù)法 拉鏈法拉鏈法 設(shè)設(shè)基本區(qū)域基本區(qū)域長(zhǎng)度為長(zhǎng)度為m，建立，建立m條條鏈表，將所有關(guān)鏈表，將所有關(guān)鍵字為同義詞的記錄存儲(chǔ)在同一鍵字為同義詞的記錄存儲(chǔ)在同一條條線性鏈表中。線性鏈表中。 K=18, 73, 10, 05, 68, 99, 27, 41

25、, 51, 32, 25 5, 8, 10, 5, 3, 8, 1, 2, 12, 6, 12 h(key)=key%13; ，27，41，68， ，18，05, 32， ，73， 99， ，10， ，51，25 27 41 68 18 5 32 73 99 10 51 25 圖6.4 用拉鏈法解決碰撞 在外存上，同義詞表可以采用順序表或散列表。在外存上，同義詞表可以采用順序表或散列表。有時(shí)把存放同義詞的表稱為有時(shí)把存放同義詞的表稱為“桶桶”。 按按“桶桶”散列的文件由若干桶和一個(gè)桶目錄構(gòu)散列的文件由若干桶和一個(gè)桶目錄構(gòu)成成。6.5.4 散列文件 桶目錄桶：由若干頁(yè)塊組成每個(gè)頁(yè)塊存放若干記錄l

26、作業(yè)：p. 198l復(fù)習(xí)題 2，3，4l算法題 3，4l網(wǎng)絡(luò)課堂測(cè)試: 6 集合與字典 l上機(jī)實(shí)驗(yàn)5.2 5.3 5.67.3 7.3 二叉排序樹(shù)二叉排序樹(shù)7.4 7.4 最佳二叉排序樹(shù)最佳二叉排序樹(shù)* *7.5 7.5 平衡二叉排序樹(shù)平衡二叉排序樹(shù) 字典采用二叉排序樹(shù)作為存儲(chǔ)結(jié)構(gòu)，既有較高的檢索效率，又具有鏈?zhǔn)酱鎯?chǔ)時(shí)元素插入、刪除操作的靈活性。 二叉排序樹(shù)二叉排序樹(shù)定義定義 二叉排序樹(shù)(Binary Sort Tree)或者是一棵空二叉樹(shù)；或者具有下列性質(zhì)的二叉樹(shù)： A. 若它的左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的 值均小于它的根結(jié)點(diǎn)的值； B. 若它的右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn) 的值均大于

27、它的根結(jié)點(diǎn)的值； C. 它的左右子樹(shù)也分別為二叉排序樹(shù)。實(shí)際上，折半查找法的判定樹(shù)就是一棵二叉排序樹(shù)。K= 18, 73, 10, 05, 68, 99, 27, 41, 51, 32, 251810739968272541325105圖7.5 二叉排序樹(shù)示例struct BinSearchNodestruct BinSearchNode; ;typedef struct BinSearchNode typedef struct BinSearchNode * *PBinSearchNodePBinSearchNode; ; struct BinSearchNode struct BinSea

28、rchNode KeyTypeKeyType key; key;/ /* * 結(jié)點(diǎn)的關(guān)鍵碼字段結(jié)點(diǎn)的關(guān)鍵碼字段 * */ / PBinSearchNode llink, rlinkPBinSearchNode llink, rlink; ; / /* * 二叉樹(shù)的左、右指針二叉樹(shù)的左、右指針 * */ / ; ; typedef struct BinSearchNode typedef struct BinSearchNode * *BinSearchTreeBinSearchTree; ;typedef BinSearchTree typedef BinSearchTree * *PBinS

29、earchTreePBinSearchTree; ;二叉排序樹(shù)的存儲(chǔ)結(jié)構(gòu)（llink_rlink)： L.keyT.keykey) 查左子樹(shù)；查左子樹(shù)； else 查右子樹(shù)；查右子樹(shù)； 算法7.1 二叉排序樹(shù)的檢索算法 TLR算法算法7.1 7.1 二叉排序樹(shù)的檢索算法二叉排序樹(shù)的檢索算法int search(PBinSearchTree ptree, KeyTypeint search(PBinSearchTree ptree, KeyType key, key, PBinSearchNode PBinSearchNode * *position)position) PBinSearchNo

30、de PBinSearchNode p, q; p, q; p= p=* *ptreeptree; q=p; q=p; while(p while(p!=NULL) !=NULL) q=p; q=p; if(p-key=key if(p-key=key) ) * *position=p; return(1); position=p; return(1); else if(p-keykey) p=p-llink else if(p-keykey) p=p-llink; ; else p=p-rlink else p=p-rlink; ; * *position=q; return(0);posi

31、tion=q; return(0); 當(dāng)樹(shù)中不存在關(guān)鍵字等于給定值的結(jié)點(diǎn)時(shí)，需要生成新結(jié)點(diǎn)并插入到二叉樹(shù)中。而新插入的結(jié)點(diǎn)必定是一個(gè)葉子結(jié)點(diǎn)，并且是查找不成功時(shí)查找路徑上訪問(wèn)的最后一個(gè)結(jié)點(diǎn)的左孩子或右孩子結(jié)點(diǎn)。 算法： if ( 二叉排序樹(shù)中查不到該結(jié)點(diǎn)) 建立新結(jié)點(diǎn)； if (原二叉排序樹(shù)是空樹(shù)) 新結(jié)點(diǎn)作為根結(jié)點(diǎn); else if (新結(jié)點(diǎn)key=key; p-llink=p-rlink=NULL; if(position=NULL) *ptree=p; else if(keykey) position-llink=p; /插入的左子樹(shù)插入的左子樹(shù)else position-rlink=p

32、; /* 插入插入position的右子樹(shù)的右子樹(shù) */ return 1; 若從空樹(shù)出發(fā)，經(jīng)過(guò)一系列插入操作后，可生成一棵二叉排序樹(shù)。 例如，K=18, 73, 10, 05, 68, 99, 27, 41, 51, 32, 251873100568992741513225圖7.7 二叉排序樹(shù) 的生成過(guò)程示例 容易看出，中序遍歷可以得到一個(gè)關(guān)鍵字的有序序列，這就是說(shuō)，一個(gè)無(wú)序序列可以通過(guò)構(gòu)造一棵二叉排序樹(shù)而變成一個(gè)有序序列。 另外可以看到，每次插入的新結(jié)點(diǎn)都是樹(shù)中一個(gè)葉子結(jié)點(diǎn)，因此在進(jìn)行插入的時(shí)候不必移動(dòng)其他結(jié)點(diǎn)，僅需改動(dòng)某個(gè)結(jié)點(diǎn)的指針。由此可見(jiàn)： 二叉排序樹(shù)既有折半查找的特性，又采用了鏈表

33、作存儲(chǔ)結(jié)構(gòu)。因此是動(dòng)態(tài)查找表的適宜結(jié)構(gòu)。刪除二叉排序樹(shù)的某個(gè)指定結(jié)點(diǎn)后，仍然是二叉排序樹(shù)。假設(shè)指針p指向要?jiǎng)h除的結(jié)點(diǎn), 指針parentp指向*p的父結(jié)點(diǎn)。 1. 若*p是葉子結(jié)點(diǎn)，由于刪除葉子結(jié)點(diǎn)不破壞整棵樹(shù)的結(jié)構(gòu)，因此，只需要修改其雙親結(jié)點(diǎn)的指針。 2. 若*p只有左子樹(shù)PL或只有右子樹(shù)PR，此時(shí)，只要令PL或PR的根結(jié)點(diǎn)直接代替*p即可.PR*p*parentpPl*p*parentp*parent *p PR*parent Pl *p二叉排序樹(shù)結(jié)點(diǎn)的刪除二叉排序樹(shù)結(jié)點(diǎn)的刪除3. 若*p的左右子樹(shù)均不空，則從下圖可知,在刪除 *p 之前，中序遍歷該二叉樹(shù)得到的序列為L(zhǎng) *p R 刪除*p

34、之后，為保持其它元素之間的相對(duì)位置不 變，可以有兩種做法。rrLRr*pLRr第一種方法：令*p的左子樹(shù)的根結(jié)點(diǎn)代替*p ，而*p的右子樹(shù)為 的右子樹(shù); 在p的左子樹(shù)中找出關(guān)鍵碼最大的結(jié)點(diǎn)r，將r的右指針指向p的右子女，用p的左子女代替p結(jié)點(diǎn)。4518731059927415132257.8 刪除結(jié)點(diǎn)73的過(guò)程p為被刪除的結(jié)點(diǎn)r為p的左子樹(shù)中關(guān)鍵碼最大的的結(jié)點(diǎn) 在p的左子樹(shù)中找出關(guān)鍵碼最大的結(jié)點(diǎn)r，將r的右指針指向p的右子女，用p的左子女代替p結(jié)點(diǎn)。4518731059927415132257.8 刪除結(jié)點(diǎn)73的過(guò)程p為被刪除的結(jié)點(diǎn)r為p的左子樹(shù)中關(guān)鍵碼最大的的結(jié)點(diǎn) 在p的左子樹(shù)中找出關(guān)鍵碼最

35、大的結(jié)點(diǎn)r，將r的右指針指向p的右子女，用p的左子女代替p結(jié)點(diǎn)。181057.8 刪除結(jié)點(diǎn)73的過(guò)程p為被刪除的結(jié)點(diǎn)45992741513225r為p的左子樹(shù)中關(guān)鍵碼最大的的結(jié)點(diǎn)第二種方法： （a）按對(duì)稱序周游p的左子樹(shù)，找到關(guān)鍵碼最大的 結(jié)點(diǎn)r，刪除r（用r的左子女代替r）； （b）用r結(jié)點(diǎn)代替被刪除結(jié)點(diǎn)p。LRr*pLRrL r *p RL r R 刪除r（用r的左子女代替r），用r結(jié)點(diǎn)代替被刪除結(jié)點(diǎn)p 。4518731059927415132257.8 刪除結(jié)點(diǎn)73的過(guò)程p為被刪除的結(jié)點(diǎn)r為p的左子樹(shù)中關(guān)鍵碼最大的的結(jié)點(diǎn) 刪除r（用r的左子女代替r），用r結(jié)點(diǎn)代替被刪除結(jié)點(diǎn)p 。4518

36、5110599274132257.8 刪除結(jié)點(diǎn)73的過(guò)程p為被刪除的結(jié)點(diǎn)r為p的左子樹(shù)中關(guān)鍵碼最大的的結(jié)點(diǎn) 查找被刪除結(jié)點(diǎn)*p； if(*p無(wú)左子女) 用*p的右子女代替*p； else 找*p的左子樹(shù)中最右下結(jié)點(diǎn)*r； 用*r的右指針指向*p的右子女； 用*p的左子女代替*p； 算法 7.4 從二叉排序樹(shù)上刪除一個(gè)結(jié)點(diǎn)算法算法7.4 7.4 二叉排序樹(shù)的刪除算法二叉排序樹(shù)的刪除算法int delete(PBinSearch ptree, KeyTypeint delete(PBinSearch ptree, KeyType key) key) PBinSearchNode parentp P

37、BinSearchNode parentp, p, r;, p, r; p= p=* *ptree; parentpptree; parentp=NULL;=NULL; while(p while(p!=NULL) !=NULL) if(p-key=key if(p-key=key) break; ) break; / /* * 找到了關(guān)鍵碼為找到了關(guān)鍵碼為keykey的結(jié)點(diǎn)的結(jié)點(diǎn) * */ / parentp parentp=p;=p; if(p-keykey)p=p-llink if(p-keykey)p=p-llink; ; / /* *進(jìn)入左子樹(shù)進(jìn)入左子樹(shù) * */ / else p=

38、p-rlink else p=p-rlink; ; / /* *進(jìn)入右子樹(shù)進(jìn)入右子樹(shù) * */ / if(p if(p=NULL) return 0;=NULL) return 0; / /* * 二叉排序樹(shù)中無(wú)關(guān)鍵碼為二叉排序樹(shù)中無(wú)關(guān)鍵碼為keykey的結(jié)點(diǎn)的結(jié)點(diǎn) * */ /if(p-llinkif(p-llink=NULL) =NULL) / /* *結(jié)點(diǎn)結(jié)點(diǎn)* *p p無(wú)左子樹(shù)無(wú)左子樹(shù)* */ / if(parentp=NULL) if(parentp=NULL) * *ptree=p-rlinkptree=p-rlink; ; / /* *被刪除的結(jié)點(diǎn)是原二叉排序樹(shù)的根結(jié)點(diǎn)被刪除的結(jié)

39、點(diǎn)是原二叉排序樹(shù)的根結(jié)點(diǎn)* */ / else if(parentp-llink=p) parentp-llink=p-rlink else if(parentp-llink=p) parentp-llink=p-rlink; ; / /* * 將將* *p p的右子樹(shù)鏈到其父結(jié)點(diǎn)的左鏈上的右子樹(shù)鏈到其父結(jié)點(diǎn)的左鏈上 * */ / else parentp-rlink=p-rlink else parentp-rlink=p-rlink; ; / /* * 將將* *p p的右子樹(shù)鏈到其父結(jié)點(diǎn)的右鏈上的右子樹(shù)鏈到其父結(jié)點(diǎn)的右鏈上 * */ / else else / /* *結(jié)點(diǎn)結(jié)點(diǎn)* *p

40、p有左子樹(shù)有左子樹(shù)* */ / r=p-llink r=p-llink; ; while(r-rlink!=NULL) r=r-rlink while(r-rlink!=NULL) r=r-rlink; ; / /* * 在在* *p p的左子樹(shù)中找最右下結(jié)點(diǎn)的左子樹(shù)中找最右下結(jié)點(diǎn)* *r r * */ / r-rlink=p-rlink r-rlink=p-rlink; ;/ /* * 用用* *r r的右指針指向的右指針指向* *p p的右子女的右子女 * */ / if(parentp=NULL) if(parentp=NULL) * *ptree=p-llinkptree=p-llin

41、k; ; else if(parentp-llink=p)parentp-llink=p-llink else if(parentp-llink=p)parentp-llink=p-llink; ; else parentp-rlink=p-llink else parentp-rlink=p-llink; ; free(p free(p););return 1; return 1; / /* * 釋放被刪除結(jié)點(diǎn)釋放被刪除結(jié)點(diǎn) * */ / 性能分析 在二叉排序樹(shù)上查找關(guān)鍵字實(shí)際上是走了一條從根結(jié)點(diǎn)到某個(gè)結(jié)點(diǎn)的路徑的過(guò)程，比較的次數(shù)等于路徑長(zhǎng)度加1。因此，比較的次數(shù)不超過(guò)樹(shù)的深度+1。但是具有

42、n個(gè)結(jié)點(diǎn)的二叉樹(shù)可以有不同的形態(tài)，因此，對(duì)于不同形態(tài)的二叉排序樹(shù)，其平均查找長(zhǎng)度也是不同的。最壞的情況下蛻變?yōu)閱沃?shù)，此時(shí)的平均查找長(zhǎng)度為（n+1)/2。 在隨機(jī)的情況下，平均性能為：P(n) = 2(1+1/n) ln n 由此可見(jiàn)，在隨機(jī)情況下的平均查找長(zhǎng)度和ln n是等數(shù)量級(jí)的，然而在某些情況下，還需進(jìn)行“平衡化”處理。 n個(gè)結(jié)點(diǎn)按不同的次序插入到二叉排序樹(shù)中，有n!棵二叉排序樹(shù)(其中有的形態(tài)相同) 。271005734151991825051018252741517399圖7.9 由同一組關(guān)鍵碼構(gòu)成的兩棵形態(tài)不同的二叉排序樹(shù)7.4 7.4 最佳二叉排序樹(shù)最佳二叉排序樹(shù)* *平衡二叉樹(shù)定

43、義 平衡二叉樹(shù)又稱AVL樹(shù)。它或者是一棵空樹(shù)，或者是具有下列性質(zhì)的二叉樹(shù)：它的左右子樹(shù)均為平衡二叉樹(shù)，且左右子樹(shù)的深度之差的絕對(duì)值不超過(guò)1。 若定義二叉樹(shù)上結(jié)點(diǎn)的平衡因子BF(Balance Factor)為該結(jié)點(diǎn)的右子樹(shù)的高度減去左子樹(shù)的高度，在平衡二叉樹(shù)上所有結(jié)點(diǎn)平衡因子只可能為-1, 0, 1。只要二叉樹(shù)上有一個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值大于1，則該二叉樹(shù)就是不平衡的。 對(duì)于平衡二叉樹(shù)來(lái)說(shuō)，它的深度和logN是同數(shù)量級(jí)的，因此我們希望任何初始序列構(gòu)成的二叉排序樹(shù)都是AVL樹(shù)。 -1-1-110001-1-200-1圖7.14 平衡和不平衡二叉樹(shù)示例最小不平衡子樹(shù): 指離插入結(jié)點(diǎn)最近，且以平衡

44、因子絕對(duì)值大于1的結(jié)點(diǎn)為根的子樹(shù)。27105118412500-1-112圖 6.13 最小不平衡子樹(shù)插入結(jié)點(diǎn)7.5.2 7.5.2 調(diào)整平衡的模式調(diào)整平衡的模式 設(shè)最小不平衡子樹(shù)的根為A，調(diào)整的規(guī)律可歸納為下列四種： 1. LL型調(diào)整； 2. RR型調(diào)整； 3. LR型調(diào)整； 4. RL型調(diào)整； 上面的幾種情況在經(jīng)過(guò)平衡旋轉(zhuǎn)處理后，以*b或*c為根的新子樹(shù)為平衡二叉樹(shù)，而且它的深度和插入之前以*a為根的子樹(shù)相同。因此，當(dāng)平衡的二叉排序樹(shù)因插入結(jié)點(diǎn)而失去平衡時(shí)，僅需對(duì)最小不平衡子樹(shù)進(jìn)行旋轉(zhuǎn)處理即可。 A A B B B A h h h+1 h h h h h h -1 0 -2 1 0 0 L

45、L型調(diào)整操作示意圖 (B)A()= ()B(A) 調(diào)整規(guī)則是將A的左子女B提升為新二叉樹(shù)的根；原來(lái)的根A連同其右子樹(shù)向右下旋轉(zhuǎn)成為B的右子樹(shù)；B的原右子樹(shù)作為A的左子樹(shù)。 27100-1BA27100-1BA05-2271000BA05051270-1BA100051800030-1-1-251270BA10005180030-10圖6.15 LL型調(diào)整操作示例 A A B B B A h h h+1 h h h h h h 1 0 0 0 2 1 RR型調(diào)整操作示意圖 ()A(B)= (A)B() 調(diào)整規(guī)則：將A的右子女B提升為新二叉樹(shù)的根；原來(lái)的根A連同其左子樹(shù)向左下旋轉(zhuǎn)成為B的左子樹(shù)；B

46、的原左子樹(shù)作為A的右子樹(shù)。 275101BA275101BA732735100BA27051270 1BA1007341099730BA510274101000-1圖6.17 RR型調(diào)整操作示例0990 1 12 A A C B B B A h h C C h h h h h-1 h h-1 h-1 h h-1 -1 -2 0 1 0 1 0 0 -1 LR型調(diào)整操作示意圖 ()B(C)A()= (B)C(A) 調(diào)整規(guī)則設(shè)C為A的左子女的右子女，將A的孫子結(jié)點(diǎn)C提升為新二叉樹(shù)的根；原C的父結(jié)點(diǎn)B連同其左子樹(shù)向左下旋轉(zhuǎn)成為新根C的左子樹(shù)，原C的左子樹(shù)成為B的右子樹(shù)；原根A連同其右子樹(shù)向右下旋轉(zhuǎn)成

47、為新根C的右子樹(shù)，原C的右子樹(shù)成為A的左子樹(shù)。 51270-1BA100051800C51270CA180101600500 1B圖6.19 LR型調(diào)整操作示例5127 1BA10005180-1C160-2 A A C B B A B h h C C h h h h h-1 h h-1 h-1 h h-1 0 1 0 0 -1 0 1 2 RL型調(diào)整操作示意圖 ()A(C)B()= (A)C(B) 調(diào)整規(guī)則：設(shè)C為A的右子女的左子女，將A的孫子結(jié)點(diǎn)C提升為新二叉樹(shù)的根，原來(lái)C的父結(jié)點(diǎn)B連同其右子樹(shù)向右下旋轉(zhuǎn)成為新根C的右子樹(shù)，C的原右子樹(shù)成為B的左子樹(shù)；原來(lái)的根A連同其左子樹(shù)向左下旋轉(zhuǎn)成為新

48、根C的左子樹(shù)，原來(lái)C的左子樹(shù)成為A的右子樹(shù)。 51270 1BA1007341073510CA410B273001000 1圖6.21 RL型調(diào)整操作示例000C51270 1BA1007341-103000-1 2C 設(shè) 在平衡二叉樹(shù)上插入一個(gè)關(guān)鍵碼為key的結(jié)點(diǎn),二叉樹(shù)采用llink_rlink表示，結(jié)點(diǎn)中增加一個(gè)字段存儲(chǔ)結(jié)點(diǎn)的平衡因子。算法中包括以下幾個(gè)部分：6.5.2 6.5.2 插入元素的算法插入元素的算法（1）找最小不平衡子樹(shù)。找插入位置時(shí)，令*A離插入位置最近，且平衡因子不為0的結(jié)點(diǎn)，若這樣的結(jié)點(diǎn)不存在，則A指向根結(jié)點(diǎn)；若插入后使AVL樹(shù)失去平衡，則*A是最小不平衡子樹(shù)的根。（2

49、）修改一些結(jié)點(diǎn)的平衡因子 路徑： *A， ，新結(jié)點(diǎn)。插入前，僅*A的平衡因子不為0。插入后，從*A的子女開(kāi)始，順序掃描路徑上的結(jié)點(diǎn)*P,若新結(jié)點(diǎn)插入*P的左子樹(shù)中，則*P平衡因子變?yōu)?；否則變?yōu)?1。 (3)判別以*A為根的子樹(shù)是否失去了平衡。 若*A的平衡因子為0，則插入后不會(huì)； 若*A的平衡因子為1，且插入到*A的左子樹(shù)，則失去平衡，進(jìn)一步，若插入到*A的左子女的左子樹(shù)，則采用LL型調(diào)整；若插入到*A的左子女的右子樹(shù)，則采用LR型調(diào)整; 若*A的平衡因子為-1, 且插入到*A的右子樹(shù),則失去平衡，進(jìn)一步,若插入到*A的右子女的右子樹(shù),則采用RR型調(diào)整;若插入到*A的右子女的左子樹(shù),則采用R

50、L型調(diào)整;算法算法6.10 AVL樹(shù)的檢索和插入性能分析 含有n個(gè)結(jié)點(diǎn)的平衡二叉樹(shù)的高度是h= O(log2n)。插入關(guān)鍵碼為key的結(jié)點(diǎn)的時(shí)間耗費(fèi)最大為樹(shù)的深度O(log2n)。算法在查找插入結(jié)點(diǎn)的同時(shí)也找到最小不平衡子樹(shù)。最小不平衡子樹(shù)中平衡因子的調(diào)整時(shí)間最大為最小不平衡子樹(shù)的深度。而四種子樹(shù)調(diào)整時(shí)間耗費(fèi)為常數(shù)O( 1 ).因此， 整個(gè)算法的時(shí)間復(fù)雜度為 O(log2n). 最佳二叉排序樹(shù)的檢索效率是最好的，但是，當(dāng)進(jìn)行結(jié)點(diǎn)的插入或刪除操作后，保持其最佳性的時(shí)間代價(jià)太大。平衡二叉排序樹(shù)的檢索效率與最佳二叉排序樹(shù)的檢索效率是同級(jí)的，因此，動(dòng)態(tài)字典常采用平衡二叉排序樹(shù)作為存儲(chǔ)結(jié)構(gòu)。 B樹(shù)和B樹(shù)

51、用于外存文件的索引。 6.6.1 B樹(shù) 6.6.2 B+樹(shù)一、B樹(shù)的定義 一棵m階的B樹(shù)，或?yàn)榭諛?shù)，或是滿足下列特性的m叉樹(shù)： （1）樹(shù)中每個(gè)結(jié)點(diǎn)至多有m棵子樹(shù)； （2） 除根之外的所有分支結(jié)點(diǎn)至少有m/2棵子樹(shù)； （3）若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少有兩棵子樹(shù)； （4） 有j個(gè)子女的非葉結(jié)點(diǎn)中恰好有j-1個(gè)關(guān)鍵碼， 且 按遞增順 序排列，結(jié)點(diǎn)中包含的信息為 (p0, k1, p1, k2, , kj-1, pj)6.6 .1 B6.6 .1 B樹(shù)樹(shù) 其中ki(i=1,.,j-1)為關(guān)鍵碼，且ki ki+1(i=1,j-2); pi(i=0,j-1)為指向子樹(shù)根結(jié)點(diǎn)的指針，且pi-1所指子樹(shù)中所

52、有結(jié)點(diǎn)的關(guān)鍵碼均小于ki(i=1,j-1), pj-1所指子樹(shù)中所有結(jié)點(diǎn)的關(guān)鍵碼均大于kj, j（ m/2 = j = m-1）為關(guān)鍵碼的個(gè)數(shù)。 （ 5）所有葉子結(jié)點(diǎn)都在同一層上，實(shí)際上這些 結(jié)點(diǎn)不存在。 當(dāng)m=2時(shí)，m階B樹(shù)實(shí)際上就是二叉排序樹(shù)。所以m階B樹(shù)是二叉排序樹(shù)的推廣。其查找過(guò)程和二叉排序樹(shù)類似，它是一個(gè)沿指針查找結(jié)點(diǎn)和在結(jié)點(diǎn)的關(guān)鍵碼中進(jìn)行順序查找交叉進(jìn)行的過(guò)程。 實(shí)際應(yīng)用中， m和內(nèi)外存交換的單位有關(guān)，一般，m=1024 040008375045 112 236392 490 560 631 670110050212142135279240237388381378471435400

53、396393553502492629626557660652633678673671圖6.22 一棵6階的B樹(shù)B樹(shù)主要用于文件的索引 。結(jié)點(diǎn)類型可以如下說(shuō)明：#define m3typedef struct BTNode int keyNum; /* 關(guān)鍵字個(gè)數(shù) */ struct BTNode *parent; /* 指向父結(jié)點(diǎn)*/ KeyType keym+1; /* 關(guān)鍵字向量 */ struct BTNode *ptrm+1; /* 子樹(shù)指針向量 */ Record *recPtrm+1; /* 指向文件中的記錄號(hào) */ BTNode, *BTree;二. B樹(shù)的運(yùn)算 1. B樹(shù)的檢索

54、 key ki ki+1 pi 首先在根結(jié)點(diǎn)的關(guān)鍵碼集合中進(jìn)行檢索，若key= = ki ，則檢索成功；否則， key一定在ki 和 ki+1 之間（存在某個(gè)i），沿pi繼續(xù)查找，重復(fù)上述過(guò)程，直到檢索成功，或pi為空，檢索失敗。性能分析 在B樹(shù)是進(jìn)行查找包含兩種基本操作：（1）在B樹(shù)中找結(jié)點(diǎn)；（2）在結(jié)點(diǎn)中找關(guān)鍵字。由于B樹(shù)通常存儲(chǔ)在磁盤上，因此前一操作是在磁盤上進(jìn)行的，而后一操作是在內(nèi)存中進(jìn)行的，即在磁盤上找到指針p所指結(jié)點(diǎn)后，先將結(jié)點(diǎn)中信息讀入內(nèi)存，然后查詢。而在磁盤上進(jìn)行操作比在內(nèi)存中操作慢得多，因此在磁盤上進(jìn)行查找的次數(shù)，即待查關(guān)鍵字所在結(jié)點(diǎn)在B樹(shù)是的層次數(shù)，是決定B樹(shù)查找效率的關(guān)鍵

55、因素。 現(xiàn)在考慮最壞的情況：含n個(gè)關(guān)鍵字的m階B樹(shù)的最大深度為log m/2(n+1)/2 + 12. B樹(shù)的插入 深度為h的m階B樹(shù)，新結(jié)點(diǎn)一般插入到h層，首先檢索到第h層，確定插入結(jié)點(diǎn)位置。 （1）若被插入結(jié)點(diǎn)中關(guān)鍵碼個(gè)數(shù)小于m-1，則插入。 （2）若被插入結(jié)點(diǎn)中關(guān)鍵碼個(gè)數(shù)等于m-1，則引起 結(jié)點(diǎn)“分裂”。 可如下實(shí)現(xiàn)“分裂”： 假設(shè)*p結(jié)點(diǎn)中含有信息為：m,p0, (k1,p1), , (km, pm)將*p分裂為*p和*p兩個(gè)結(jié)點(diǎn)，分別含有信息為： *p ： m/21, p0, (k1,p1), (k m/21,pm/21) *p：(m- m/2, pm/2, (k m/2+1, p

56、m/2+1), (km, pm)把關(guān)鍵字k m/2和指針*p一起插入到*p的雙親結(jié)點(diǎn)中。 375 400 045 112 236 375 400 560 631 670040 008110 050212 142135297 240237388 381378471 460435396 393553 502492629 626557圖6.23 一棵6階B樹(shù)的插入示例3. B樹(shù)的刪除 在深度為h的m階B樹(shù)中刪除一個(gè)關(guān)鍵碼，首先檢索到該關(guān)鍵碼所在的結(jié)點(diǎn),然后根據(jù)不同情況進(jìn)行刪除。（1)若結(jié)點(diǎn)在第h層，且關(guān)鍵碼數(shù)目大于m/2-1， 則只需從該結(jié)點(diǎn)中刪去該關(guān)鍵碼ki。（2）若結(jié)點(diǎn)在第h層，且關(guān)鍵碼數(shù)目等于

57、m/2-1， 該結(jié)點(diǎn)左兄弟（或右兄弟）結(jié)點(diǎn)中的關(guān)鍵碼數(shù)目 大于m/21，則需調(diào)整被刪除關(guān)鍵碼的結(jié)點(diǎn)， 兄弟結(jié)點(diǎn)，以及父結(jié)點(diǎn)中的信息。方法：設(shè)父結(jié) 點(diǎn) 中的信息為：（p0, k1,p1,k2,p2,kxpx),由pi指向 被刪除關(guān)鍵碼的結(jié)點(diǎn)，其的信息為： （p 0, k 1,p 1,k 2,p 2,k y p y), 兄弟結(jié)點(diǎn)中的 信息為：（p 0, k 1 ,p 1 ,k 2 ,p 2 ,k z p z)。 則應(yīng)將k(x+y)/2上移到父結(jié)點(diǎn)中，并將左（或右） 兄第中大于（或小于） k(x+y)/2及父結(jié)點(diǎn)中的ki移 到被刪除關(guān)鍵碼的結(jié)點(diǎn)中。 (3) 若結(jié)點(diǎn)在h層，且關(guān)鍵碼數(shù)目及其相鄰的兄弟結(jié)

58、 點(diǎn)中的關(guān)鍵碼數(shù)目均等于m/21，則需合并結(jié) 點(diǎn)。假設(shè)該結(jié)點(diǎn)有右兄弟，且其右兄弟結(jié)點(diǎn)由雙 親結(jié)點(diǎn)中的指針pi所指，則在刪去關(guān)鍵碼之后， 它所在結(jié)點(diǎn)中剩余的關(guān)鍵碼和指針，加上雙親結(jié) 點(diǎn)中的關(guān)鍵碼ki一起，合并到pi所指兄弟結(jié)點(diǎn)中 （若沒(méi)有右兄弟結(jié)點(diǎn)，則合并到左兄弟結(jié)點(diǎn)中）。(4) 若結(jié)點(diǎn)的層數(shù)小于h，設(shè)刪除結(jié)點(diǎn)中第i個(gè)關(guān)鍵碼 ki ，則用pi所指的子樹(shù)中的最小關(guān)鍵碼k與ki互換，然后再刪除關(guān)鍵碼ki 。 50 63 20 35 23 30 66 90 56 42 3 7 3035 （a) 一棵三階B樹(shù) 圖6.24 (b) 從（a)中刪除關(guān)鍵碼66 （c) 從(b)中刪除關(guān)鍵碼42 50 63 2

59、0 3023 90 56 35 3 7 （d) 從 ( c ) 中刪除關(guān)鍵碼35圖6.24 (e) 從（d)中刪除關(guān)鍵碼56 23 30 56 20 50 3 7 23 30 63 90 50 63 20 3023 90 56 35 3 7 （d) 從 ( c ) 中刪除關(guān)鍵碼35圖6.24 (e) 從（d)中刪除關(guān)鍵碼56 23 30 56三. B樹(shù)在索引文件中的應(yīng)用 (B, ) (E, ) (C, ) (D, ) (F, ) (G, ) (A, ) 圖6.25 用B樹(shù)組織索引順序文件B+樹(shù)是B樹(shù)的變形。一. B+樹(shù)的定義： 一棵m階的B樹(shù)，或?yàn)榭諛?shù)，或是滿足下列條件的m叉樹(shù)： （1）樹(shù)中每

60、個(gè)結(jié)點(diǎn)至多有m棵子樹(shù)； （2） 除根之外的所有分支結(jié)點(diǎn)至少有m/2棵子樹(shù)； （3）若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少有兩棵子樹(shù)； （4） 有n棵子樹(shù)的結(jié)點(diǎn)有n個(gè)關(guān)鍵碼； （5）葉結(jié)點(diǎn)中存放數(shù)據(jù)文件中記錄的關(guān)鍵碼及指向該記錄的指針（或存放數(shù)據(jù)文件分塊后每塊的最大關(guān)鍵碼及指向該塊的指針。葉結(jié)點(diǎn)按關(guān)鍵碼值大小順 序 鏈接?？梢园衙總€(gè)葉結(jié)點(diǎn)看成一個(gè)基本索引塊。 6.6 .2 B+6.6 .2 B+樹(shù)樹(shù) (6) 所有分支結(jié)點(diǎn)可看成是索引的索引，使結(jié)點(diǎn)中僅包含它的各子結(jié)點(diǎn)中最大（或最小）關(guān)鍵碼及指向子結(jié)點(diǎn)的指針。一棵m階的B樹(shù)和B樹(shù)的差異在于： （A）有n棵子樹(shù)的結(jié)點(diǎn)中含有n個(gè)關(guān)鍵碼； （B）所有的葉子結(jié)點(diǎn)中包

61、含了全部關(guān)鍵碼的信息，及指向含這些關(guān)鍵碼記錄的指針，且葉子結(jié)點(diǎn)的本身依關(guān)鍵碼的大小從小到大順序鏈接。 （C）所有的非終端結(jié)點(diǎn)可以看成是索引部分，結(jié)點(diǎn)中僅含有其子樹(shù)（根結(jié)點(diǎn)）中最大（或最?。╆P(guān)鍵碼。 通常在B樹(shù)上有兩個(gè)頭指針，一個(gè)指向根結(jié)點(diǎn)，另一個(gè)指向關(guān)鍵碼最小的葉子結(jié)點(diǎn)。 60 99 85 99 20 39 60 27 36 39 92 99 65 79 85 46 51 60 10 20圖6.26 一棵三階的B+樹(shù) 二. B+樹(shù)的運(yùn)算 1. B+樹(shù)的檢索 (1) 和B樹(shù)的檢索方式相似。從根結(jié)點(diǎn)開(kāi)始進(jìn)行隨 機(jī)檢索， key一定在ki 和 ki+1 之間（存在個(gè)i）， 沿pi繼續(xù)查找，重復(fù)上述過(guò)

62、程，直到檢索到葉 結(jié)點(diǎn)，若key = = ki ，則檢索成功；否則檢索 失敗。 （2） 從最小關(guān)鍵碼開(kāi)始沿葉結(jié)點(diǎn)鏈順序檢索。 2 . B+樹(shù)的插入 和B樹(shù)的插入相似，但總是在葉結(jié)點(diǎn)上進(jìn)行，當(dāng) 結(jié)點(diǎn)中原關(guān)鍵碼個(gè)數(shù)等于m時(shí)，該結(jié)點(diǎn)分裂。 (3) B+樹(shù)的刪除 僅在葉結(jié)點(diǎn)中進(jìn)行刪除操作，在和兄第結(jié)點(diǎn)合并 時(shí)，父結(jié)點(diǎn)中作為分界的關(guān)鍵碼不放入合并后的結(jié) 點(diǎn)中。三. B+樹(shù)在索引順序文件中的應(yīng)用 主文件的每個(gè)頁(yè)塊作B+樹(shù)的一個(gè)外部結(jié)點(diǎn)，并且 這些頁(yè)塊之間連成單鏈。 B+樹(shù)的樹(shù)葉層是主文件的 稀疏索引，整個(gè)B+樹(shù)構(gòu)成多級(jí)索引。索引項(xiàng)就是B+ 樹(shù)中一個(gè)關(guān)鍵碼和它對(duì)應(yīng)的指針?biāo)鶚?gòu)成的二元組。 A D D E A

63、B C 圖6.27 用B+樹(shù)組織索引順序文件1. 靜態(tài)字典（1）順序表示 A. 順序檢索：簡(jiǎn)單，常用于未排序元素的檢索， 但檢索效率不高； B. 二分法檢索：僅用于排序元素，檢索效率較高當(dāng)插入、刪除運(yùn)算時(shí)會(huì)引起大量數(shù)據(jù)的移動(dòng)。（2）散列表示：檢索操作達(dá)到近乎隨機(jī)存取的速度 。但散列表示經(jīng)常出現(xiàn)碰撞與堆積現(xiàn)象，增加 了檢索長(zhǎng)度。（3）二叉樹(shù)表示二叉排序樹(shù)：元素插入次序不同，會(huì)構(gòu)成不同的二叉排序樹(shù)。最佳二叉排序樹(shù) 的平均檢索長(zhǎng)度為O(log2n) 。2. 動(dòng)態(tài)字典 平衡二叉排序樹(shù)表示：維持較高的檢索效率。3. 對(duì)于較大的必須存放在外存貯器上的字典，應(yīng) 采用B樹(shù)或B+樹(shù)表示。B+樹(shù)是B樹(shù)的變種。B樹(shù)

64、 和B+樹(shù)都能動(dòng)態(tài)地調(diào)整，保持均衡，而使動(dòng)態(tài) 字典保持較高的檢索效率。小小 結(jié)結(jié) 字典是一種特殊的集合，其最主要的操作為字典中元素的檢索。本章介紹了字典的各種存儲(chǔ)表示及相應(yīng)的檢索方法，它們是字典的各種線性表示（例如：順序表表示，鏈表表示和目錄表表示等）、各種散列表示（例如：開(kāi)地址法、拉鏈法和桶散列等）、各種二叉樹(shù)表示（例如：一般的二叉排序樹(shù)、最佳二叉排序樹(shù)和平衡的二叉排序樹(shù)等）以及各種多叉樹(shù)表示（例如B樹(shù)和B+樹(shù)）。其中順序表示的線性表、開(kāi)地址法處理碰撞的散列表和最佳二叉排序樹(shù)主要使用于靜態(tài)或基本靜態(tài)的字典；鏈表表示的線性表、拉鏈法處理碰撞的散列表、桶散列結(jié)構(gòu)、平衡的二叉排序樹(shù)、B樹(shù)和B+樹(shù)等較多地考慮到元素的動(dòng)態(tài)處理，適合于組織各種動(dòng)態(tài)的字典；其中B樹(shù)、B+樹(shù)和桶散列結(jié)構(gòu)主要使用于外存的大型字典表示。 l作業(yè)：p.243 復(fù)習(xí)題 1、7、8 p.244 算法題 1l網(wǎng)絡(luò)課堂測(cè)試：6 字典與高級(jí)字典l上機(jī)：實(shí)驗(yàn)5.4