第10章查找

1、第第1010章章 查找查找10.1 10.1 查找的基本概念查找的基本概念本章小結(jié)本章小結(jié)10.2 10.2 線性表的查找線性表的查找10.3 10.3 樹表的查找樹表的查找10.4 10.4 哈希表查找哈希表查找10.1 10.1 查找的基本概念查找的基本概念 被查找的對象是由一組記錄組成的表或文件被查找的對象是由一組記錄組成的表或文件, ,而每而每個記錄則由若干個數(shù)據(jù)項組成個記錄則由若干個數(shù)據(jù)項組成, ,并假設(shè)每個記錄都有并假設(shè)每個記錄都有一個能惟一標識該記錄的關(guān)鍵字。一個能惟一標識該記錄的關(guān)鍵字。 在這種條件下在這種條件下, ,查找的定義是：給定一個值查找的定義是：給定一個值k,k,在含

2、在含有有n n個記錄的表中找出關(guān)鍵字等于個記錄的表中找出關(guān)鍵字等于k k的記錄。若找到的記錄。若找到, ,則查找成功則查找成功, ,返回該記錄的信息或該記錄在表中的位返回該記錄的信息或該記錄在表中的位置；否則查找失敗置；否則查找失敗, ,返回相關(guān)的指示信息。返回相關(guān)的指示信息。 采用何種查找方法采用何種查找方法? (1) 使用哪種數(shù)據(jù)結(jié)構(gòu)來表示使用哪種數(shù)據(jù)結(jié)構(gòu)來表示“表表”,即表中記即表中記錄是按何種方式組織的。錄是按何種方式組織的。 (2) 表中關(guān)鍵字的次序。是對無序集合查找還表中關(guān)鍵字的次序。是對無序集合查找還是對有序集合查找是對有序集合查找? 若在查找的同時對表做修改運算若在查找的同時對

3、表做修改運算(如插入和如插入和刪除刪除),則相應(yīng)的表稱之為則相應(yīng)的表稱之為動態(tài)查找表動態(tài)查找表,否則稱之為否則稱之為靜態(tài)查找表靜態(tài)查找表。 由于查找運算的主要運算是關(guān)鍵字的比較由于查找運算的主要運算是關(guān)鍵字的比較,所以通所以通常把查找過程中對關(guān)鍵字需要執(zhí)行的平均比較次數(shù)常把查找過程中對關(guān)鍵字需要執(zhí)行的平均比較次數(shù)(也也稱為平均查找長度稱為平均查找長度)作為衡量一個查找算法效率優(yōu)劣的作為衡量一個查找算法效率優(yōu)劣的標準。平均查找長度標準。平均查找長度ASL(Average Search Length)定義定義為：為： n1iiicpASL 其中其中,n是查找表中記錄的個數(shù)。是查找表中記錄的個數(shù)。p

4、i是查找第是查找第i個記個記錄的概率錄的概率,一般地一般地,均認為每個記錄的查找概率相等均認為每個記錄的查找概率相等,即即pi=1/n(1in),ci是找到第是找到第i個記錄所需進行的比較次數(shù)個記錄所需進行的比較次數(shù)。 10.2 10.2 線性表的查找線性表的查找 在表的組織方式中在表的組織方式中,線性表是最簡單的一種。三種線性表是最簡單的一種。三種在線性表上進行查找的方法：在線性表上進行查找的方法： (1) 順序查找順序查找 (2) 二分查找二分查找 (3) 分塊查找。分塊查找。 因為不考慮在查找的同時對表做修改因為不考慮在查找的同時對表做修改,故上述三種故上述三種查找操作都是在靜態(tài)查找表上

5、實現(xiàn)的。查找操作都是在靜態(tài)查找表上實現(xiàn)的。 查找與數(shù)據(jù)的存儲結(jié)構(gòu)有關(guān)查找與數(shù)據(jù)的存儲結(jié)構(gòu)有關(guān),線性表有順序和鏈式線性表有順序和鏈式兩種存儲結(jié)構(gòu)。本節(jié)只介紹以順序表作為存儲結(jié)構(gòu)時兩種存儲結(jié)構(gòu)。本節(jié)只介紹以順序表作為存儲結(jié)構(gòu)時實現(xiàn)的順序查找算法。定義被查找的順序表類型定義實現(xiàn)的順序查找算法。定義被查找的順序表類型定義如下：如下： #define MAXL typedef struct KeyType key; /*KeyType為關(guān)鍵字的數(shù)據(jù)類型為關(guān)鍵字的數(shù)據(jù)類型*/ InfoType data; /*其他數(shù)據(jù)其他數(shù)據(jù)*/ NodeType; typedef NodeType SeqListMAX

6、L; /*順序表類型順序表類型*/ 10.2.1 10.2.1 順序查找順序查找 順序查找是一種最簡單的查找方法。順序查找是一種最簡單的查找方法。 它的基本思路是：從表的一端開始它的基本思路是：從表的一端開始,順序掃描線性表順序掃描線性表,依次將掃描到的關(guān)鍵字和給定值依次將掃描到的關(guān)鍵字和給定值k相比較相比較,若當前掃描若當前掃描到的關(guān)鍵字與到的關(guān)鍵字與k相等相等,則查找成功；若掃描結(jié)束后則查找成功；若掃描結(jié)束后,仍未仍未找到關(guān)鍵字等于找到關(guān)鍵字等于k的記錄的記錄,則查找失敗。則查找失敗。 例如例如,在關(guān)鍵字序列為在關(guān)鍵字序列為3,9,1,5,8,10,6,7,2,4的線性的線性表查找關(guān)鍵字為

7、表查找關(guān)鍵字為6的元素。的元素。 順序查找過程如下：順序查找過程如下： 開始開始: 3 9 1 5 8 10 6 7 2 4 第第1次比較次比較: 3 9 1 5 8 10 6 7 2 4 i=0 第第2次比較次比較: 3 9 1 5 8 10 6 7 2 4 i=1 第第3次比較次比較: 3 9 1 5 8 10 6 7 2 4 i=2 第第4次比較次比較: 3 9 1 5 8 10 6 7 2 4 i=3 第第5次比較次比較: 3 9 1 5 8 10 6 7 2 4 i=4 第第6次比較次比較: 3 9 1 5 8 10 6 7 2 4 i=5 第第7次比較次比較: 3 9 1 5 8

8、10 6 7 2 4 i=6 查找成功查找成功,返回序號返回序號6 順序查找的算法如下順序查找的算法如下( (在順序表在順序表R0.n-1R0.n-1中查找關(guān)中查找關(guān)鍵字為鍵字為k k的記錄的記錄, ,成功時返回找到的記錄位置成功時返回找到的記錄位置, ,失敗時返失敗時返回回-1)-1)： int SeqSearch(SeqList R,int n,KeyType k) int i=0; while (i=n) return -1; else return i; 從順序查找過程可以看到從順序查找過程可以看到(不考慮越界比較不考慮越界比較in),ci取決于所查記錄在表中的位置。如查找表中取決于所

