數(shù)據(jù)結構教程（第3版）四ppt課件

1、數(shù)據(jù)構造教程第數(shù)據(jù)構造教程第3版四版四第第1010章章 查找查找10.1 10.1 查找的根本概念查找的根本概念本章小結本章小結10.2 10.2 線性表的查找線性表的查找10.3 10.3 樹表的查找樹表的查找10.4 10.4 哈希表查找哈希表查找10.1 10.1 查找的根本概念查找的根本概念 被查找的對象是由一組記錄組成的表或文被查找的對象是由一組記錄組成的表或文件件, ,而每個記錄那么由假設干個數(shù)據(jù)項組成而每個記錄那么由假設干個數(shù)據(jù)項組成, ,并并假設每個記錄都有一個能獨一標識該記錄的關假設每個記錄都有一個能獨一標識該記錄的關鍵字。鍵字。 在這種條件下在這種條件下, ,查找的定義是：

2、給定一個值查找的定義是：給定一個值k,k,在含有在含有n n個記錄的表中找出關鍵字等于個記錄的表中找出關鍵字等于k k的記的記錄。假設找到錄。假設找到, ,那么查找勝利那么查找勝利, ,前往該記錄的信前往該記錄的信息或該記錄在表中的位置；否那么查找失敗息或該記錄在表中的位置；否那么查找失敗, ,前往相關的指示信息。前往相關的指示信息。 采用何種查找方法采用何種查找方法? (1) 運用哪種數(shù)據(jù)構造來表示運用哪種數(shù)據(jù)構造來表示“表表,即表中記錄即表中記錄是按何種方式組織的。是按何種方式組織的。 (2) 表中關鍵字的次序。是對無序集合查找還表中關鍵字的次序。是對無序集合查找還是對有序集合查找是對有序

3、集合查找? 假設在查找的同時對表做修正運算假設在查找的同時對表做修正運算(如插入如插入和刪除和刪除),那么相應的表稱之為動態(tài)查找表那么相應的表稱之為動態(tài)查找表,否那么否那么稱之為靜態(tài)查找表。稱之為靜態(tài)查找表。 由于查找運算的主要運算是關鍵字的比較由于查找運算的主要運算是關鍵字的比較,所以通所以通常把查找過程中對關鍵字需求執(zhí)行的平均比較次數(shù)常把查找過程中對關鍵字需求執(zhí)行的平均比較次數(shù)(也也稱為平均查找長度稱為平均查找長度)作為衡量一個查找算法效率優(yōu)劣的作為衡量一個查找算法效率優(yōu)劣的規(guī)范。平均查找長度規(guī)范。平均查找長度ASL(Average Search Length)定義定義為：為： n1iii

4、cpASL 其中其中,n是查找表中記錄的個數(shù)。是查找表中記錄的個數(shù)。pi是查找第是查找第i個記個記錄的概率錄的概率,普通地普通地,均以為每個記錄的查找概率相等均以為每個記錄的查找概率相等,即即pi=1/n(1in),ci是找到第是找到第i個記錄所需進展的比較次個記錄所需進展的比較次數(shù)。數(shù)。 10.2 10.2 線性表的查找線性表的查找 在表的組織方式中在表的組織方式中, ,線性表是最簡單的一線性表是最簡單的一種。三種在線性表上進展查找的方法：種。三種在線性表上進展查找的方法： (1) (1) 順序查找順序查找 (2) (2) 二分查找二分查找 (3) (3) 分塊查找。分塊查找。 由于不思索在

5、查找的同時對表做修正由于不思索在查找的同時對表做修正, ,故故上述三種查找操作都是在靜態(tài)查找表上實現(xiàn)的。上述三種查找操作都是在靜態(tài)查找表上實現(xiàn)的。 查找與數(shù)據(jù)的存儲構造有關查找與數(shù)據(jù)的存儲構造有關,線性表有順序和鏈式線性表有順序和鏈式兩種存儲構造。本節(jié)只引見以順序表作為存儲構造時兩種存儲構造。本節(jié)只引見以順序表作為存儲構造時實現(xiàn)的順序查找算法。定義被查找的順序表類型定義實現(xiàn)的順序查找算法。定義被查找的順序表類型定義如下：如下： #define MAXL typedef struct KeyType key; /*KeyType為關鍵字的數(shù)據(jù)類為關鍵字的數(shù)據(jù)類型型*/ InfoType data

6、; /*其他數(shù)據(jù)其他數(shù)據(jù)*/ NodeType; typedef NodeType SeqListMAXL; /*順序表類型順序表類型*/ 10.2.1 10.2.1 順序查找順序查找 順序查找是一種最簡單的查找方法。順序查找是一種最簡單的查找方法。 它的根本思緒是：從表的一端開場它的根本思緒是：從表的一端開場, ,順序掃描線性順序掃描線性表表, ,依次將掃描到的關鍵字和給定值依次將掃描到的關鍵字和給定值k k相比較相比較, ,假設當前假設當前掃描到的關鍵字與掃描到的關鍵字與k k相等相等, ,那么查找勝利；假設掃描終那么查找勝利；假設掃描終了后了后, ,仍未找到關鍵字等于仍未找到關鍵字等于k

