《算法與數據結構》教學課件第6章 字典和高級字典C語言描述（第2版）張乃孝編著

6.1 集合及其抽象數據類型*6.2 集合的實現*6.3 字典及其抽象數據類型6.4 字典的順序表示6.5 字典的散列表示6.3 字典及其抽象數據類型6.3.1 基本概念 字典：是一種集合，其中每個元素由兩部分組成，分別稱為關鍵碼和屬性。這種包含關鍵碼和屬性得二元組稱作關聯。 對字典進行的操作主要有：檢索、插入元素和刪除元素。字典中最主要的運算是進行檢索。 靜態(tài)字典：一經建立就基本保持不變； 動態(tài)字典：經常需要改動。 存儲方法存儲方法：順序法、散列法、二叉樹法和B樹。 存儲方法的選擇：考慮檢索效率、元素的插入和刪除是否簡便。 檢索效率的標準檢索效率的標準：檢索過程中和關鍵碼的平均比較次數，即平均檢索長度ASL，定義為： ASL = pici 每個元素的檢索概率相等時， pi=1/n。ni=16.3.2 抽象數據類型抽象數據類型ADT6.2 字典的抽象數據類型字典的抽象數據類型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 dictionary字典的順序表示定義如下typedef int KeyType;typedef int DataType;typedef struct KeyType key; /* 字典元素的關鍵碼字段字典元素的關鍵碼字段*/DataType value; /* 字典元素的屬性字段字典元素的屬性字段*/DicElement;typedef struct int MAXNUM;int n; /*字典中元素的個數字典中元素的個數 */ DicElement *element; SeqDictionary; 6.4.1 6.4.1 存儲結構存儲結構算法算法6.11 順序檢索算法順序檢索算法int seqSearch(SeqDictionary *pdic, KeyType key, int &position) /*在字典中順序檢索關鍵碼為在字典中順序檢索關鍵碼為key的元素的元素*/int i; for(i=0; in; i+) /* 從頭開始向后掃描從頭開始向后掃描*/ if(pdic-elementi.key=key) position=i; return(1); /* 檢索成功檢索成功 */ position=pdic-n;return(0); /* 檢索失敗檢索失敗 */6.4.2 6.4.2 算法的實現算法的實現l算法算法6.11 6.11 順序檢索算法順序檢索算法ASL = 1*p1 +2* p2 + +n* pn = (1+2+n)/n (pi=1/n) = (n+1)/2=O(n) 優(yōu)點是算法簡單且適應面廣，無論字典中元素是否有序均可使用。缺點是平均檢索長度較大，特別是當n很大時，檢索效率較低。6.4.2 6.4.2 算法的實現算法的實現6.4.3 有序順序表與二分法檢索 按照關鍵碼大小排序的順序表稱為有序順序表。 二分法檢索又稱折半檢索。要求字典的元素在順序表中按關鍵碼排序（從小到大）。 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,51,68,73,99檢索關鍵碼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檢索關鍵碼75l算法算法6.12 6.12 二分法檢索算法二分法檢索算法 條件：字典中的元素按關鍵碼排序。 優(yōu)點是比較次數少，檢索速度快。缺點是要將字典按關鍵碼排序，且只適用于順序存儲結構。算法算法6.12二分法檢索算法二分法檢索算法int binarySearch(SeqDictionary * pdic, KeyType key, int &position) /* 在字典中用二分法查找關鍵碼為在字典中用二分法查找關鍵碼為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; /* 要檢索的元素在右半區(qū)要檢索的元素在右半區(qū) */ position=low; return(0); /* 檢索失敗檢索失敗 */折半查找的判定樹l用一棵二叉樹來描述折半用一棵二叉樹來描述折半查找過程：二叉樹結點中查找過程：二叉樹結點中的數值表示有序表記錄中的數值表示有序表記錄中的序號。的序號。虛黑線虛黑線表示查找表示查找2525比較過的記錄，比較過的記錄，虛紅線虛紅線表示查找表示查找7575經過的記錄。經過的記錄。記錄在判定樹上的層次恰記錄在判定樹上的層次恰為找到此記錄時所需比較為找到此記錄時所需比較的次數。的次數。l設每個記錄查找概率相等，設每個記錄查找概率相等，查找成功的平均查找長度：查找成功的平均查找長度：ASL（12233334+4+4+4)/11=33/11=3321868254173515992710 05,10,18,25,27,32,41,51,68,73,996.5 6.5 字典的散列表示字典的散列表示 前面介紹的查找方法都是建立在前面介紹的查找方法都是建立在“比較比較”的基礎的基礎上，查找的效率依賴于查找過程中所進行比較的次數。上，查找的效率依賴于查找過程中所進行比較的次數。 理想的情況理想的情況是希望不進行任何比較，一次存取便能得是希望不進行任何比較，一次存取便能得到所查記錄。這樣就需要在關鍵碼和記錄的存儲位置到所查記錄。這樣就需要在關鍵碼和記錄的存儲位置之間建立一個確定的對應關系之間建立一個確定的對應關系. key 存儲地址存儲地址h 6.5.1 基本概念 6.5.2 散列函數 6.5.3 碰撞的處理 6.5.4 散列文件散列函數散列函數： 使每個關鍵碼都和結構中存儲位置對應使每個關鍵碼都和結構中存儲位置對應,這樣的一這樣的一個對應關系稱為個對應關系稱為散列（哈希散列（哈希Hash）函數）函數。 關鍵碼關鍵碼 存儲地址存儲地址碰撞碰撞：若：若key1 key2 ,h(key1)=h(key2). key1和和key2稱為稱為同義詞同義詞。h(key)的值域所對應的的值域所對應的地址空間稱為地址空間稱為基本區(qū)域基本區(qū)域。發(fā)生碰撞時，發(fā)生碰撞時，同義詞可以存放在同義詞可以存放在基本區(qū)域中未被占基本區(qū)域中未被占用的單元，也用的單元，也可以存放到另開的可以存放到另開的區(qū)域中。區(qū)域中。負載因子負載因子： 散列表中結點數散列表中結點數 基本區(qū)域能容納的結點數基本區(qū)域能容納的結點數6.5.1 基本概念h = 關鍵碼關鍵碼經過經過散列函數散列函數得到一個隨機地址，得到一個隨機地址，以便使一組關鍵碼的散列地址均勻地分布在以便使一組關鍵碼的散列地址均勻地分布在逐個地址區(qū)間中，從而減少沖突。逐個地址區(qū)間中，從而減少沖突。 常用的散列函數有：常用的散列函數有：1 1 數字分析法數字分析法2 2 折疊法折疊法 3. 3. 中平方法中平方法 4. 4. 基數轉換法基數轉換法 5. 5. 除余法除余法6.5.2 散列函數1. 數字分析法數字分析法 假設關鍵碼是以假設關鍵碼是以r為基的數，并且哈希表中可為基的數，并且哈希表中可能現的關鍵碼都是事先知道的，則可取關鍵碼的能現的關鍵碼都是事先知道的，則可取關鍵碼的若干數位組成散列地址。若干數位組成散列地址。 Key h(key) 000319426 326 000718309 709 000629443 643 000758615 715 000919697 997 000310329 3292. 折疊法折疊法 將關鍵碼分割成幾部分，然后取這幾部分的疊加和將關鍵碼分割成幾部分，然后取這幾部分的疊加和作為地址。作為地址。 key=582422241 58 | 2422 | 241 58 | 2422 | 241 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. 中平方法中平方法 先求出關鍵碼的平方，然后取中間幾位作為地址。先求出關鍵碼的平方，然后取中間幾位作為地址。 key=4731 (4731)2 = 22382361 h(key)=3824. 基數轉換法基數轉換法 把關鍵碼看成基數為把關鍵碼看成基數為r1的數，將它轉換成基數為的數，將它轉換成基數為r2的數，用數字分析法取中間幾位作為散列地址。的數，用數字分析法取中間幾位作為散列地址。r1和和r2最好互素。例如，最好互素。例如，key=236075, r1=13, r2=10, (236075)13=2*135+3*134+6*133+7*13+5 =(841547)10 h(key)=41545. 除余法除余法 取關鍵碼被某個不大于散列表長度取關鍵碼被某個不大于散列表長度m的數的數p除后所得余數為散列地址。數除后所得余數為散列地址。數p的選?。阂话愕倪x取：一般可選它為質數。可選它為質數。 h(key)=key % p; m=128, 256, 512, 1024 p=127, 251, 503, 1019實際工作中需視情況的不同而采用不同的散列函實際工作中需視情況的不同而采用不同的散列函數，通常需要考慮的因素有：數，通常需要考慮的因素有： A. 計算哈希函數所需時間計算哈希函數所需時間; B. 關鍵碼的長度關鍵碼的長度; C. 哈希表的大小哈希表的大小; D. 關鍵碼的分布情況關鍵碼的分布情況; E. 記錄的查找頻率。記錄的查找頻率?？傊强傊恰半s湊雜湊”出來的。出來的。 開地址法開地址法在在基本區(qū)域基本區(qū)域內形成一個內形成一個探查序列探查序列 Hi = (H(key) + di)MOD m, i = 1, 2, , k ( k m-1)其中：其中：m為表長，為表長，di為增量序列，可有多種取法：為增量序列，可有多種取法： A. di = 1, 2, 3, , m-1, 稱稱線性探查序列線性探查序列; B. di = i*h2(key), h2(key)是另一個是另一個散列函數，稱散列函數，稱 雙散列探查序列雙散列探查序列; C. di = 12, -12, 22, -22, , k2, -k2 (k m/2)稱為稱為二次探查序列二次探查序列； D. di = 偽隨機數序列，稱偽隨機數序列，稱偽隨機探查序列偽隨機探查序列。 當發(fā)生碰撞時，則沿探查序列進行查找，當發(fā)生碰撞時，則沿探查序列進行查找， 插插入時，直到找到一個空單元；查找時，或查找到入時，直到找到一個空單元；查找時，或查找到關健碼為關健碼為key的元素或查找到達一個空單元。例如：的元素或查找到達一個空單元。例如： K=18, 73, 10, 05, 68, 99, 27, 41, 51, 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 關鍵碼 1873100568992741513225 采用采用線性探測序列線性探測序列，容易出現，容易出現堆積堆積現象，即在處現象，即在處理同義詞的過程中又添加了非同義詞的沖突。理同義詞的過程中又添加了非同義詞的沖突。存儲結構存儲結構typedef int KeyTypetypedef int DataType;typedef struct KeyType key; DataType value;DicElement;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 HashDictionary; ; 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 space!”endl cout“Out of space!”endl; ; return NULL; return NULL; 在散列表上進行查找和構造散列表的過程基本一在散列表上進行查找和構造散列表的過程基本一致。給定致。給定key值，根據散列函數求得散列地址，若表值，根據散列函數求得散列地址，若表中沒有記錄，則查找不成功；否則比較關鍵碼，若中沒有記錄，則查找不成功；否則比較關鍵碼，若和給定值相等，則查找成功；否則根據造表時設定和給定值相等，則查找成功；否則根據造表時設定的沖突處理方法找的沖突處理方法找“下一地址下一地址”，直到散列表某個，直到散列表某個位置為空或表中所填記錄的關鍵碼等于給定值時為位置為空或表中所填記錄的關鍵碼等于給定值時為止。止。 算法算法6.14 散列表的檢索散列表的檢索算法算法6.15 散列表的插入散列表的插入散列表的查找散列表的查找算法算法6.14 散列表的檢索算法散列表的檢索算法用線性探查法解決碰撞用線性探查法解決碰撞int linearSearch(HashDictionary *phash, KeyType key, int *position) int d, inc; d=h(key);/* d為散列地址，散列函數為為散列地址，散列函數為h(key) */ for(inc=0; incm; inc+) if(phash-elementd.key=key) *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(linearSearch(phash, ele.key, &position) = 1 ) /* 散列表中已有關鍵碼為散列表中已有關鍵碼為key 的結點的結點 */ printf(“Findn”); else if(position!=-1) phash-elementposition = ele; /* 插入結點，忽略對插入結點，忽略對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, 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;雙散列函數法雙散列函數法 拉鏈法拉鏈法 設設基本區(qū)域基本區(qū)域長度為長度為m，建立，建立m條條鏈表，將所有關鏈表，將所有關鍵字為同義詞的記錄存儲在同一鍵字為同義詞的記錄存儲在同一條條線性鏈表中。線性鏈表中。 K=18, 73, 10, 05, 68, 99, 27, 41, 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 用拉鏈法解決碰撞 在外存上，同義詞表可以采用順序表或散列表。在外存上，同義詞表可以采用順序表或散列表。有時把存放同義詞的表稱為有時把存放同義詞的表稱為“桶桶”。 按按“桶桶”散列的文件由若干桶和一個桶目錄構散列的文件由若干桶和一個桶目錄構成成。6.5.4 散列文件 桶目錄桶：由若干頁塊組成每個頁塊存放若干記錄l作業(yè)：p. 198l復習題 2，3，4l算法題 3，4l網絡課堂測試: 6 集合與字典 l上機實驗5.2 5.3 5.67.3 7.3 二叉排序樹二叉排序樹7.4 7.4 最佳二叉排序樹最佳二叉排序樹* *7.5 7.5 平衡二叉排序樹平衡二叉排序樹 字典采用二叉排序樹作為存儲結構，既有較高的檢索效率，又具有鏈式存儲時元素插入、刪除操作的靈活性。 二叉排序樹二叉排序樹定義定義 二叉排序樹(Binary Sort Tree)或者是一棵空二叉樹；或者具有下列性質的二叉樹： A. 若它的左子樹不空，則左子樹上所有結點的 值均小于它的根結點的值； B. 若它的右子樹不空，則右子樹上所有結點 的值均大于它的根結點的值； C. 它的左右子樹也分別為二叉排序樹。實際上，折半查找法的判定樹就是一棵二叉排序樹。K= 18, 73, 10, 05, 68, 99, 27, 41, 51, 32, 251810739968272541325105圖7.5 二叉排序樹示例struct BinSearchNodestruct BinSearchNode; ;typedef struct BinSearchNode typedef struct BinSearchNode * *PBinSearchNodePBinSearchNode; ; struct BinSearchNode struct BinSearchNode KeyTypeKeyType key; key;/ /* * 結點的關鍵碼字段結點的關鍵碼字段 * */ / PBinSearchNode llink, rlinkPBinSearchNode llink, rlink; ; / /* * 二叉樹的左、右指針二叉樹的左、右指針 * */ / ; ; typedef struct BinSearchNode typedef struct BinSearchNode * *BinSearchTreeBinSearchTree; ;typedef BinSearchTree typedef BinSearchTree * *PBinSearchTreePBinSearchTree; ;二叉排序樹的存儲結構（llink_rlink)： L.keyT.keykey) 查左子樹；查左子樹； else 查右子樹；查右子樹； 算法7.1 二叉排序樹的檢索算法 TLR算法算法7.1 7.1 二叉排序樹的檢索算法二叉排序樹的檢索算法int search(PBinSearchTree ptree, KeyTypeint search(PBinSearchTree ptree, KeyType key, key, PBinSearchNode PBinSearchNode * *position)position) PBinSearchNode 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);position=q; return(0); 當樹中不存在關鍵字等于給定值的結點時，需要生成新結點并插入到二叉樹中。而新插入的結點必定是一個葉子結點，并且是查找不成功時查找路徑上訪問的最后一個結點的左孩子或右孩子結點。 算法： if ( 二叉排序樹中查不到該結點) 建立新結點； if (原二叉排序樹是空樹) 新結點作為根結點; else if (新結點key=key; p-llink=p-rlink=NULL; if(position=NULL) *ptree=p; else if(keykey) position-llink=p; /插入的左子樹插入的左子樹else position-rlink=p; /* 插入插入position的右子樹的右子樹 */ return 1; 若從空樹出發(fā)，經過一系列插入操作后，可生成一棵二叉排序樹。 例如，K=18, 73, 10, 05, 68, 99, 27, 41, 51, 32, 251873100568992741513225圖7.7 二叉排序樹 的生成過程示例 容易看出，中序遍歷可以得到一個關鍵字的有序序列，這就是說，一個無序序列可以通過構造一棵二叉排序樹而變成一個有序序列。 另外可以看到，每次插入的新結點都是樹中一個葉子結點，因此在進行插入的時候不必移動其他結點，僅需改動某個結點的指針。由此可見： 二叉排序樹既有折半查找的特性，又采用了鏈表作存儲結構。因此是動態(tài)查找表的適宜結構。刪除二叉排序樹的某個指定結點后，仍然是二叉排序樹。假設指針p指向要刪除的結點, 指針parentp指向*p的父結點。 1. 若*p是葉子結點，由于刪除葉子結點不破壞整棵樹的結構，因此，只需要修改其雙親結點的指針。 2. 若*p只有左子樹PL或只有右子樹PR，此時，只要令PL或PR的根結點直接代替*p即可.PR*p*parentpPl*p*parentp*parent *p PR*parent Pl *p二叉排序樹結點的刪除二叉排序樹結點的刪除3. 若*p的左右子樹均不空，則從下圖可知,在刪除 *p 之前，中序遍歷該二叉樹得到的序列為L *p R 刪除*p之后，為保持其它元素之間的相對位置不 變，可以有兩種做法。rrLRr*pLRr第一種方法：令*p的左子樹的根結點代替*p ，而*p的右子樹為 的右子樹; 在p的左子樹中找出關鍵碼最大的結點r，將r的右指針指向p的右子女，用p的左子女代替p結點。4518731059927415132257.8 刪除結點73的過程p為被刪除的結點r為p的左子樹中關鍵碼最大的的結點 在p的左子樹中找出關鍵碼最大的結點r，將r的右指針指向p的右子女，用p的左子女代替p結點。4518731059927415132257.8 刪除結點73的過程p為被刪除的結點r為p的左子樹中關鍵碼最大的的結點 在p的左子樹中找出關鍵碼最大的結點r，將r的右指針指向p的右子女，用p的左子女代替p結點。181057.8 刪除結點73的過程p為被刪除的結點45992741513225r為p的左子樹中關鍵碼最大的的結點第二種方法： （a）按對稱序周游p的左子樹，找到關鍵碼最大的 結點r，刪除r（用r的左子女代替r）； （b）用r結點代替被刪除結點p。LRr*pLRrL r *p RL r R 刪除r（用r的左子女代替r），用r結點代替被刪除結點p 。4518731059927415132257.8 刪除結點73的過程p為被刪除的結點r為p的左子樹中關鍵碼最大的的結點 刪除r（用r的左子女代替r），用r結點代替被刪除結點p 。45185110599274132257.8 刪除結點73的過程p為被刪除的結點r為p的左子樹中關鍵碼最大的的結點 查找被刪除結點*p； if(*p無左子女) 用*p的右子女代替*p； else 找*p的左子樹中最右下結點*r； 用*r的右指針指向*p的右子女； 用*p的左子女代替*p； 算法 7.4 從二叉排序樹上刪除一個結點算法算法7.4 7.4 二叉排序樹的刪除算法二叉排序樹的刪除算法int delete(PBinSearch ptree, KeyTypeint delete(PBinSearch ptree, KeyType key) key) PBinSearchNode parentp PBinSearchNode 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; / /* * 找到了關鍵碼為找到了關鍵碼為keykey的結點的結點 * */ / parentp parentp=p;=p; if(p-keykey)p=p-llink if(p-keykey)p=p-llink; ; / /* *進入左子樹進入左子樹 * */ / else p=p-rlink else p=p-rlink; ; / /* *進入右子樹進入右子樹 * */ / if(p if(p=NULL) return 0;=NULL) return 0; / /* * 二叉排序樹中無關鍵碼為二叉排序樹中無關鍵碼為keykey的結點的結點 * */ /if(p-llinkif(p-llink=NULL) =NULL) / /* *結點結點* *p p無左子樹無左子樹* */ / if(parentp=NULL) if(parentp=NULL) * *ptree=p-rlinkptree=p-rlink; ; / /* *被刪除的結點是原二叉排序樹的根結點被刪除的結點是原二叉排序樹的根結點* */ / else if(parentp-llink=p) parentp-llink=p-rlink else if(parentp-llink=p) parentp-llink=p-rlink; ; / /* * 將將* *p p的右子樹鏈到其父結點的左鏈上的右子樹鏈到其父結點的左鏈上 * */ / else parentp-rlink=p-rlink else parentp-rlink=p-rlink; ; / /* * 將將* *p p的右子樹鏈到其父結點的右鏈上的右子樹鏈到其父結點的右鏈上 * */ / else else / /* *結點結點* *p p有左子樹有左子樹* */ / r=p-llink r=p-llink; ; while(r-rlink!=NULL) r=r-rlink while(r-rlink!=NULL) r=r-rlink; ; / /* * 在在* *p p的左子樹中找最右下結點的左子樹中找最右下結點* *r r * */ / r-rlink=p-rlink r-rlink=p-rlink; ;/ /* * 用用* *r r的右指針指向的右指針指向* *p p的右子女的右子女 * */ / if(parentp=NULL) if(parentp=NULL) * *ptree=p-llinkptree=p-llink; ; 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; / /* * 釋放被刪除結點釋放被刪除結點 * */ / 性能分析 在二叉排序樹上查找關鍵字實際上是走了一條從根結點到某個結點的路徑的過程，比較的次數等于路徑長度加1。因此，比較的次數不超過樹的深度+1。但是具有n個結點的二叉樹可以有不同的形態(tài)，因此，對于不同形態(tài)的二叉排序樹，其平均查找長度也是不同的。最壞的情況下蛻變?yōu)閱沃?，此時的平均查找長度為（n+1)/2。 在隨機的情況下，平均性能為：P(n) = 2(1+1/n) ln n 由此可見，在隨機情況下的平均查找長度和ln n是等數量級的，然而在某些情況下，還需進行“平衡化”處理。 n個結點按不同的次序插入到二叉排序樹中，有n!棵二叉排序樹(其中有的形態(tài)相同) 。271005734151991825051018252741517399圖7.9 由同一組關鍵碼構成的兩棵形態(tài)不同的二叉排序樹7.4 7.4 最佳二叉排序樹最佳二叉排序樹* *平衡二叉樹定義 平衡二叉樹又稱AVL樹。它或者是一棵空樹，或者是具有下列性質的二叉樹：它的左右子樹均為平衡二叉樹，且左右子樹的深度之差的絕對值不超過1。 若定義二叉樹上結點的平衡因子BF(Balance Factor)為該結點的右子樹的高度減去左子樹的高度，在平衡二叉樹上所有結點平衡因子只可能為-1, 0, 1。只要二叉樹上有一個結點的平衡因子的絕對值大于1，則該二叉樹就是不平衡的。 對于平衡二叉樹來說，它的深度和logN是同數量級的，因此我們希望任何初始序列構成的二叉排序樹都是AVL樹。 -1-1-110001-1-200-1圖7.14 平衡和不平衡二叉樹示例最小不平衡子樹: 指離插入結點最近，且以平衡因子絕對值大于1的結點為根的子樹。27105118412500-1-112圖 6.13 最小不平衡子樹插入結點7.5.2 7.5.2 調整平衡的模式調整平衡的模式 設最小不平衡子樹的根為A，調整的規(guī)律可歸納為下列四種： 1. LL型調整； 2. RR型調整； 3. LR型調整； 4. RL型調整； 上面的幾種情況在經過平衡旋轉處理后，以*b或*c為根的新子樹為平衡二叉樹，而且它的深度和插入之前以*a為根的子樹相同。因此，當平衡的二叉排序樹因插入結點而失去平衡時，僅需對最小不平衡子樹進行旋轉處理即可。 A A B B B A h h h+1 h h h h h h -1 0 -2 1 0 0 LL型調整操作示意圖 (B)A()= ()B(A) 調整規(guī)則是將A的左子女B提升為新二叉樹的根；原來的根A連同其右子樹向右下旋轉成為B的右子樹；B的原右子樹作為A的左子樹。 27100-1BA27100-1BA05-2271000BA05051270-1BA100051800030-1-1-251270BA10005180030-10圖6.15 LL型調整操作示例 A A B B B A h h h+1 h h h h h h 1 0 0 0 2 1 RR型調整操作示意圖 ()A(B)= (A)B() 調整規(guī)則：將A的右子女B提升為新二叉樹的根；原來的根A連同其左子樹向左下旋轉成為B的左子樹；B的原左子樹作為A的右子樹。 275101BA275101BA732735100BA27051270 1BA1007341099730BA510274101000-1圖6.17 RR型調整操作示例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型調整操作示意圖 ()B(C)A()= (B)C(A) 調整規(guī)則設C為A的左子女的右子女，將A的孫子結點C提升為新二叉樹的根；原C的父結點B連同其左子樹向左下旋轉成為新根C的左子樹，原C的左子樹成為B的右子樹；原根A連同其右子樹向右下旋轉成為新根C的右子樹，原C的右子樹成為A的左子樹。 51270-1BA100051800C51270CA180101600500 1B圖6.19 LR型調整操作示例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型調整操作示意圖 ()A(C)B()= (A)C(B) 調整規(guī)則：設C為A的右子女的左子女，將A的孫子結點C提升為新二叉樹的根，原來C的父結點B連同其右子樹向右下旋轉成為新根C的右子樹，C的原右子樹成為B的左子樹；原來的根A連同其左子樹向左下旋轉成為新根C的左子樹，原來C的左子樹成為A的右子樹。 51270 1BA1007341073510CA410B273001000 1圖6.21 RL型調整操作示例000C51270 1BA1007341-103000-1 2C 設 在平衡二叉樹上插入一個關鍵碼為key的結點,二叉樹采用llink_rlink表示，結點中增加一個字段存儲結點的平衡因子。算法中包括以下幾個部分：6.5.2 6.5.2 插入元素的算法插入元素的算法（1）找最小不平衡子樹。找插入位置時，令*A離插入位置最近，且平衡因子不為0的結點，若這樣的結點不存在，則A指向根結點；若插入后使AVL樹失去平衡，則*A是最小不平衡子樹的根。（2）修改一些結點的平衡因子 路徑： *A， ，新結點。插入前，僅*A的平衡因子不為0。插入后，從*A的子女開始，順序掃描路徑上的結點*P,若新結點插入*P的左子樹中，則*P平衡因子變?yōu)?；否則變?yōu)?1。 (3)判別以*A為根的子樹是否失去了平衡。 若*A的平衡因子為0，則插入后不會； 若*A的平衡因子為1，且插入到*A的左子樹，則失去平衡，進一步，若插入到*A的左子女的左子樹，則采用LL型調整；若插入到*A的左子女的右子樹，則采用LR型調整; 若*A的平衡因子為-1, 且插入到*A的右子樹,則失去平衡，進一步,若插入到*A的右子女的右子樹,則采用RR型調整;若插入到*A的右子女的左子樹,則采用RL型調整;算法算法6.10 AVL樹的檢索和插入性能分析 含有n個結點的平衡二叉樹的高度是h= O(log2n)。插入關鍵碼為key的結點的時間耗費最大為樹的深度O(log2n)。算法在查找插入結點的同時也找到最小不平衡子樹。最小不平衡子樹中平衡因子的調整時間最大為最小不平衡子樹的深度。而四種子樹調整時間耗費為常數O( 1 ).因此， 整個算法的時間復雜度為 O(log2n). 最佳二叉排序樹的檢索效率是最好的，但是，當進行結點的插入或刪除操作后，保持其最佳性的時間代價太大。平衡二叉排序樹的檢索效率與最佳二叉排序樹的檢索效率是同級的，因此，動態(tài)字典常采用平衡二叉排序樹作為存儲結構。 B樹和B樹用于外存文件的索引。 6.6.1 B樹 6.6.2 B+樹一、B樹的定義 一棵m階的B樹，或為空樹，或是滿足下列特性的m叉樹： （1）樹中每個結點至多有m棵子樹； （2） 除根之外的所有分支結點至少有m/2棵子樹； （3）若根結點不是葉子結點，則至少有兩棵子樹； （4） 有j個子女的非葉結點中恰好有j-1個關鍵碼， 且 按遞增順 序排列，結點中包含的信息為 (p0, k1, p1, k2, , kj-1, pj)6.6 .1 B6.6 .1 B樹樹 其中ki(i=1,.,j-1)為關鍵碼，且ki ki+1(i=1,j-2); pi(i=0,j-1)為指向子樹根結點的指針，且pi-1所指子樹中所有結點的關鍵碼均小于ki(i=1,j-1), pj-1所指子樹中所有結點的關鍵碼均大于kj, j（ m/2 = j = m-1）為關鍵碼的個數。 （ 5）所有葉子結點都在同一層上，實際上這些 結點不存在。 當m=2時，m階B樹實際上就是二叉排序樹。所以m階B樹是二叉排序樹的推廣。其查找過程和二叉排序樹類似，它是一個沿指針查找結點和在結點的關鍵碼中進行順序查找交叉進行的過程。 實際應用中， m和內外存交換的單位有關，一般，m=1024 040008375045 112 236392 490 560 631 670110050212142135279240237388381378471435400396393553502492629626557660652633678673671圖6.22 一棵6階的B樹B樹主要用于文件的索引 。結點類型可以如下說明：#define m3typedef struct BTNode int keyNum; /* 關鍵字個數 */ struct BTNode *parent; /* 指向父結點*/ KeyType keym+1; /* 關鍵字向量 */ struct BTNode *ptrm+1; /* 子樹指針向量 */ Record *recPtrm+1; /* 指向文件中的記錄號 */ BTNode, *BTree;二. B樹的運算 1. B樹的檢索 key ki ki+1 pi 首先在根結點的關鍵碼集合中進行檢索，若key= = ki ，則檢索成功；否則， key一定在ki 和 ki+1 之間（存在某個i），沿pi繼續(xù)查找，重復上述過程，直到檢索成功，或pi為空，檢索失敗。性能分析 在B樹是進行查找包含兩種基本操作：（1）在B樹中找結點；（2）在結點中找關鍵字。由于B樹通常存儲在磁盤上，因此前一操作是在磁盤上進行的，而后一操作是在內存中進行的，即在磁盤上找到指針p所指結點后，先將結點中信息讀入內存，然后查詢。而在磁盤上進行操作比在內存中操作慢得多，因此在磁盤上進行查找的次數，即待查關鍵字所在結點在B樹是的層次數，是決定B樹查找效率的關鍵因素。 現在考慮最壞的情況：含n個關鍵字的m階B樹的最大深度為log m/2(n+1)/2 + 12. B樹的插入 深度為h的m階B樹，新結點一般插入到h層，首先檢索到第h層，確定插入結點位置。 （1）若被插入結點中關鍵碼個數小于m-1，則插入。 （2）若被插入結點中關鍵碼個數等于m-1，則引起 結點“分裂”。 可如下實現“分裂”： 假設*p結點中含有信息為：m,p0, (k1,p1), , (km, pm)將*p分裂為*p和*p兩個結點，分別含有信息為： *p ： m/21, p0, (k1,p1), (k m/21,pm/21) *p：(m- m/2, pm/2, (k m/2+1, p m/2+1), (km, pm)把關鍵字k m/2和指針*p一起插入到*p的雙親結點中。 375 400 045 112 236 375 400 560 631 670040 008110 050212 142135297 240237388 381378471 460435396 393553 502492629 626557圖6.23 一棵6階B樹的插入示例3. B樹的刪除 在深度為h的m階B樹中刪除一個關鍵碼，首先檢索到該關鍵碼所在的結點,然后根據不同情況進行刪除。（1)若結點在第h層，且關鍵碼數目大于m/2-1， 則只需從該結點中刪去該關鍵碼ki。（2）若結點在第h層，且關鍵碼數目等于m/2-1， 該結點左兄弟（或右兄弟）結點中的關鍵碼數目 大于m/21，則需調整被刪除關鍵碼的結點， 兄弟結點，以及父結點中的信息。方法：設父結 點 中的信息為：（p0, k1,p1,k2,p2,kxpx),由pi指向 被刪除關鍵碼的結點，其的信息為： （p 0, k 1,p 1,k 2,p 2,k y p y), 兄弟結點中的 信息為：（p 0, k 1 ,p 1 ,k 2 ,p 2 ,k z p z)。 則應將k(x+y)/2上移到父結點中，并將左（或右） 兄第中大于（或小于） k(x+y)/2及父結點中的ki移 到被刪除關鍵碼的結點中。 (3) 若結點在h層，且關鍵碼數目及其相鄰的兄弟結 點中的關鍵碼數目均等于m/21，則需合并結 點。假設該結點有右兄弟，且其右兄弟結點由雙 親結點中的指針pi所指，則在刪去關鍵碼之后， 它所在結點中剩余的關鍵碼和指針，加上雙親結 點中的關鍵碼ki一起，合并到pi所指兄弟結點中 （若沒有右兄弟結點，則合并到左兄弟結點中）。(4) 若結點的層數小于h，設刪除結點中第i個關鍵碼 ki ，則用pi所指的子樹中的最小關鍵碼k與ki互換，然后再刪除關鍵碼ki 。 50 63 20 35 23 30 66 90 56 42 3 7 3035 （a) 一棵三階B樹 圖6.24 (b) 從（a)中刪除關鍵碼66 （c) 從(b)中刪除關鍵碼42 50 63 20 3023 90 56 35 3 7 （d) 從 ( c ) 中刪除關鍵碼35圖6.24 (e) 從（d)中刪除關鍵碼56 23 30 56 20 50 3 7 23 30 63 90 50 63 20 3023 90 56 35 3 7 （d) 從 ( c ) 中刪除關鍵碼35圖6.24 (e) 從（d)中刪除關鍵碼56 23 30 56三. B樹在索引文件中的應用 (B, ) (E, ) (C, ) (D, ) (F, ) (G, ) (A, ) 圖6.25 用B樹組織索引順序文件B+樹是B樹的變形。一. B+樹的定義： 一棵m階的B樹，或為空樹，或是滿足下列條件的m叉樹： （1）樹中每個結點至多有m棵子樹； （2） 除根之外的所有分支結點至少有m/2棵子樹； （3）若根結點不是葉子結點，則至少有兩棵子樹； （4） 有n棵子樹的結點有n個關鍵碼； （5）葉結點中存放數據文件中記錄的關鍵碼及指向該記錄的指針（或存放數據文件分塊后每塊的最大關鍵碼及指向該塊的指針。葉結點按關鍵碼值大小順 序 鏈接。可以把每個葉結點看成一個基本索引塊。 6.6 .2 B+6.6 .2 B+樹樹 (6) 所有分支結點可看成是索引的索引，使結點中僅包含它的各子結點中最大（或最?。╆P鍵碼及指向子結點的指針。一棵m階的B樹和B樹的差異在于： （A）有n棵子樹的結點中含有n個關鍵碼； （B）所有的葉子結點中包含了全部關鍵碼的信息，及指向含這些關鍵碼記錄的指針，且葉子結點的本身依關鍵碼的大小從小到大順序鏈接。 （C）所有的非終端結點可以看成是索引部分，結點中僅含有其子樹（根結點）中最大（或最?。╆P鍵碼。 通常在B樹上有兩個頭指針，一個指向根結點，另一個指向關鍵碼最小的葉子結點。 60 99 85 99 20 39 60 27 36 39 92 99 65 79 85 46 51 60 10 20圖6.26 一棵三階的B+樹 二. B+樹的運算 1. B+樹的檢索 (1) 和B樹的檢索方式相似。從根結點開始進行隨 機檢索， key一定在ki 和 ki+1 之間（存在個i）， 沿pi繼續(xù)查找，重復上述過程，直到檢索到葉 結點，若key = = ki ，則檢索成功；否則檢索 失敗。 （2） 從最小關鍵碼開始沿葉結點鏈順序檢索。 2 . B+樹的插入 和B樹的插入相似，但總是在葉結點上進行，當 結點中原關鍵碼個數等于m時，該結點分裂。 (3) B+樹的刪除 僅在葉結點中進行刪除操作，在和兄第結點合并 時，父結點中作為分界的關鍵碼不放入合并后的結 點中。三. B+樹在索引順序文件中的應用 主文件的每個頁塊作B+樹的一個外部結點，并且 這些頁塊之間連成單鏈。 B+樹的樹葉層是主文件的 稀疏索引，整個B+樹構成多級索引。索引項就是B+ 樹中一個關鍵碼和它對應的指針所構成的二元組。 A D D E A B C 圖6.27 用B+樹組織索引順序文件1. 靜態(tài)字典（1）順序表示 A. 順序檢索：簡單，常用于未排序元素的檢索， 但檢索效率不高； B. 二分法檢索：僅用于排序元素，檢索效率較高當插入、刪除運算時會引起大量數據的移動。（2）散列表示：檢索操作達到近乎隨機存取的速度 。但散列表示經常出現碰撞與堆積現象，增加 了檢索長度。（3）二叉樹表示二叉排序樹：元素插入次序不同，會構成不同的二叉排序樹。最佳二叉排序樹 的平均檢索長度為O(log2n) 。2. 動態(tài)字典 平衡二叉排序樹表示：維持較高的檢索效率。3. 對于較大的必須存放在外存貯器上的字典，應 采用B樹或B+樹表示。B+樹是B樹的變種。B樹 和B+樹都能動態(tài)地調整，保持均衡，而使動態(tài) 字典保持較高的檢索效率。小小 結結 字典是一種特殊的集合，其最主要的操作為字典中元素的檢索。本章介紹了字典的各種存儲表示及相應的檢索方法，它們是字典的各種線性表示（例如：順序表表示，鏈表表示和目錄表表示等）、各種散列表示（例如：開地址法、拉鏈法和桶散列等）、各種二叉樹表示（例如：一般的二叉排序樹、最佳二叉排序樹和平衡的二叉排序樹等）以及各種多叉樹表示（例如B樹和B+樹）。其中順序表示的線性表、開地址法處理碰撞的散列表和最佳二叉排序樹主要使用于靜態(tài)或基本靜態(tài)的字典；鏈表表示的線性表、拉鏈法處理碰撞的散列表、桶散列結構、平衡的二叉排序樹、B樹和B+樹等較多地考慮到元素的動態(tài)處理，適合于組織各種動態(tài)的字典；其中B樹、B+樹和桶散列結構主要使用于外存的大型字典表示。 l作業(yè)：p.243 復習題 1、7、8 p.244 算法題 1l網絡課堂測試：6 字典與高級字典l上機：實驗5.4