9、查記錄在表中的位置。如查找表中第第1個記錄個記錄R0時時,僅需比較一次；而查找表中最后僅需比較一次；而查找表中最后一個記錄一個記錄Rn-1時時,需比較需比較n次次,即即ci=i。因此。因此,成功時成功時的順序查找的平均查找長度為：的順序查找的平均查找長度為： 21n2)1n(nn1in1icipsqASLn1in1i 查找成功時的平均比較次數(shù)約為表長的一半查找成功時的平均比較次數(shù)約為表長的一半 。10.2.2 10.2.2 二分查找二分查找 二分查找也稱為折半查找要求線性表中的結(jié)點必二分查找也稱為折半查找要求線性表中的結(jié)點必須己按關(guān)鍵字值的遞增或遞減順序排列。它首先用要須己按關(guān)鍵字值的遞增或遞

10、減順序排列。它首先用要查找的關(guān)鍵字查找的關(guān)鍵字k k與中間位置的結(jié)點的關(guān)鍵字相比較與中間位置的結(jié)點的關(guān)鍵字相比較, ,這這個中間結(jié)點把線性表分成了兩個子表個中間結(jié)點把線性表分成了兩個子表, ,若比較結(jié)果相若比較結(jié)果相等則查找完成等則查找完成; ;若不相等若不相等, ,再根據(jù)再根據(jù)k k與該中間結(jié)點關(guān)鍵與該中間結(jié)點關(guān)鍵字的比較大小確定下一步查找哪個子表字的比較大小確定下一步查找哪個子表, ,這樣遞歸進這樣遞歸進行下去行下去, ,直到找到滿足條件的結(jié)點或者該線性表中沒直到找到滿足條件的結(jié)點或者該線性表中沒有這樣的結(jié)點。有這樣的結(jié)點。 例如例如,在關(guān)鍵字有序序列在關(guān)鍵字有序序列2,4,7,9,10,

11、14,18,26,32,40中采用二分查找法查找關(guān)鍵字為中采用二分查找法查找關(guān)鍵字為7的元素。的元素。二分查找過程如下：二分查找過程如下： 開始開始: 2 4 7 9 10 14 18 26 32 40 low=0 high=9 mid=(0+9)/2=4 第第1次比較次比較: 2 4 7 9 10 14 18 26 32 40 low=0 high=3 mid=(0+3)/2=1 第第2次比較次比較: 2 4 7 9 10 14 18 26 32 40 low=2 high=3 mid=(2+3)/2=2 第第3次比較次比較: 2 4 7 9 10 14 18 26 32 40 R2.key

12、=7 查找成功查找成功,返回序號返回序號2 其算法如下其算法如下(在有序表在有序表R0.n-1中進行二分查找中進行二分查找,成功成功時返回記錄的位置時返回記錄的位置,失敗時返回失敗時返回-1)： int BinSearch(SeqList R,int n,KeyType k) int low=0,high=n-1,mid; while (lowk) /*繼續(xù)在繼續(xù)在Rlow.mid-1中查找中查找*/ high=mid-1; else low=mid+1; /*繼續(xù)在繼續(xù)在Rmid+1.high中查找中查找*/ return -1; 二分查找過程可用二叉樹來描述二分查找過程可用二叉樹來描述,我

13、們把當前我們把當前查找區(qū)間的中間位置上的記錄作為根查找區(qū)間的中間位置上的記錄作為根,左子表和右左子表和右子表中的記錄分別作為根的左子樹和右子樹子表中的記錄分別作為根的左子樹和右子樹,由此由此得到的二叉樹得到的二叉樹,稱為描述二分查找的稱為描述二分查找的判定樹判定樹或或比較比較樹樹。 5 2 8 0 3 6 9 -1 1 23 4 56 7 89 10 01 12 34 45 67 78 910 10 = = = = = = = = = = = R0.10的二分查線的判定樹的二分查線的判定樹(n=11) 例例10.1對于給定對于給定11個數(shù)據(jù)元素的有序表個數(shù)據(jù)元素的有序表2,3,10,15,20

14、,25,28,29,30,35,40,采用二分查找采用二分查找,試試問：問： (1)若查找給定值為若查找給定值為20的元素的元素,將依次與表中哪將依次與表中哪些元素比較？些元素比較？ (2)若查找給定值為若查找給定值為26的元素的元素,將依次與哪些元將依次與哪些元素比較？素比較？ (3)假設(shè)查找表中每個元素的概率相同假設(shè)查找表中每個元素的概率相同,求查找求查找成功時的平均查找長度和查找不成功時的平均查成功時的平均查找長度和查找不成功時的平均查找長度。找長度。 25 10 30 2 15 28 35 3 20 29 40 二分查二分查找判定找判定樹樹 (2)若查找給定值為若查找給定值為26的元素

15、的元素,依次與依次與25,30,28元素比較元素比較,共比共比較較3次。次。 (3)在查找成功時在查找成功時,會找到圖中某個圓形結(jié)點會找到圖中某個圓形結(jié)點,則成功時的平則成功時的平均查找長度：均查找長度：31144342211ASLsucc (1)若查找給定若查找給定值為值為20的元素的元素,依次依次與表中與表中25,10,15,20元素比較元素比較,共比較共比較4次。次。 在查找不成功時在查找不成功時, ,會找到圖中某個方形結(jié)點會找到圖中某個方形結(jié)點, ,則不成功則不成功時的平均查找長度：時的平均查找長度： 67. 3124834ASLunsucc 10.2.3 10.2.3 分塊查找分塊查

16、找 分塊查找又稱索引順序查找分塊查找又稱索引順序查找,它是一種性能介于它是一種性能介于順序查找和二分查找之間的查找方法。順序查找和二分查找之間的查找方法。 它要求按如下的索引方式來存儲線性表：將表它要求按如下的索引方式來存儲線性表：將表R0.n-1均分為均分為b塊塊,前前b-1塊中記錄個數(shù)為塊中記錄個數(shù)為s= n/b ,最最后一塊即第后一塊即第b塊的記錄數(shù)小于等于塊的記錄數(shù)小于等于s；每一塊中的關(guān)；每一塊中的關(guān)鍵字不一定有序鍵字不一定有序,但前一塊中的最大關(guān)鍵字必須小于但前一塊中的最大關(guān)鍵字必須小于后一塊中的最小關(guān)鍵字后一塊中的最小關(guān)鍵字,即要求表是即要求表是“分塊有序分塊有序”的；的；抽取各

17、塊中的最大關(guān)鍵字及其起始位置構(gòu)成一個索抽取各塊中的最大關(guān)鍵字及其起始位置構(gòu)成一個索引表引表IDX0.b-1,即即IDXi(0ib-1)中存放著第中存放著第i塊的塊的最大關(guān)鍵字及該塊在表最大關(guān)鍵字及該塊在表R中的起始位置。由于表中的起始位置。由于表R是是分塊有序的分塊有序的,所以索引表是一個遞增有序表。所以索引表是一個遞增有序表。索引表的數(shù)據(jù)類型定義如下：索引表的數(shù)據(jù)類型定義如下：#define MAXI typedef struct KeyType key; /*KeyType為關(guān)鍵字的類型為關(guān)鍵字的類型*/ int link; /*指向?qū)?yīng)塊的起始下標指向?qū)?yīng)塊的起始下標*/ IdxType

18、;typedef IdxType IDXMAXI;/*索引表類型索引表類型*/ 例如例如,設(shè)有一個線性表設(shè)有一個線性表,其中包含其中包含25個記錄個記錄,其關(guān)鍵字序列其關(guān)鍵字序列為為8,14,6,9,10,22,34,18,19,31,40,38,54,66, 46,71,78,68,80,85,100, 94,88,96,87。假設(shè)將。假設(shè)將25個記錄分為個記錄分為5塊塊,每塊中有每塊中有5個記個記錄錄,該線性表的索引存儲結(jié)構(gòu)如下圖所示。該線性表的索引存儲結(jié)構(gòu)如下圖所示。 14 34 66 85 100 0 5 10 15 20 8 14 6 9 10 22 34 18 19 31 40 3

19、8 54 66 46 71 78 68 80 85 100 94 88 96 87 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 key link 采用二分查找索引表的分塊查找算法如下采用二分查找索引表的分塊查找算法如下(索索引表引表I的長度為的長度為m)：int IdxSearch(IDX I,int m,SeqList R,int n,KeyType k) int low=0,high=m-1,mid,i; int b=n/m; /*b為每塊的記錄個數(shù)為每塊的記錄個數(shù)*/ while (low=k) hig

20、h=mid-1; else low=mid+1; if (lowm) /*在塊中順序查找在塊中順序查找*/ i=Ilow.link; while (i=Ilow.link+b-1 & Ri.key!=k) i+; if (ikey=k) /*遞歸終結(jié)條件遞歸終結(jié)條件*/ return bt; if (kkey) return SearchBST(bt-lchild,k); /*在左子樹中遞歸查找在左子樹中遞歸查找*/ else return SearchBST(bt-rchild,k); /*在右子樹中遞歸查找在右子樹中遞歸查找*/ 2. 二叉排序樹的插入和生成二叉排序樹的插入和生成 在二叉排

21、序樹中插入一個新記錄在二叉排序樹中插入一個新記錄,要保證插入后要保證插入后仍滿足仍滿足BST性質(zhì)。其插入過程是：若二叉排序樹性質(zhì)。其插入過程是：若二叉排序樹T為為空空,則創(chuàng)建一個則創(chuàng)建一個key域為域為k的結(jié)點的結(jié)點,將它作為根結(jié)點；否將它作為根結(jié)點；否則將則將k和根結(jié)點的關(guān)鍵字比較和根結(jié)點的關(guān)鍵字比較,若二者相等若二者相等,則說明樹則說明樹中已有此關(guān)鍵字中已有此關(guān)鍵字k,無須插入無須插入,直接返回直接返回0；若；若kkey,則將則將k插入根結(jié)點的左子樹中插入根結(jié)點的左子樹中,否則將它插入右子樹中。否則將它插入右子樹中。對應(yīng)的遞歸算法對應(yīng)的遞歸算法InsertBST()如下：如下：int In

22、sertBST(BSTNode *&p,KeyType k)/*在以在以*p為根結(jié)點的為根結(jié)點的BST中插入一個關(guān)鍵字為中插入一個關(guān)鍵字為k的結(jié)點。插入的結(jié)點。插入成功返回成功返回1,否則返回否則返回0*/ if (p=NULL) /*原樹為空原樹為空, 新插入的記錄為根結(jié)點新插入的記錄為根結(jié)點*/ p=(BSTNode *)malloc(sizeof(BSTNode); p-key=k;p-lchild=p-rchild=NULL; return 1; else if (k=p-key) /*存在相同關(guān)鍵字的結(jié)點存在相同關(guān)鍵字的結(jié)點,返回返回0*/ return 0; else if (kk

23、ey) return InsertBST(p-lchild,k);/*插入到左子樹中插入到左子樹中*/ else return InsertBST(p-rchild,k); /*插入到右子樹中插入到右子樹中*/ 二叉排序樹的生成二叉排序樹的生成,是從一個空樹開始是從一個空樹開始,每插入一每插入一個關(guān)鍵字個關(guān)鍵字,就調(diào)用一次插入算法將它插入到當前已生就調(diào)用一次插入算法將它插入到當前已生成的二叉排序樹中。從關(guān)鍵字數(shù)組成的二叉排序樹中。從關(guān)鍵字數(shù)組A0.n-1生成二生成二叉排序樹的算法叉排序樹的算法CreatBST()如下：如下： BSTNode *CreatBST(KeyType A,int n)

24、 /*返回樹根指針返回樹根指針*/ BSTNode *bt=NULL; /*初始時初始時bt為空樹為空樹*/ int i=0; while (irchild!=NULL) Delete1(p,r-rchild);/*遞歸找最右下結(jié)點遞歸找最右下結(jié)點*/else /*找到了最右下結(jié)點找到了最右下結(jié)點*r*/ p-key=r-key; /*將將*r的關(guān)鍵字值賦給的關(guān)鍵字值賦給*p*/ q=r; r=r-lchild; /*將左子樹的根結(jié)點放在被刪結(jié)點的位置上將左子樹的根結(jié)點放在被刪結(jié)點的位置上*/ free(q); /*釋放原釋放原*r的空間的空間*/ void Delete(BSTNode *&

25、p) /*從二叉排序樹中刪除從二叉排序樹中刪除*p結(jié)點結(jié)點*/ BSTNode *q; if (p-rchild=NULL) /*p結(jié)點沒有右子樹的情況結(jié)點沒有右子樹的情況*/ q=p; p=p-lchild; /*其右子樹的根結(jié)點放在被刪結(jié)點的位置上其右子樹的根結(jié)點放在被刪結(jié)點的位置上*/ free(q); else if (p-lchild=NULL) /*p結(jié)點沒有左子樹結(jié)點沒有左子樹*/ q=p; p=p-rchild; /*將將*p結(jié)點的右子樹作為雙親結(jié)點的相應(yīng)子樹結(jié)點的右子樹作為雙親結(jié)點的相應(yīng)子樹/ free(q); else Delete1(p,p-lchild); /*p結(jié)點既

26、沒有左子樹又沒有右子樹的情況結(jié)點既沒有左子樹又沒有右子樹的情況*/int DeleteBST(BSTNode *&bt,KeyType k)/*在在bt中刪除關(guān)鍵字為中刪除關(guān)鍵字為k的結(jié)點的結(jié)點*/ if (bt=NULL) return 0;/*空樹刪除失敗空樹刪除失敗*/ else if (kkey) return DeleteBST(bt-lchild,k); /*遞歸在左子樹中刪除為遞歸在左子樹中刪除為k的結(jié)點的結(jié)點*/else if (kbt-key) return DeleteBST(bt-rchild,k); /*遞歸在右子樹中刪除為遞歸在右子樹中刪除為k的結(jié)點的結(jié)點*/else

27、 Delete(bt); /*調(diào)用調(diào)用Delete(bt)函數(shù)刪除函數(shù)刪除*bt結(jié)點結(jié)點*/ return 1; 10.3.2 10.3.2 平衡二叉樹平衡二叉樹(AVL)(AVL) 若一棵二叉樹中每個結(jié)點的左、右子樹的高度若一棵二叉樹中每個結(jié)點的左、右子樹的高度至多相差至多相差1,則稱此二叉樹為平衡二叉樹。在算法中則稱此二叉樹為平衡二叉樹。在算法中,通過平衡因子通過平衡因子(balancd factor,用用bf表示表示)來具體實現(xiàn)上來具體實現(xiàn)上述平衡二叉樹的定義。平衡因子的定義是：平衡二述平衡二叉樹的定義。平衡因子的定義是：平衡二叉樹中每個結(jié)點有一個平衡因子域叉樹中每個結(jié)點有一個平衡因子域

28、,每個結(jié)點的平衡每個結(jié)點的平衡因子是該結(jié)點左子樹的高度減去右子樹的高度。從因子是該結(jié)點左子樹的高度減去右子樹的高度。從平衡因子的角度可以說平衡因子的角度可以說,若一棵二叉樹中所有結(jié)點的若一棵二叉樹中所有結(jié)點的平衡因子的絕對值小于或等于平衡因子的絕對值小于或等于1,即平衡因子取值為即平衡因子取值為1、0或或-1,則該二叉樹稱為平衡二叉樹。則該二叉樹稱為平衡二叉樹。 5 2 6 1 4 3 7 1 0 -1 0 1 0 -1 3 1 4 2 5 6 7 (b) (a) 0 -1 -2 -3 -2 -1 0 平衡二叉樹和不平衡二叉樹平衡二叉樹和不平衡二叉樹 定義定義AVL樹的結(jié)點的類型如下：樹的結(jié)點

29、的類型如下：typedef struct node /*記錄類型記錄類型*/KeyType key; /*關(guān)鍵字項關(guān)鍵字項*/ int bf;/*增加的平衡因子增加的平衡因子*/ InfoType data; /*其他數(shù)據(jù)域其他數(shù)據(jù)域*/ struct node *lchild,*rchild; /*左右孩子指針左右孩子指針*/ BSTNode; 假定向平衡二叉樹中插入一個新結(jié)點后破壞了平假定向平衡二叉樹中插入一個新結(jié)點后破壞了平衡二叉樹的平衡性衡二叉樹的平衡性,首先要找出插入新結(jié)點后失去平衡首先要找出插入新結(jié)點后失去平衡的最小子樹根結(jié)點的指針的最小子樹根結(jié)點的指針,然后再調(diào)整這個子樹中有關(guān)然

30、后再調(diào)整這個子樹中有關(guān)結(jié)點之間的鏈接關(guān)系結(jié)點之間的鏈接關(guān)系,使之成為新的平衡子樹。當失去使之成為新的平衡子樹。當失去平衡的最小子樹被調(diào)整為平衡子樹后平衡的最小子樹被調(diào)整為平衡子樹后,原有其他所有不原有其他所有不平衡子樹無需調(diào)整平衡子樹無需調(diào)整,整個二叉排序樹就又成為一棵平衡整個二叉排序樹就又成為一棵平衡二叉樹。二叉樹。 失去平衡的最小子樹是指以離插入結(jié)點最近失去平衡的最小子樹是指以離插入結(jié)點最近,且平且平衡因子絕對值大于衡因子絕對值大于1的結(jié)點作為根的子樹。假設(shè)用的結(jié)點作為根的子樹。假設(shè)用A表表示失去平衡的最小子樹的根結(jié)點示失去平衡的最小子樹的根結(jié)點,則調(diào)整該子樹的操作則調(diào)整該子樹的操作可歸納

31、為下列四種情況：可歸納為下列四種情況： (1) LL型調(diào)整型調(diào)整 (2) RR型調(diào)整型調(diào)整 (3) LR型調(diào)整型調(diào)整 (4) RL型調(diào)整型調(diào)整 例例10.3 輸入關(guān)鍵字序列輸入關(guān)鍵字序列16,3,7,11,9,26,18,14,15,給給出構(gòu)造一棵出構(gòu)造一棵AVL樹的步驟。樹的步驟。 16 0 (a)插入插入 16 16 1 (b)插入插入 3 3 0 16 2 (c)插入插入 7 3 -1 7 0 7 0 (d)LR 調(diào)整調(diào)整 3 0 16 0 7 -1 (e)插入插入 11 3 0 16 1 11 0 7 -2 (f)插入插入 9 3 0 16 2 11 1 9 0 7 -1 (g)LL

32、調(diào)整調(diào)整 3 0 11 0 9 0 16 0 7 -2 3 0 11 -1 9 0 16 -1 (h)插入插入 26 26 0 7 0 3 0 11 0 9 0 16 -1 26 0 (i)RR 調(diào)整調(diào)整 7 0 3 0 11 -1 9 0 16 -2 26 1 (j)插插入入 18 18 0 7 0 3 0 11 0 9 0 18 0 26 0 (k)RL 調(diào)調(diào)整整 16 0 7 0 3 0 11 -1 9 0 18 1 26 0 16 1 (l)插插入入 14 14 0 7 0 3 0 11 -2 9 0 18 2 26 0 16 2 (m)插插入入 15 14 -1 15 0 7 0 3

33、 0 11 -1 9 0 18 1 26 0 15 0 0 14 16 0 (n)LR 調(diào)調(diào)整整 在平衡二叉樹上進行查找的過程和在二叉排序樹上在平衡二叉樹上進行查找的過程和在二叉排序樹上進行查找的過程完全相同，因此，在平衡二叉樹上進進行查找的過程完全相同，因此，在平衡二叉樹上進行查找關(guān)鍵字的比較次數(shù)不會超過平衡二叉樹的深度。行查找關(guān)鍵字的比較次數(shù)不會超過平衡二叉樹的深度。 在最壞的情況下，普通二叉排序樹的查找長度為在最壞的情況下，普通二叉排序樹的查找長度為O(n)。那么，平衡二叉樹的情況又是怎樣的呢？下面。那么，平衡二叉樹的情況又是怎樣的呢？下面分析平衡二叉樹的高度分析平衡二叉樹的高度h和結(jié)點

34、個數(shù)和結(jié)點個數(shù)n之間的關(guān)系。之間的關(guān)系。 首先，構(gòu)造一系列的平衡二叉樹首先，構(gòu)造一系列的平衡二叉樹T1，T2，T3，其中，其中，Th（h=1，2，3，）是高度為）是高度為h且且結(jié)點數(shù)盡可能少的平衡二叉樹，如圖結(jié)點數(shù)盡可能少的平衡二叉樹，如圖10.12中所示的中所示的T1，T2，T3和和T4。為了構(gòu)造。為了構(gòu)造Th，先分別構(gòu)造，先分別構(gòu)造Th-1和和Th-2，使，使Th以以Th-1和和Th-2作為其根結(jié)點的左、右子樹。對作為其根結(jié)點的左、右子樹。對于每一個于每一個Th，只要從中刪去一個結(jié)點，就會失去平，只要從中刪去一個結(jié)點，就會失去平衡或高度不再是衡或高度不再是h（顯然，這樣構(gòu)造的平衡二叉樹在（

35、顯然，這樣構(gòu)造的平衡二叉樹在結(jié)點個數(shù)相同的平衡二叉樹中具有最大高度）。結(jié)點個數(shù)相同的平衡二叉樹中具有最大高度）。 T1 T2 T3 T4 Th Th-1 Th-2 圖圖10.12 結(jié)點個數(shù)結(jié)點個數(shù)n最少的平衡二叉樹最少的平衡二叉樹 然后，通過計算上述平衡二叉樹中的結(jié)點個數(shù)，來建立高度然后，通過計算上述平衡二叉樹中的結(jié)點個數(shù)，來建立高度與結(jié)點個數(shù)之間的關(guān)系。設(shè)與結(jié)點個數(shù)之間的關(guān)系。設(shè)N(h)為為Th的結(jié)點數(shù)，從圖的結(jié)點數(shù)，從圖10.12中中可以看出有下列關(guān)系成立：可以看出有下列關(guān)系成立： N(1)=1，N(2)=2，N(h)=N(h-1)+N(h-2)+1當當h1時，此關(guān)系類似于定義時，此關(guān)系類

36、似于定義Fibonacci數(shù)的關(guān)系：數(shù)的關(guān)系： F(1)=1，F(xiàn)(2)=1，F(xiàn)(h)=F(h-1)+F(h-2)通過檢查兩個序列的前幾項就可發(fā)現(xiàn)兩者之間的對應(yīng)關(guān)系：通過檢查兩個序列的前幾項就可發(fā)現(xiàn)兩者之間的對應(yīng)關(guān)系： N(h)=F(h+2)-1由于由于Fibonacci數(shù)滿足漸近公式：數(shù)滿足漸近公式：F(h)=其中，其中，故由此可得近似公式：故由此可得近似公式：N(h)=即：即：hlog2(N(h)+1)所以，含有所以，含有n個結(jié)點的平衡二叉樹的平均查找長度為個結(jié)點的平衡二叉樹的平均查找長度為O(log2n)。 h51251 121512 hh10.3.3 B-樹樹 B-樹又稱為多路平衡查找樹

37、樹又稱為多路平衡查找樹,是一種組織和維護外是一種組織和維護外存文件系統(tǒng)非常有效的數(shù)據(jù)結(jié)構(gòu)。存文件系統(tǒng)非常有效的數(shù)據(jù)結(jié)構(gòu)。 B-樹中所有結(jié)點的孩子結(jié)點最大值稱為樹中所有結(jié)點的孩子結(jié)點最大值稱為B-樹的階樹的階,通常用通常用m表示表示,從查找效率考慮從查找效率考慮,要求要求m3。一棵。一棵m階階B-樹或者是一棵空樹樹或者是一棵空樹,或者是滿足下列要求的或者是滿足下列要求的m叉樹：叉樹： (1) 樹中每個結(jié)點至多有樹中每個結(jié)點至多有m個孩子結(jié)點個孩子結(jié)點(即至多有即至多有m-1個關(guān)鍵字個關(guān)鍵字)； (2) 除根結(jié)點外除根結(jié)點外,其他結(jié)點至少有其他結(jié)點至少有 m/2 個孩子結(jié)點個孩子結(jié)點(即至少有即至

38、少有 m/2 -1= (m-1)/2 個關(guān)鍵字個關(guān)鍵字)； (3) 若根結(jié)點不是葉子結(jié)點若根結(jié)點不是葉子結(jié)點,則根結(jié)點至少有兩個孩則根結(jié)點至少有兩個孩子結(jié)點子結(jié)點； (4) 每個結(jié)點的結(jié)構(gòu)為：每個結(jié)點的結(jié)構(gòu)為：np0k1p1k2p2knpn 其中其中,n為該結(jié)點中的關(guān)鍵字個數(shù)為該結(jié)點中的關(guān)鍵字個數(shù),除根結(jié)點外除根結(jié)點外,其其他所有結(jié)點的他所有結(jié)點的n大于等于大于等于 m/2 -1,且小于等于且小于等于m-1；ki(1in)為該結(jié)點的關(guān)鍵字且滿足為該結(jié)點的關(guān)鍵字且滿足kiki+1；pi(0in)為該結(jié)點的孩子結(jié)點指針且滿足為該結(jié)點的孩子結(jié)點指針且滿足pi(0in-1)結(jié)點上的關(guān)鍵字大于等于結(jié)點上

39、的關(guān)鍵字大于等于ki且小于且小于ki+1,pn結(jié)點上結(jié)點上的關(guān)鍵字大于的關(guān)鍵字大于kn。 (5) 所有葉子結(jié)點都在同一層上所有葉子結(jié)點都在同一層上,即即B-樹是所有結(jié)樹是所有結(jié)點的平衡因子均等于點的平衡因子均等于0的多路查找樹。的多路查找樹。 3 12 15 22 2 2 7 2 35 41 3 53 54 63 4 68 69 71 76 3 79 84 93 2 11 30 2 66 78 1 51 一棵一棵5階階B-樹樹在在B-樹的存儲結(jié)構(gòu)中樹的存儲結(jié)構(gòu)中,各結(jié)點的類型定義如下：各結(jié)點的類型定義如下：#define MAXM 10/*定義定義B-樹的最大的階數(shù)樹的最大的階數(shù)*/typed

40、ef int KeyType; /*KeyType為關(guān)鍵字類型為關(guān)鍵字類型*/typedef struct node /*B-樹結(jié)點類型定義樹結(jié)點類型定義*/ int keynum; /*結(jié)點當前擁有的關(guān)鍵字的個數(shù)結(jié)點當前擁有的關(guān)鍵字的個數(shù)*/ KeyType keyMAXM; /*1.keynum存放關(guān)鍵字存放關(guān)鍵字,0不用不用*/ struct node *parent; /*雙親結(jié)點指針雙親結(jié)點指針*/ struct node *ptrMAXM;/*孩子結(jié)點指針數(shù)組孩子結(jié)點指針數(shù)組0.keynum*/ BTNode;(B-樹的查找樹的查找( 在在B-樹中查找給定關(guān)鍵字的方法類似于二叉排樹

41、中查找給定關(guān)鍵字的方法類似于二叉排序樹上的查找序樹上的查找,不同的是在每個記錄上確定向下查找不同的是在每個記錄上確定向下查找的路徑不一定是二路的路徑不一定是二路(即二叉即二叉)的的,而是而是n+1路的。因為路的。因為記錄內(nèi)的關(guān)鍵字序列是有序的數(shù)量記錄內(nèi)的關(guān)鍵字序列是有序的數(shù)量key1.n,故既可故既可以用順序查找以用順序查找,也可以用折半查找。在一棵也可以用折半查找。在一棵B-樹上順樹上順序查找關(guān)鍵字為序查找關(guān)鍵字為k的方法為：的方法為：將將k與根結(jié)點中的與根結(jié)點中的keyi進行比較：進行比較： (1) 若若k=keyi,則查找成功；則查找成功； (2) 若若kkey1,則沿著指針則沿著指針p

42、tr0所指的子樹所指的子樹繼續(xù)查找；繼續(xù)查找； (3) 若若keyikkeyi+1,則沿著指針則沿著指針ptri所所指的子樹繼續(xù)查找；指的子樹繼續(xù)查找； (4) 若若kkeyn,則沿著指針則沿著指針ptrn所指的子樹所指的子樹繼續(xù)查找。繼續(xù)查找。 2. B-樹的插入樹的插入將關(guān)鍵字將關(guān)鍵字k插入到插入到B-樹的過程分兩步完成：樹的過程分兩步完成： (1) 利用前述的利用前述的B-樹的查找算法找出該關(guān)鍵字的插入樹的查找算法找出該關(guān)鍵字的插入結(jié)點結(jié)點(注意注意B-樹的插入結(jié)點一定是葉子結(jié)點樹的插入結(jié)點一定是葉子結(jié)點)。 (2) 判斷該結(jié)點是否還有空位置判斷該結(jié)點是否還有空位置,即判斷該結(jié)點是否滿即

43、判斷該結(jié)點是否滿足足nm-1,若該結(jié)點滿足若該結(jié)點滿足nm-1,說明該結(jié)點還有空位置說明該結(jié)點還有空位置,直接把關(guān)鍵字直接把關(guān)鍵字k插入到該結(jié)點的合適位置上插入到該結(jié)點的合適位置上(即滿足插入即滿足插入后結(jié)點上的關(guān)鍵字仍保持有序后結(jié)點上的關(guān)鍵字仍保持有序)； 若該結(jié)點有若該結(jié)點有n=m-1,說明該結(jié)點已沒有空位置說明該結(jié)點已沒有空位置,需需要把結(jié)點分裂成兩個。要把結(jié)點分裂成兩個。 分裂的做法是分裂的做法是,取一新結(jié)點取一新結(jié)點,把原結(jié)點上的關(guān)鍵字把原結(jié)點上的關(guān)鍵字和和k按升序排序后按升序排序后,從中間位置從中間位置(即即 m/2 = (m+1)/2 之之處處)把關(guān)鍵字把關(guān)鍵字(不包括中間位置的

44、關(guān)鍵字不包括中間位置的關(guān)鍵字)分成兩部分分成兩部分,左部分所含關(guān)鍵字放在舊結(jié)點中左部分所含關(guān)鍵字放在舊結(jié)點中,右部分所含關(guān)鍵字右部分所含關(guān)鍵字放在新結(jié)點中放在新結(jié)點中,中間位置的關(guān)鍵字連同新結(jié)點的存儲中間位置的關(guān)鍵字連同新結(jié)點的存儲位置插入到父親結(jié)點中。如果父結(jié)點的關(guān)鍵字個數(shù)位置插入到父親結(jié)點中。如果父結(jié)點的關(guān)鍵字個數(shù)也超過也超過Max,則要再分裂則要再分裂,再往上插再往上插,直至這個過程傳直至這個過程傳到根結(jié)點為止。到根結(jié)點為止。例如例如 關(guān)鍵字序列為：關(guān)鍵字序列為：1,2,6,7,11,4,8,13,10,5,17,9,16,20,3,12,14,18,19,15。創(chuàng)建一棵創(chuàng)建一棵5階階B

45、-樹。樹。建立建立B-的過程如下圖所示。的過程如下圖所示。 1 2 6 7 6 1 2 7 11 6 1 2 4 7 8 11 13 6 10 1 2 4 11 13 7 8 6 10 1 2 4 5 11 13 16 7 8 9 6 10 16 1 2 4 5 7 8 9 3 6 10 16 1 2 7 8 9 17 18 19 20 4 5 10 14 15 13 16 3 6 1 2 7 8 9 (a)插入插入 1,2,6,7 (b)插入插入 11 (c)插入插入 4,8,13 (d)插入插入 10 (e)插入插入 5,17,9,16 (f)插入插入 20 (g)插入插入 3,12,14

46、,18,19 (h)插入插入 15 11 13 17 20 17 18 19 20 11 12 13 14 4 5 11 12 3. B-樹的刪除樹的刪除 B-樹的刪除過程與插入過程類似樹的刪除過程與插入過程類似,只是稍為復雜一些。只是稍為復雜一些。要使刪除后的結(jié)點中的關(guān)鍵字個數(shù)要使刪除后的結(jié)點中的關(guān)鍵字個數(shù) m/2 -1,將涉及到結(jié)將涉及到結(jié)點的點的“合并合并”問題。在問題。在B-樹上刪除關(guān)鍵字樹上刪除關(guān)鍵字k的過程分兩的過程分兩步完成：步完成： (1) 利用前述的利用前述的B-樹的查找算法找出該關(guān)鍵字所在的樹的查找算法找出該關(guān)鍵字所在的結(jié)點。結(jié)點。 (2) 在結(jié)點上刪除關(guān)鍵字在結(jié)點上刪除關(guān)

47、鍵字k分兩種情況：一種是在葉分兩種情況：一種是在葉子結(jié)點上刪除關(guān)鍵字；另一種是在非葉子結(jié)點上刪除關(guān)子結(jié)點上刪除關(guān)鍵字；另一種是在非葉子結(jié)點上刪除關(guān)鍵字。鍵字。 (3) 在非葉子結(jié)點上刪除關(guān)鍵字的過程：假設(shè)要刪在非葉子結(jié)點上刪除關(guān)鍵字的過程：假設(shè)要刪除關(guān)鍵字除關(guān)鍵字keyi(1in),在刪去該關(guān)鍵字后在刪去該關(guān)鍵字后,以該結(jié)點以該結(jié)點ptri所指子樹中的最小關(guān)鍵字所指子樹中的最小關(guān)鍵字keymin來代替被刪關(guān)來代替被刪關(guān)鍵字鍵字keyi所在的位置所在的位置(注意注意ptri所指子樹中的最小關(guān)所指子樹中的最小關(guān)鍵字鍵字keymin一定是在葉子結(jié)點上一定是在葉子結(jié)點上),然后再以指針然后再以指針pt

48、ri所指結(jié)點為根結(jié)點查找并刪除所指結(jié)點為根結(jié)點查找并刪除keymin(即再以即再以ptri所指結(jié)點為所指結(jié)點為B-樹的根結(jié)點樹的根結(jié)點,以以keymin為要刪除的關(guān)鍵為要刪除的關(guān)鍵字字,然后再次調(diào)用然后再次調(diào)用B-樹上的刪除算法樹上的刪除算法),這樣也就把在非這樣也就把在非葉子結(jié)點上刪除關(guān)鍵字葉子結(jié)點上刪除關(guān)鍵字k的問題轉(zhuǎn)化成了在葉子結(jié)點的問題轉(zhuǎn)化成了在葉子結(jié)點上刪除關(guān)鍵字上刪除關(guān)鍵字keymin的問題。的問題。 (4) 在在B-樹的葉子結(jié)點上刪除關(guān)鍵字共有以下三種情樹的葉子結(jié)點上刪除關(guān)鍵字共有以下三種情況：況： 假如被刪結(jié)點的關(guān)鍵字個數(shù)大于假如被刪結(jié)點的關(guān)鍵字個數(shù)大于Min,說明刪去該說明刪

49、去該關(guān)鍵字后該結(jié)點仍滿足關(guān)鍵字后該結(jié)點仍滿足B-樹的定義樹的定義,則可直接刪去該關(guān)則可直接刪去該關(guān)鍵字。鍵字。 假如被刪結(jié)點的關(guān)鍵字個數(shù)等于假如被刪結(jié)點的關(guān)鍵字個數(shù)等于Min,說明刪去關(guān)說明刪去關(guān)鍵字后該結(jié)點將不滿足鍵字后該結(jié)點將不滿足B-樹的定義樹的定義,此時若該結(jié)點的左此時若該結(jié)點的左(或右或右)兄弟結(jié)點中關(guān)鍵字個數(shù)大于兄弟結(jié)點中關(guān)鍵字個數(shù)大于Min,則把該結(jié)點的左則把該結(jié)點的左(或右或右)兄弟結(jié)點中最大兄弟結(jié)點中最大(或最小或最小)的關(guān)鍵字上移到雙親結(jié)的關(guān)鍵字上移到雙親結(jié)點中點中,同時把雙親結(jié)點中大于同時把雙親結(jié)點中大于(或小于或小于)上移關(guān)鍵字的關(guān)鍵上移關(guān)鍵字的關(guān)鍵字下移到要刪除關(guān)鍵字

50、的結(jié)點中字下移到要刪除關(guān)鍵字的結(jié)點中,這樣刪去關(guān)鍵字這樣刪去關(guān)鍵字k后該后該結(jié)點以及它的左結(jié)點以及它的左(或右或右)兄弟結(jié)點都仍舊滿足兄弟結(jié)點都仍舊滿足B-樹的定義。樹的定義。 假如被刪結(jié)點的關(guān)鍵字個數(shù)等于假如被刪結(jié)點的關(guān)鍵字個數(shù)等于Min,并且該并且該結(jié)點的左和右兄弟結(jié)點結(jié)點的左和右兄弟結(jié)點(如果存在的話如果存在的話)中關(guān)鍵字個中關(guān)鍵字個數(shù)均等于數(shù)均等于Min,這時這時,需把要刪除關(guān)鍵字的結(jié)點與其左需把要刪除關(guān)鍵字的結(jié)點與其左(或右或右)兄弟結(jié)點以及雙親結(jié)點中分割二者的關(guān)鍵字兄弟結(jié)點以及雙親結(jié)點中分割二者的關(guān)鍵字合并成一個結(jié)點。如果因此使雙親結(jié)點中關(guān)鍵字個合并成一個結(jié)點。如果因此使雙親結(jié)點中

51、關(guān)鍵字個數(shù)小于數(shù)小于Min,則對此雙親結(jié)點做同樣處理則對此雙親結(jié)點做同樣處理,以致于可能以致于可能直到對根結(jié)點做這樣的處理而使整個樹減少一層。直到對根結(jié)點做這樣的處理而使整個樹減少一層。 例如例如,對于上例生成的對于上例生成的B-樹樹,給出刪除給出刪除8,16,15,4等四個關(guān)等四個關(guān)鍵字的過程。鍵字的過程。 10 3 6 13 17 1 2 4 5 7 9 11 12 14 15 18 19 20 (a) 初始初始 5 階階 B- -樹樹 (b) 刪除刪除 8,16 后的結(jié)果后的結(jié)果 10 3 6 13 18 1 2 4 5 11 12 14 17 19 20 (c) 刪除刪除 15 后的結(jié)

52、果后的結(jié)果 6 10 13 18 1 2 3 5 7 9 14 17 19 20 (d) 刪除刪除 4 后的結(jié)果后的結(jié)果 7 9 11 12 10 14 15 13 16 3 6 1 2 7 8 9 17 18 19 20 4 5 11 12 10.3.4 B+10.3.4 B+樹樹 在索引文件組織中在索引文件組織中,經(jīng)常使用經(jīng)常使用B-樹的一些變形樹的一些變形,其中其中B+樹是一種應(yīng)用廣泛的變形。一棵樹是一種應(yīng)用廣泛的變形。一棵m階階B+樹滿足下列樹滿足下列條件：條件： (1) 每個分支結(jié)點至多有每個分支結(jié)點至多有m棵子樹?？米訕洹?(2) 除根結(jié)點外除根結(jié)點外,其他每個分支結(jié)點至少有其他每

53、個分支結(jié)點至少有 (m+1)/2 棵子樹?？米訕?。 (3) 根結(jié)點至少有兩棵子樹根結(jié)點至少有兩棵子樹,至多有至多有m棵子樹?？米訕?。 (4) 有有n棵子樹的結(jié)點有棵子樹的結(jié)點有n個關(guān)鍵字。個關(guān)鍵字。 (5) 所有葉子結(jié)點包含全部所有葉子結(jié)點包含全部(數(shù)據(jù)文件中記錄數(shù)據(jù)文件中記錄) 關(guān)關(guān)鍵字及指向相應(yīng)記錄的指針鍵字及指向相應(yīng)記錄的指針(或存放數(shù)據(jù)文件分塊或存放數(shù)據(jù)文件分塊后每塊的最大關(guān)鍵字及指向該塊的指針后每塊的最大關(guān)鍵字及指向該塊的指針),而且葉子而且葉子結(jié)點按關(guān)鍵字大小順序鏈接結(jié)點按關(guān)鍵字大小順序鏈接(可以把每個葉子結(jié)點可以把每個葉子結(jié)點看成是一個基本索引塊看成是一個基本索引塊,它的指針不再

54、指向另一級索它的指針不再指向另一級索引塊引塊,而是直接指向數(shù)據(jù)文件中的記錄而是直接指向數(shù)據(jù)文件中的記錄)。 (6) 所有分支結(jié)點所有分支結(jié)點(可看成是索引的索引可看成是索引的索引)中僅包中僅包含它的各個子結(jié)點含它的各個子結(jié)點(即下級索引的索引塊即下級索引的索引塊)中最大關(guān)中最大關(guān)鍵字及指向子結(jié)點的指針。鍵字及指向子結(jié)點的指針。 33 18 23 48 10 12 15 18 19 20 21 22 23 30 31 33 45 47 48 50 52 一棵一棵4階的階的B+樹樹 m階的階的B+樹和樹和m階的階的B-樹樹,定義中的前三點是相同定義中的前三點是相同的的,主要的差異是：主要的差異是：

55、 (1) 在在B+樹中樹中,具有具有n個關(guān)鍵字的結(jié)點含有個關(guān)鍵字的結(jié)點含有n棵子樹棵子樹,即即每個關(guān)鍵字對應(yīng)一棵子樹每個關(guān)鍵字對應(yīng)一棵子樹,而在而在B-樹中樹中,具有具有n個關(guān)鍵字個關(guān)鍵字的結(jié)點含有的結(jié)點含有(n+1)棵子樹?？米訕?。 (2) 在在B+樹中樹中,每個結(jié)點每個結(jié)點(除根結(jié)點外除根結(jié)點外)中的關(guān)鍵字個數(shù)中的關(guān)鍵字個數(shù)n的取值范圍是的取值范圍是 m/2 n m,根結(jié)點根結(jié)點n的取值范圍是的取值范圍是1nm；而在；而在B-樹中樹中,它們的取值范圍分別是它們的取值范圍分別是 m/2 -1n m-1和和1nm-1。 (3) B+樹中的所有葉子結(jié)點包含了全部關(guān)鍵字樹中的所有葉子結(jié)點包含了全部

56、關(guān)鍵字,即其即其他非葉子結(jié)點中的關(guān)鍵字包含在葉子結(jié)點中他非葉子結(jié)點中的關(guān)鍵字包含在葉子結(jié)點中,而在而在B-樹樹中中,葉子結(jié)點包含的關(guān)鍵字與其他結(jié)點包含的關(guān)鍵字是葉子結(jié)點包含的關(guān)鍵字與其他結(jié)點包含的關(guān)鍵字是不重復的。不重復的。 (4) B+樹中所有非葉子結(jié)點僅起到索引的作用樹中所有非葉子結(jié)點僅起到索引的作用,即即結(jié)點中的每個索引項只含有對應(yīng)子樹的最大關(guān)鍵字和結(jié)點中的每個索引項只含有對應(yīng)子樹的最大關(guān)鍵字和指向該子樹的指針指向該子樹的指針,不含有該關(guān)鍵字對應(yīng)記錄的存儲不含有該關(guān)鍵字對應(yīng)記錄的存儲地址。而在地址。而在B-樹中樹中,每個關(guān)鍵字對應(yīng)一個記錄的存儲每個關(guān)鍵字對應(yīng)一個記錄的存儲地址。地址。 (

57、5) 通常在通常在B+樹上有兩個頭指針樹上有兩個頭指針,一個指向根結(jié)點一個指向根結(jié)點,另一個指向關(guān)鍵字最小的葉子結(jié)點另一個指向關(guān)鍵字最小的葉子結(jié)點,所有葉子結(jié)點鏈所有葉子結(jié)點鏈接成一個不定長的線性鏈表。接成一個不定長的線性鏈表。10.4 10.4 哈希表查找哈希表查找10.4.1 10.4.1 哈希表的基本概念哈希表的基本概念 哈希表哈希表(Hash Table)又稱散列表又稱散列表,是除順序表存儲結(jié)是除順序表存儲結(jié)構(gòu)、鏈接表存儲結(jié)構(gòu)和索引表存儲結(jié)構(gòu)之外的又一種存構(gòu)、鏈接表存儲結(jié)構(gòu)和索引表存儲結(jié)構(gòu)之外的又一種存儲線性表的存儲結(jié)構(gòu)。哈希表存儲的基本思路是：設(shè)要儲線性表的存儲結(jié)構(gòu)。哈希表存儲的基本

58、思路是：設(shè)要存儲的對象個數(shù)為存儲的對象個數(shù)為n,設(shè)置一個長度為設(shè)置一個長度為m(mn)的連續(xù)內(nèi)的連續(xù)內(nèi)存單元存單元,以線性表中每個對象的關(guān)鍵字以線性表中每個對象的關(guān)鍵字ki(0in-1)為自變?yōu)樽宰兞苛?通過一個稱為哈希函數(shù)的函數(shù)通過一個稱為哈希函數(shù)的函數(shù)h(ki),把把ki映射為內(nèi)存映射為內(nèi)存單元的地址單元的地址(或稱下標或稱下標)h(ki),并把該對象存儲在這個內(nèi)存并把該對象存儲在這個內(nèi)存單元中。單元中。h(ki)也稱為哈希地址也稱為哈希地址(又稱散列地址又稱散列地址)。把如此。把如此構(gòu)造的線性表存儲結(jié)構(gòu)稱為構(gòu)造的線性表存儲結(jié)構(gòu)稱為哈希表。哈希表。 但是存在這樣的問題但是存在這樣的問題,對

59、于兩個關(guān)鍵字對于兩個關(guān)鍵字ki和和kj(ij),有有kikj(ij),但但h(ki)=h(kj)。我們把這種現(xiàn)象叫做。我們把這種現(xiàn)象叫做哈哈希沖突希沖突。 通常把這種具有不同關(guān)鍵字而具有相同哈希地通常把這種具有不同關(guān)鍵字而具有相同哈希地址的對象稱做址的對象稱做“同義詞同義詞”,由同義詞引起的沖突稱作由同義詞引起的沖突稱作同義詞沖突同義詞沖突。在哈希表存儲結(jié)構(gòu)的存儲中。在哈希表存儲結(jié)構(gòu)的存儲中,同義詞沖同義詞沖突是很難避免的突是很難避免的,除非關(guān)鍵字的變化區(qū)間小于等于哈除非關(guān)鍵字的變化區(qū)間小于等于哈希地址的變化區(qū)間希地址的變化區(qū)間,而這種情況當關(guān)鍵字取值不連續(xù)而這種情況當關(guān)鍵字取值不連續(xù)時是非常

60、浪費存儲空間的。通常的實際情況是關(guān)鍵時是非常浪費存儲空間的。通常的實際情況是關(guān)鍵字的取值區(qū)間遠大于哈希地址的變化區(qū)間。字的取值區(qū)間遠大于哈希地址的變化區(qū)間。歸納起來：歸納起來： (1)哈希函數(shù)是一個映象哈希函數(shù)是一個映象,即：將關(guān)鍵字的集合映即：將關(guān)鍵字的集合映射到某個地址集合上射到某個地址集合上,它的設(shè)置很靈活它的設(shè)置很靈活,只要這個地只要這個地址集合的址集合的 大小不超出允許范圍即可；大小不超出允許范圍即可； (2)由于哈希函數(shù)是一個壓縮映象由于哈希函數(shù)是一個壓縮映象,因此因此,在一般情在一般情況下況下,很容易產(chǎn)生很容易產(chǎn)生“沖突沖突”現(xiàn)象現(xiàn)象,即：即：key1 key2,而而 f(key