7、 k的記錄的記錄, ,那么查找失敗。那么查找失敗。 例 如例 如 , , 在 關 鍵 字 序 列 為在 關 鍵 字 序 列 為3,9,1,5,8,10,6,7,2,43,9,1,5,8,10,6,7,2,4的線性表查找的線性表查找關鍵字為關鍵字為6 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次比較次比較:

8、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 10 6 7 2 4 i=6 查找勝利查找勝利,前往序號前往序號6 順序查找的算法如下順序查找的算法如下( (在順序表在順序表R0.n-1R0.n-1中查找關中查找關鍵字為鍵字為k k的記錄的記錄, ,勝利時前往找到的記錄位置勝利時前往找到的記錄位置, ,失敗時前失敗時前往往-1)-1)： int SeqSearch(SeqList R,int n,KeyTyp

9、e k)int SeqSearch(SeqList R,int n,KeyType k) int i=0; int i=0; while (in & Ri.key!=k) i+; / while (i=n) if (i=n) return -1; return -1; else else return i; return i; 從順序查找過程可以看到從順序查找過程可以看到(不思索越界比較不思索越界比較in),ci取決于所查記錄在表中的位置。如查找表中取決于所查記錄在表中的位置。如查找表中第第1個記錄個記錄R0時時,僅需比較一次；而查找表中最后僅需比較一次；而查找表中最后一個記錄一個記錄

10、Rn-1時時,需比較需比較n次次,即即ci=i。因此。因此,勝利時勝利時的順序查找的平均查找長度為：的順序查找的平均查找長度為： 21n2)1n(nn1in1icipsqASLn1in1i 查找勝利時的平均比較次數(shù)約為表長的一半查找勝利時的平均比較次數(shù)約為表長的一半 。10.2.2 10.2.2 二分查找二分查找 二分查找也稱為折半查找要求線性表中的二分查找也稱為折半查找要求線性表中的結點必需己按關鍵字值的遞增或遞減順序陳列。結點必需己按關鍵字值的遞增或遞減順序陳列。它首先用要查找的關鍵字它首先用要查找的關鍵字k k與中間位置的結點與中間位置的結點的關鍵字相比較的關鍵字相比較, ,這個中間結點

11、把線性表分成這個中間結點把線性表分成了兩個子表了兩個子表, ,假設比較結果相等那么查找完成假設比較結果相等那么查找完成; ;假設不相等假設不相等, ,再根據(jù)再根據(jù)k k與該中間結點關鍵字的比與該中間結點關鍵字的比較大小確定下一步查找哪個子表較大小確定下一步查找哪個子表, ,這樣遞歸進這樣遞歸進展下去展下去, ,直到找到滿足條件的結點或者該線性直到找到滿足條件的結點或者該線性表中沒有這樣的結點。表中沒有這樣的結點。 例 如例 如 , , 在 關 鍵 字 有 序 序 列在 關 鍵 字 有 序 序 列2,4,7,9,10,14,18,26,32,402,4,7,9,10,14,18,26,32,40

12、中采用二中采用二分查找法查找關鍵字為分查找法查找關鍵字為7 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 l o w = 0 h i g h = 3 mid=(0+3)/2=1 第第2次比較次比較: 2 4 7 9 10 14 18 26 32 40 l o w = 2 h i g h = 3 mid=(2+3)/2=2 第第3次比較次比較: 2 4 7 9 10 14 18 26 32 40

13、R2.key=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; 二分查找過程可用二叉樹來描畫二分查找過程可用二叉

14、樹來描畫,我們把當前我們把當前查找區(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,1

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

16、假設查找給定值為26的元素的元素,依次與依次與25,30,28元素比較元素比較,共共比較比較3次。次。 (3)在查找勝利時在查找勝利時,會找到圖中某個圓形結點會找到圖中某個圓形結點,那么勝利時的那么勝利時的平均查找長度：平均查找長度：31144342211ASLsucc (1)假設查找給假設查找給定值為定值為20的元素的元素,依依次與表中次與表中25,10,15,20元素比元素比較較,共比較共比較4次。次。 在查找不勝利時在查找不勝利時, ,會找到圖中某個方形結點會找到圖中某個方形結點, ,那么不勝那么不勝利時的平均查找長度：利時的平均查找長度： 67. 3124834ASLunsucc 10

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

18、關鍵字字必需小于后一塊中的最小關鍵字, ,即要求表是即要求表是“分分塊有序的；抽取各塊中的最大關鍵字及其起始位塊有序的；抽取各塊中的最大關鍵字及其起始位置構成一個索引表置構成一個索引表IDX0.b-1,IDX0.b-1,即即IDXi(0ib-IDXi(0ib-1)1)中存放著第中存放著第i i塊的最大關鍵字及該塊在表塊的最大關鍵字及該塊在表R R中的起中的起始位置。由于表始位置。由于表R R是分塊有序的是分塊有序的, ,所以索引表是一個所以索引表是一個遞增有序表。遞增有序表。索引表的數(shù)據(jù)類型定義如下：索引表的數(shù)據(jù)類型定義如下：#define MAXI typedef struct KeyTyp

19、e key; /*KeyType為關鍵字的類型為關鍵字的類型*/ int link; /*指向對應塊的起始指向對應塊的起始下標下標*/ IdxType;typedef IdxType IDXMAXI;/*索引表類型索引表類型*/ 例如,設有一個線性表,其中包含25個記錄,其關鍵字序列為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。假設將。假設將25個記錄分為個記錄分為5塊塊,每塊中有每塊中有5個記個記錄錄,該線性表的索引存儲構造如以下圖所示。該線性表的索引存儲構造如以下圖所示。 14 34

20、66 85 100 0 5 10 15 20 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 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

21、,i; int b=n/m; /*b為每塊的記錄個為每塊的記錄個數(shù)數(shù)*/ while (low=k) high=mid-1; else low=mid+1; if (lowm) /*在塊中順序查找在塊中順序查找*/ i=Ilow.link; while (i=Ilow.link+b-1 & Ri.key!=k) i+; if (ikey=k) /*遞歸終結條件遞歸終結條件*/ return bt; if (kkey) return SearchBST(bt-lchild,k); /*在左子樹中遞歸查找在左子樹中遞歸查找*/ else return SearchBST(bt-rchild

22、,k); /*在右子樹中遞歸查找在右子樹中遞歸查找*/ 2. 二叉排序樹的插入和生成二叉排序樹的插入和生成 在二叉排序樹中插入一個新記錄在二叉排序樹中插入一個新記錄,要保證插入后要保證插入后仍滿足仍滿足BST性質(zhì)。其插入過程是：假設二叉排序樹性質(zhì)。其插入過程是：假設二叉排序樹T為空為空,那么創(chuàng)建一個那么創(chuàng)建一個key域為域為k的結點的結點,將它作為根結點；將它作為根結點；否那么將否那么將k和根結點的關鍵字比較和根結點的關鍵字比較,假設二者相等假設二者相等,那那么闡明樹中已有此關鍵字么闡明樹中已有此關鍵字k,無須插入無須插入,直接前往直接前往0；假；假設設kkey,那么將那么將k插入根結點的左子

23、樹中插入根結點的左子樹中,否那么否那么將它插入右子樹中。對應的遞歸算法將它插入右子樹中。對應的遞歸算法InsertBST()如如下：下：int InsertBST(BSTNode *&p,KeyType k)/*在以在以*p為根結點的為根結點的BST中插入一個關鍵字為中插入一個關鍵字為k的結點。插入的結點。插入勝利前往勝利前往1,否那么前往否那么前往0*/ if (p=NULL) /*原樹為空原樹為空, 新插入的記錄為根結點新插入的記錄為根結點*/ p=(BSTNode *)malloc(sizeof(BSTNode); p-key=k;p-lchild=p-rchild=NULL;

24、return 1; else if (k=p-key) /*存在一樣關鍵字的結點存在一樣關鍵字的結點,前往前往0*/ return 0; else if (kkey) return InsertBST(p-lchild,k);/*插入到左子樹中插入到左子樹中*/ else return InsertBST(p-rchild,k); /*插入到右子樹中插入到右子樹中*/ 二叉排序樹的生成二叉排序樹的生成,是從一個空樹開場是從一個空樹開場,每插入一個關鍵字每插入一個關鍵字,就調(diào)用一次插入算法將它插入到當前已生成的二叉排序樹中。就調(diào)用一次插入算法將它插入到當前已生成的二叉排序樹中。從關鍵字數(shù)組從關鍵

25、字數(shù)組A0.n-1生成二叉排序樹的算法生成二叉排序樹的算法CreatBST()如如下：下： BSTNode *CreatBST(KeyType A,int n) /*前往樹根指針前往樹根指針*/ BSTNode *bt=NULL; /*初始時初始時bt為空樹為空樹*/ int i=0; while (irchild!=NULL) Delete1(p,r-rchild);/*遞歸找最右下結遞歸找最右下結點點*/else /*找到了最右下結點找到了最右下結點*r*/ p-key=r-key; /*將將*r的關鍵字值賦的關鍵字值賦給給*p*/ q=r; r=r-lchild; /*將左子樹的根結點放

26、在被刪結點的位置將左子樹的根結點放在被刪結點的位置上上*/ free(q); /*釋放原釋放原*r的空間的空間*/ void Delete(BSTNode *&p) /*從二叉排序樹中刪除從二叉排序樹中刪除*p結點結點*/ BSTNode *q; if (p-rchild=NULL) /*p結點沒有右子樹的情況結點沒有右子樹的情況*/ q=p; p=p-lchild; /*其右子樹的根結點放在被刪結點的位置上其右子樹的根結點放在被刪結點的位置上*/ free(q); else if (p-lchild=NULL) /*p結點沒有左子樹結點沒有左子樹*/ q=p; p=p-rchild;

27、 /*將將*p結點的右子樹作為雙親結點的相應子樹結點的右子樹作為雙親結點的相應子樹/ free(q); else Delete1(p,p-lchild); /*p結點既沒有左子樹又沒有右子樹的情況結點既沒有左子樹又沒有右子樹的情況*/int DeleteBST(BSTNode *&bt,KeyType k)/*在在bt中刪除關鍵字為中刪除關鍵字為k的結點的結點*/ if (bt=NULL) return 0;/*空樹刪除失敗空樹刪除失敗*/ else if (kkey) return DeleteBST(bt-lchild,k); /*遞歸在左子樹中刪除為遞歸在左子樹中刪除為k的結點的

28、結點*/else if (kbt-key) return DeleteBST(bt-rchild,k); /*遞歸在右子樹中刪除為遞歸在右子樹中刪除為k的結點的結點*/else Delete(bt); /*調(diào)用調(diào)用Delete(bt)函數(shù)刪除函數(shù)刪除*bt結點結點*/ return 1; 10.3.2 10.3.2 平衡二叉樹平衡二叉樹(AVL)(AVL) 假設一棵二叉樹中每個結點的左、右子樹假設一棵二叉樹中每個結點的左、右子樹的高度至多相差的高度至多相差1,1,那么稱此二叉樹為平衡二叉樹。那么稱此二叉樹為平衡二叉樹。在算法中在算法中, ,經(jīng)過平衡因子經(jīng)過平衡因子(balancd factor

29、,(balancd factor,用用bfbf表示表示) )來詳細實現(xiàn)上述平衡二叉樹的定義。平衡因子的定來詳細實現(xiàn)上述平衡二叉樹的定義。平衡因子的定義是：平衡二叉樹中每個結點有一個平衡因子域義是：平衡二叉樹中每個結點有一個平衡因子域, ,每每個結點的平衡因子是該結點左子樹的高度減去右子個結點的平衡因子是該結點左子樹的高度減去右子樹的高度。從平衡因子的角度可以說樹的高度。從平衡因子的角度可以說, ,假設一棵二叉假設一棵二叉樹中一切結點的平衡因子的絕對值小于或等于樹中一切結點的平衡因子的絕對值小于或等于1,1,即即平衡因子取值為平衡因子取值為1 1、0 0或或-1,-1,那么該二叉樹稱為平衡二那么

30、該二叉樹稱為平衡二叉樹。叉樹。 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樹的結點的類型如下：樹的結點的類型如下：typedef struct node /*記錄類型記錄類型*/KeyType key; /*關鍵字項關鍵字項*/ int bf;/*添加的平衡添加的平衡因子因子*/ InfoType data; /*其他數(shù)據(jù)域其他數(shù)據(jù)域*/ struct node *lchild,*rchild;/*左右孩子指左右孩子指針針*/ BS

31、TNode; 假定向平衡二叉樹中插入一個新結點后破壞了平衡二叉樹的平衡性,首先要找出插入新結點后失去平衡的最小子樹根結點的指針,然后再調(diào)整這個子樹中有關結點之間的鏈接關系,使之成為新的平衡子樹。當失去平衡的最小子樹被調(diào)整為平衡子樹后,原有其他一切不平衡子樹無需調(diào)整,整個二叉排序樹就又成為一棵平衡二叉樹。 失去平衡的最小子樹是指以離插入結點最近,且平衡因子絕對值大于1的結點作為根的子樹。假設用A表示失去平衡的最小子樹的根結點,那么調(diào)整該子樹的操作可歸納為以下四種情況： (1) LL型調(diào)整 (2) RR型調(diào)整 (3) LR型調(diào)整 (4) RL型調(diào)整 例例10.3 輸入關鍵字序列輸入關鍵字序列16,

32、3,7,11,9,26,18,14,15,給給出構造一棵出構造一棵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 調(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)R

33、R 調(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 0 11 -1 9 0 18 1 26 0 15 0 0 14 16 0 (n)LR 調(diào)整調(diào)整 在平衡二叉樹上進展查找的過程和在二叉排序樹上在平衡二叉樹上進展查找的過程和在二叉排序樹上進展查

34、找的過程完全一樣，因此，在平衡二叉樹上進進展查找的過程完全一樣，因此，在平衡二叉樹上進展查找關鍵字的比較次數(shù)不會超越平衡二叉樹的深度。展查找關鍵字的比較次數(shù)不會超越平衡二叉樹的深度。 在最壞的情況下，普通二叉排序樹的查找長度為在最壞的情況下，普通二叉排序樹的查找長度為O(n)。那么，平衡二叉樹的情況又是怎樣的呢？下面。那么，平衡二叉樹的情況又是怎樣的呢？下面分析平衡二叉樹的高度分析平衡二叉樹的高度h和結點個數(shù)和結點個數(shù)n之間的關系。之間的關系。 首先，構造一系列的平衡二叉樹首先，構造一系列的平衡二叉樹T1，T2，T3，其，其中，中，Thh=1，2，3，是高度為是高度為h且結點數(shù)盡能夠少的平且結

35、點數(shù)盡能夠少的平衡二叉樹，如圖衡二叉樹，如圖10.12中所示的中所示的T1，T2，T3和和T4。為了構造。為了構造Th，先分別構造，先分別構造Th-1和和Th-2，使，使Th以以Th-1和和Th-2作為其根結作為其根結點的左、右子樹。對于每一個點的左、右子樹。對于每一個Th，只需從中刪去一個結點，只需從中刪去一個結點，就會失去平衡或高度不再是就會失去平衡或高度不再是h顯然，這樣構造的平衡二叉樹顯然，這樣構造的平衡二叉樹在結點個數(shù)一樣的平衡二叉樹中具有最大高度。在結點個數(shù)一樣的平衡二叉樹中具有最大高度。 T1 T2 T3 T4 Th Th-1 Th-2 圖圖10.12 結點個數(shù)結點個數(shù)n最少的平

36、衡二叉樹最少的平衡二叉樹 然后，經(jīng)過計算上述平衡二叉樹中的結點個數(shù)，來建立高度然后，經(jīng)過計算上述平衡二叉樹中的結點個數(shù)，來建立高度與結點個數(shù)之間的關系。設與結點個數(shù)之間的關系。設N(h)為為Th的結點數(shù)，從圖的結點數(shù)，從圖10.12中中可以看出有以下關系成立：可以看出有以下關系成立： N(1)=1，N(2)=2，N(h)=N(h-1)+N(h-2)+1當當h1時，此關系類似于定義時，此關系類似于定義Fibonacci數(shù)的關系：數(shù)的關系： F(1)=1，F(xiàn)(2)=1，F(xiàn)(h)=F(h-1)+F(h-2)經(jīng)過檢查兩個序列的前幾項就可發(fā)現(xiàn)兩者之間的對應關系：經(jīng)過檢查兩個序列的前幾項就可發(fā)現(xiàn)兩者之間的

37、對應關系： N(h)=F(h+2)-1由于由于Fibonacci數(shù)滿足漸近公式：數(shù)滿足漸近公式：F(h)=其中，其中，故由此可得近似公式：故由此可得近似公式：N(h)=即：即：hlog2(N(h)+1)所以，含有所以，含有n個結點的平衡二叉樹的平均查找長度為個結點的平衡二叉樹的平均查找長度為O(log2n)。 h51251 121512 hh10.3.3 B-樹樹 B-樹又稱為多路平衡查找樹樹又稱為多路平衡查找樹,是一種組織和維護外是一種組織和維護外存文件系統(tǒng)非常有效的數(shù)據(jù)構造。存文件系統(tǒng)非常有效的數(shù)據(jù)構造。 B-樹中一切結點的孩子結點最大值稱為樹中一切結點的孩子結點最大值稱為B-樹的階樹的階

38、,通常用通常用m表示表示,從查找效率思索從查找效率思索,要求要求m3。一棵。一棵m階階B-樹或者是一棵空樹樹或者是一棵空樹,或者是滿足以下要求的或者是滿足以下要求的m叉樹：叉樹： (1) 樹中每個結點至多有樹中每個結點至多有m個孩子結點個孩子結點(即至多有即至多有m-1個關鍵字個關鍵字)； (2) 除根結點外除根結點外,其他結點至少有其他結點至少有m/2 個孩子結點個孩子結點(即至少有即至少有m/2 -1=(m-1)/2 個關鍵字個關鍵字)； (3) 假設根結點不是葉子結點假設根結點不是葉子結點,那么根結點至少有兩那么根結點至少有兩個孩子結點；個孩子結點； (4) 每個結點的構造為：每個結點的

39、構造為：np0k1p1k2p2knpn 其中其中,n為該結點中的關鍵字個數(shù)為該結點中的關鍵字個數(shù),除根結點外除根結點外,其其他一切結點的他一切結點的n大于等于大于等于m/2 -1,且小于等于且小于等于m-1；ki(1in)為該結點的關鍵字且滿足為該結點的關鍵字且滿足kiki+1；pi(0in)為該結點的孩子結點指針且滿足為該結點的孩子結點指針且滿足pi(0in-1)結點上的關鍵字大于等于結點上的關鍵字大于等于ki且小于且小于ki+1,pn結點上結點上的關鍵字大于的關鍵字大于kn。 (5) 一切葉子結點都在同一層上一切葉子結點都在同一層上,即即B-樹是一切結樹是一切結點的平衡因子均等于點的平衡因

40、子均等于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-樹的存儲構造中樹的存儲構造中,各結點的類型定義如下：各結點的類型定義如下：#define MAXM 10/*定義定義B-樹的最大的階數(shù)樹的最大的階數(shù)*/typedef int KeyType; /*KeyType為關鍵字類型為關鍵字類型*/typedef struct node /*B-樹結點類型定義樹結點類型定義*/ int keynum; /*結點當前擁有的關

41、鍵字的個數(shù)結點當前擁有的關鍵字的個數(shù)*/ KeyType keyMAXM; /*1.keynum存放關鍵字存放關鍵字,0不用不用*/ struct node *parent; /*雙親結點指針雙親結點指針*/ struct node *ptrMAXM;/*孩子結點指針數(shù)組孩子結點指針數(shù)組0.keynum*/ BTNode;(B-樹的查找樹的查找( 在在B-樹中查找給定關鍵字的方法類似于二叉排樹中查找給定關鍵字的方法類似于二叉排序樹上的查找序樹上的查找,不同的是在每個記錄上確定向下查找不同的是在每個記錄上確定向下查找的途徑不一定是二路的途徑不一定是二路(即二叉即二叉)的的,而是而是n+1路的。由

42、于路的。由于記錄內(nèi)的關鍵字序列是有序的數(shù)量記錄內(nèi)的關鍵字序列是有序的數(shù)量key1.n,故既可故既可以用順序查找以用順序查找,也可以用折半查找。在一棵也可以用折半查找。在一棵B-樹上順樹上順序查找關鍵字為序查找關鍵字為k的方法為：的方法為：將將k與根結點中的與根結點中的keyi進展比較：進展比較： (1) 假設假設k=keyi,那么查找勝利；那么查找勝利； (2) 假設假設kkey1,那么沿著指針那么沿著指針ptr0所指的所指的子樹繼續(xù)查找；子樹繼續(xù)查找； (3) 假設假設keyikkeyi+1,那么沿著指針那么沿著指針ptri所指的子樹繼續(xù)查找；所指的子樹繼續(xù)查找； (4) 假設假設kkeyn

43、,那么沿著指針那么沿著指針ptrn所指的所指的子樹繼續(xù)查找。子樹繼續(xù)查找。 2. B-樹的插入樹的插入將關鍵字將關鍵字k插入到插入到B-樹的過程分兩步完成：樹的過程分兩步完成： (1) 利用前述的利用前述的B-樹的查找算法找出該關鍵字的插入樹的查找算法找出該關鍵字的插入結點結點(留意留意B-樹的插入結點一定是葉子結點樹的插入結點一定是葉子結點)。 (2) 判別該結點能否還有空位置判別該結點能否還有空位置,即判別該結點能否滿即判別該結點能否滿足足nm-1,假設該結點滿足假設該結點滿足nm-1,闡明該結點還有空位闡明該結點還有空位置置,直接把關鍵字直接把關鍵字k插入到該結點的適宜位置上插入到該結點

44、的適宜位置上(即滿足即滿足插入后結點上的關鍵字仍堅持有序插入后結點上的關鍵字仍堅持有序)； 假設該結點有假設該結點有n=m-1,闡明該結點已沒有空位置闡明該結點已沒有空位置,需求把結點分裂成兩個。需求把結點分裂成兩個。 分裂的做法是分裂的做法是,取一新結點取一新結點,把原結點上的關鍵字把原結點上的關鍵字和和 k 按 升 序 排 序 后按 升 序 排 序 后 , 從 中 間 位 置從 中 間 位 置 ( 即即m/2=(m+1)/2之處之處)把關鍵字把關鍵字(不包括中間位不包括中間位置的關鍵字置的關鍵字)分成兩部分分成兩部分,左部分所含關鍵字放在舊左部分所含關鍵字放在舊結點中結點中,右部分所含關鍵

45、字放在新結點中右部分所含關鍵字放在新結點中,中間位置的中間位置的關鍵字連同新結點的存儲位置插入到父親結點中。關鍵字連同新結點的存儲位置插入到父親結點中。假設父結點的關鍵字個數(shù)也超越假設父結點的關鍵字個數(shù)也超越Max,那么要再分裂那么要再分裂,再往上插再往上插,直至這個過程傳到根結點為止。直至這個過程傳到根結點為止。例如例如 關鍵字序列為：關鍵字序列為：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-樹。樹。建立建立B-的過程如以下圖所示。的過程如以下圖所示。 1 2 6 7 6 1 2 7 11 6 1 2 4 7

46、 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,18,19 (h)插入插入 15 11 13 17 20 17 18 19 20 11 12 13 14 4 5

47、11 12 3. B-樹的刪除樹的刪除 B-樹的刪除過程與插入過程類似樹的刪除過程與插入過程類似,只是稍為復雜一些。只是稍為復雜一些。要使刪除后的結點中的關鍵字個數(shù)要使刪除后的結點中的關鍵字個數(shù)m/2 -1,將涉及到將涉及到結點的結點的“合并問題。在合并問題。在B-樹上刪除關鍵字樹上刪除關鍵字k的過程分的過程分兩步完成：兩步完成： (1) 利用前述的利用前述的B-樹的查找算法找出該關鍵字所在的樹的查找算法找出該關鍵字所在的結點。結點。 (2) 在結點上刪除關鍵字在結點上刪除關鍵字k分兩種情況：一種是在葉分兩種情況：一種是在葉子結點上刪除關鍵字；另一種是在非葉子結點上刪除關子結點上刪除關鍵字；另

48、一種是在非葉子結點上刪除關鍵字。鍵字。 (3) 在非葉子結點上刪除關鍵字的過程：假設要刪在非葉子結點上刪除關鍵字的過程：假設要刪除關鍵字除關鍵字keyi(1in),在刪去該關鍵字后在刪去該關鍵字后,以該結點以該結點ptri所指子樹中的最小關鍵字所指子樹中的最小關鍵字keymin來替代被刪關來替代被刪關鍵字鍵字keyi所在的位置所在的位置(留意留意ptri所指子樹中的最小關所指子樹中的最小關鍵字鍵字keymin一定是在葉子結點上一定是在葉子結點上),然后再以指針然后再以指針ptri所指結點為根結點查找并刪除所指結點為根結點查找并刪除keymin(即再以即再以ptri所指結點為所指結點為B-樹的根

49、結點樹的根結點,以以keymin為要刪除的關鍵為要刪除的關鍵字字,然后再次調(diào)用然后再次調(diào)用B-樹上的刪除算法樹上的刪除算法),這樣也就把在非這樣也就把在非葉子結點上刪除關鍵字葉子結點上刪除關鍵字k的問題轉化成了在葉子結點的問題轉化成了在葉子結點上刪除關鍵字上刪除關鍵字keymin的問題。的問題。 (4) 在在B-樹的葉子結點上刪除關鍵字共有以下三種情樹的葉子結點上刪除關鍵字共有以下三種情況：況： 假設被刪結點的關鍵字個數(shù)大于假設被刪結點的關鍵字個數(shù)大于Min,闡明刪去該闡明刪去該關鍵字后該結點仍滿足關鍵字后該結點仍滿足B-樹的定義樹的定義,那么可直接刪去該那么可直接刪去該關鍵字。關鍵字。 假設

50、被刪結點的關鍵字個數(shù)等于假設被刪結點的關鍵字個數(shù)等于Min,闡明刪去關闡明刪去關鍵字后該結點將不滿足鍵字后該結點將不滿足B-樹的定義樹的定義,此時假設該結點的此時假設該結點的左左(或右或右)兄弟結點中關鍵字個數(shù)大于兄弟結點中關鍵字個數(shù)大于Min,那么把該結點那么把該結點的左的左(或右或右)兄弟結點中最大兄弟結點中最大(或最小或最小)的關鍵字上移到雙的關鍵字上移到雙親結點中親結點中,同時把雙親結點中大于同時把雙親結點中大于(或小于或小于)上移關鍵字的上移關鍵字的關鍵字下移到要刪除關鍵字的結點中關鍵字下移到要刪除關鍵字的結點中,這樣刪去關鍵字這樣刪去關鍵字k后該結點以及它的左后該結點以及它的左(或

51、右或右)兄弟結點都仍舊滿足兄弟結點都仍舊滿足B-樹的樹的定義。定義。 假設被刪結點的關鍵字個數(shù)等于假設被刪結點的關鍵字個數(shù)等于Min,并且該并且該結點的左和右兄弟結點結點的左和右兄弟結點(假設存在的話假設存在的話)中關鍵字個中關鍵字個數(shù)均等于數(shù)均等于Min,這時這時,需把要刪除關鍵字的結點與其左需把要刪除關鍵字的結點與其左(或右或右)兄弟結點以及雙親結點中分割二者的關鍵字兄弟結點以及雙親結點中分割二者的關鍵字合并成一個結點。假設因此使雙親結點中關鍵字個合并成一個結點。假設因此使雙親結點中關鍵字個數(shù)小于數(shù)小于Min,那么對此雙親結點做同樣處置那么對此雙親結點做同樣處置,以致于能以致于能夠直到對根

52、結點做這樣的處置而使整個樹減少一層。夠直到對根結點做這樣的處置而使整個樹減少一層。 例如例如,對于上例生成的對于上例生成的B-樹樹,給出刪除給出刪除8,16,15,4等四個關等四個關鍵字的過程。鍵字的過程。 10 3 6 13 17 1 2 4 5 7 9 11 12 14 15 18 19 20 (a) 初始初始 5 階階 B- -樹樹 (b) 刪除刪除 8,16 后的結果后的結果 10 3 6 13 18 1 2 4 5 11 12 14 17 19 20 (c) 刪除刪除 15 后的結果后的結果 6 10 13 18 1 2 3 5 7 9 14 17 19 20 (d) 刪除刪除 4

53、后的結果后的結果 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-樹的一些變形樹的一些變形, ,其中其中B+B+樹是一種運用廣泛的變形。一棵樹是一種運用廣泛的變形。一棵m m階階B+B+樹滿足以樹滿足以下條件：下條件： (1) (1) 每個分支結點至多有每個分支結點至多有m m棵子樹。棵子樹。 (2) (2) 除根結點外除根結點外, ,其他每個分支結點至少有其他每個分支結點至少有(m+1)/2(m+1)/2棵子樹?？米?/p>

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

55、的指針不再指向另一級索引塊引塊,而是直接指向數(shù)據(jù)文件中的記錄而是直接指向數(shù)據(jù)文件中的記錄)。 (6) 一切分支結點一切分支結點(可看成是索引的索引可看成是索引的索引)中僅包中僅包含它的各個子結點含它的各個子結點(即下級索引的索引塊即下級索引的索引塊)中最大關中最大關鍵字及指向子結點的指針。鍵字及指向子結點的指針。 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-樹樹,定義中的前三點是一樣定義中的前三點是一樣的的,主要的差別是：主要的差別是： (1) 在在

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

57、非葉子結點中的關鍵字包含在葉子結點中他非葉子結點中的關鍵字包含在葉子結點中,而在而在B-樹樹中中,葉子結點包含的關鍵字與其他結點包含的關鍵字是葉子結點包含的關鍵字與其他結點包含的關鍵字是不反復的。不反復的。 (4) B+樹中一切非葉子結點僅起到索引的作用樹中一切非葉子結點僅起到索引的作用,即結點中的即結點中的每個索引項只含有對應子樹的最大關鍵字和指向該子樹的指針每個索引項只含有對應子樹的最大關鍵字和指向該子樹的指針,不含有該關鍵字對應記錄的存儲地址。而在不含有該關鍵字對應記錄的存儲地址。而在B-樹中樹中,每個關鍵每個關鍵字對應一個記錄的存儲地址。字對應一個記錄的存儲地址。 (5) 通常在通常在

58、B+樹上有兩個頭指針樹上有兩個頭指針,一個指向根結點一個指向根結點,另一個指另一個指向關鍵字最小的葉子結點向關鍵字最小的葉子結點,一切葉子結點鏈接成一個不定長的一切葉子結點鏈接成一個不定長的線性鏈表。線性鏈表。10.4 10.4 哈希表查找哈希表查找10.4.1 10.4.1 哈希表的根本概念哈希表的根本概念 哈希表哈希表(Hash Table)(Hash Table)又稱散列表又稱散列表, ,是除是除順序表存儲構造、鏈接表存儲構造和索引表存儲順序表存儲構造、鏈接表存儲構造和索引表存儲構造之外的又一種存儲線性表的存儲構造。哈希構造之外的又一種存儲線性表的存儲構造。哈希表存儲的根本思緒是：設要存

59、儲的對象個數(shù)為表存儲的根本思緒是：設要存儲的對象個數(shù)為n,n,設置一個長度為設置一個長度為m(mn)m(mn)的延續(xù)內(nèi)存單元的延續(xù)內(nèi)存單元, ,以線性以線性表中每個對象的關鍵字表中每個對象的關鍵字ki(0in-1)ki(0in-1)為自變量為自變量, ,經(jīng)過一個稱為哈希函數(shù)的函數(shù)經(jīng)過一個稱為哈希函數(shù)的函數(shù)h(ki),h(ki),把把kiki映射映射為內(nèi)存單元的地址為內(nèi)存單元的地址( (或稱下標或稱下標)h(ki),)h(ki),并把該對并把該對象存儲在這個內(nèi)存單元中。象存儲在這個內(nèi)存單元中。h(ki)h(ki)也稱為哈希地也稱為哈希地址址( (又稱散列地址又稱散列地址) )。把如此構造的線性表

60、存儲構。把如此構造的線性表存儲構造稱為哈希表。造稱為哈希表。 但是存在這樣的問題但是存在這樣的問題,對于兩個關鍵字對于兩個關鍵字ki和和kj(ij),有有kikj(ij),但但h(ki)=h(kj)。我們把這種景象叫做哈。我們把這種景象叫做哈希沖突。希沖突。 通常把這種具有不同關鍵字而具有一樣哈希地通常把這種具有不同關鍵字而具有一樣哈希地址的對象稱做址的對象稱做“同義詞同義詞,由同義詞引起的沖突稱作由同義詞引起的沖突稱作同義詞沖突。在哈希表存儲構造的存儲中同義詞沖突。在哈希表存儲構造的存儲中,同義詞沖同義詞沖突是很難防止的突是很難防止的,除非關鍵字的變化區(qū)間小于等于哈除非關鍵字的變化區(qū)間小于等于哈希地址的變化區(qū)間希地址的變化區(qū)間