1、第10章 查找,10.1 查找的基本概念,本章小結,10.2 線性表的查找,10.3 樹表的查找,10.4 哈希表查找,10.1 查找的基本概念 被查找的對象是由一組記錄組成的表或文件,而每個記錄則由若干個數(shù)據(jù)項組成,并假設每個記錄都有一個能惟一標識該記錄的關鍵字。 在這種條件下,查找的定義是：給定一個值k,在含有n個記錄的表中找出關鍵字等于k的記錄。若找到,則查找成功,返回該記錄的信息或該記錄在表中的位置；否則查找失敗,返回相關的指示信息。,采用何種查找方法? (1) 使用哪種數(shù)據(jù)結構來表示“表”,即表中記錄是按何種方式組織的。 (2) 表中關鍵字的次序。是對無序集合查找還是對有序集合查找?

2、,若在查找的同時對表做修改運算(如插入和刪除),則相應的表稱之為動態(tài)查找表,否則稱之為靜態(tài)查找表。,由于查找運算的主要運算是關鍵字的比較,所以通常把查找過程中對關鍵字需要執(zhí)行的平均比較次數(shù)(也稱為平均查找長度)作為衡量一個查找算法效率優(yōu)劣的標準。平均查找長度ASL(Average Search Length)定義為：,其中,n是查找表中記錄的個數(shù)。pi是查找第i個記錄的概率,一般地,均認為每個記錄的查找概率相等,即pi=1/n(1in),ci是找到第i個記錄所需進行的比較次數(shù)。,10.2 線性表的查找 在表的組織方式中,線性表是最簡單的一種。三種在線性表上進行查找的方法： (1) 順序查找 (

3、2) 二分查找 (3) 分塊查找。 因為不考慮在查找的同時對表做修改,故上述三種查找操作都是在靜態(tài)查找表上實現(xiàn)的。,查找與數(shù)據(jù)的存儲結構有關,線性表有順序和鏈式兩種存儲結構。本節(jié)只介紹以順序表作為存儲結構時實現(xiàn)的順序查找算法。定義被查找的順序表類型定義如下： #define MAXL typedef struct KeyType key; /*KeyType為關鍵字的數(shù)據(jù)類型*/ InfoType data; /*其他數(shù)據(jù)*/ NodeType; typedef NodeType SeqListMAXL; /*順序表類型*/,10.2.1 順序查找 順序查找是一種最簡單的查找方法。 它的基本思

4、路是：從表的一端開始,順序掃描線性表,依次將掃描到的關鍵字和給定值k相比較,若當前掃描到的關鍵字與k相等,則查找成功；若掃描結束后,仍未找到關鍵字等于k的記錄,則查找失敗。,例如,在關鍵字序列為3,9,1,5,8,10,6,7,2,4的線性表查找關鍵字為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次比

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-1中查找關鍵字為k的記錄,成功時返回找到的記錄位置,失敗時返回-1)： int SeqSearch(SeqList R,int n,KeyType k) int i=0; while (i=n) return -1; else return i; ,從順序查找過程可以看到(不考慮越界比較in),ci取決于所查記錄在表中的位置。如查找表中第1個記錄R0時,

6、僅需比較一次；而查找表中最后一個記錄Rn-1時,需比較n次,即ci=i。因此,成功時的順序查找的平均查找長度為：,查找成功時的平均比較次數(shù)約為表長的一半 。,10.2.2 二分查找 二分查找也稱為折半查找要求線性表中的結點必須己按關鍵字值的遞增或遞減順序排列。它首先用要查找的關鍵字k與中間位置的結點的關鍵字相比較,這個中間結點把線性表分成了兩個子表,若比較結果相等則查找完成;若不相等,再根據(jù)k與該中間結點關鍵字的比較大小確定下一步查找哪個子表,這樣遞歸進行下去,直到找到滿足條件的結點或者該線性表中沒有這樣的結點。,用Low、High和Mid表示待查找區(qū)間的下界、上界和中間位置指針，初值為Low

7、=0，High=n-1。 取中間位置Mid：Mid=(Low+High)/2 ； 比較中間位置記錄的關鍵字與給定的K值： 相等： 查找成功； 大于：待查記錄在區(qū)間的前半段，修改上界指針： High=Mid-1，轉 ； 小于：待查記錄在區(qū)間的后半段，修改下界指針：Low=Mid+1，轉 ； 直到越界(LowHigh)，查找失敗。,例如,在關鍵字有序序列2,4,7,9,10,14,18,26,32,40中采用二分查找法查找關鍵字為7的元素。 二分查找過程如下：,開始: 2 4 7 9 10 14 18 26 32 40 low=0 high=9 mid=(0+9)/2=4 第1次比較: 2 4 7

8、 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=7 查找成功,返回序號2,示例 如圖9-2(a)，(b)所示。,其算法如下(在有序表R0.n-1中進行二分查找,成功時返回記錄的位置,失敗時返回-1)： int BinSearch(SeqList R,int n,KeyType k) int low=0,high=n-1,mid; while (low

9、k) /*繼續(xù)在Rlow.mid-1中查找*/ high=mid-1; else low=mid+1; /*繼續(xù)在Rmid+1.high中查找*/ return -1; ,二分查找過程可用二叉樹來描述,我們把當前查找區(qū)間的中間位置上的記錄作為根,左子表和右子表中的記錄分別作為根的左子樹和右子樹,由此得到的二叉樹,稱為描述二分查找的判定樹或比較樹。 查找成功時的平均查找長度ASL：,當n很大 (n50)時， ASL 2(n+1)-1。,R0.10的二分查線的判定樹(n=11),例10.1對于給定11個數(shù)據(jù)元素的有序表2,3,10,15,20,25,28,29,30,35,40,采用二分查找,試問

10、： (1)若查找給定值為20的元素,將依次與表中哪些元素比較？ (2)若查找給定值為26的元素,將依次與哪些元素比較？ (3)假設查找表中每個元素的概率相同,求查找成功時的平均查找長度和查找不成功時的平均查找長度。,二分查找判定樹,(2)若查找給定值為26的元素,依次與25,30,28元素比較,共比較3次。 (3)在查找成功時,會找到圖中某個圓形結點,則成功時的平均查找長度：,(1)若查找給定值為20的元素,依次與表中25,10,15,20元素比較,共比較4次。,10.2.3 分塊查找 分塊查找又稱索引順序查找,它是一種性能介于順序查找和二分查找之間的查找方法。,1 查找表的組織 將查找表分成

11、幾塊。塊間有序，即第i+1塊的所有記錄關鍵字均大于(或小于)第i塊記錄關鍵字；塊內無序。 在查找表的基礎上附加一個索引表，索引表是按關鍵字有序的，索引表中記錄的構成是：,2 查找思想 先確定待查記錄所在塊，再在塊內查找(順序查找)。,索引表的數(shù)據(jù)類型定義如下： #define MAXI typedef struct KeyType key; /*KeyType為關鍵字的類型*/ int link; /*指向對應塊的起始下標*/ IdxType; typedef IdxType IDXMAXI;/*索引表類型*/,例如,設有一個線性表,其中包含25個記錄,其關鍵字序列為8,14,6,9,10,2

12、2,34,18,19,31,40,38,54,66, 46,71,78,68,80,85,100, 94,88,96,87。假設將25個記錄分為5塊,每塊中有5個記錄,該線性表的索引存儲結構如下圖所示。,采用二分查找索引表的分塊查找算法如下(索引表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ù)*/ while (low=k) high=mid-1; else low=mid+1; ,if (lowm) /*在塊中順序查找*

13、/ i=Ilow.link; while (i=Ilow.link+b-1 ,設表長為n個記錄，均分為b塊，每塊記錄數(shù)為s，則b=n/s。設記錄的查找概率相等，每塊的查找概率為1/b，塊中記錄的查找概率為1/s，則平均查找長度ASL：,查找方法比較,10.3 樹表的查找 當表的插入或刪除操作頻繁時,為維護表的有序性,需要移動表中很多記錄。這種由移動記錄引起的額外時間開銷,就會抵消二分查找的優(yōu)點。也就是說,二分查找只適用于靜態(tài)查找表。若要對動態(tài)查找表進行高效率的查找,可采用下面介紹的幾種特殊的二叉樹或樹作為表的組織形式,在這里將它們統(tǒng)稱為樹表。下面將分別討論在這些樹表上進行查找和修改操作的方法。

14、,10.3.1 二叉排序樹 二叉排序樹(簡稱BST)又稱二叉查找(搜索)樹,其定義為：二叉排序樹或者是空樹,或者是滿足如下性質的二叉樹： (1) 若它的左子樹非空,則左子樹上所有記錄的值均小于根記錄的值； (2) 若它的右子樹非空,則右子樹上所有記錄的值均大于根記錄的值； (3) 左、右子樹本身又各是一棵二叉排序樹。,結論：若按中序遍歷一棵二叉排序樹，所得到的結點序列是一個遞增序列。 BST仍然可以用二叉鏈表來存儲,在討論二叉排序樹上的運算之前,定義其結點的類型如下： typedef struct node /*記錄類型*/ KeyType key; /*關鍵字項*/ InfoType dat

15、a; /*其他數(shù)據(jù)域*/ struct node *lchild,*rchild;/*左右孩子指針*/ BSTNode;,1. 二叉排序樹上的查找 因為二叉排序樹可看做是一個有序表,所以在二叉排序樹上進行查找,和二分查找類似,也是一個逐步縮小查找范圍的過程。 查找思想: 首先將給定的K值與二叉排序樹的根結點的關鍵字進行比較：若相等： 則查找成功； 給定的K值小于BST的根結點的關鍵字：繼續(xù)在該結點的左子樹上進行查找； 給定的K值大于BST的根結點的關鍵字：繼續(xù)在該結點的右子樹上進行查找。,遞歸查找算法SearchBST()如下(在二叉排序樹bt上查找關鍵字為k的記錄,成功時返回該結點指針,否則

16、返回NULL)： BSTNode *SearchBST(BSTNode *bt,KeyType k) if (bt=NULL | bt-key=k) /*遞歸終結條件*/ return bt; if (kkey) return SearchBST(bt-lchild,k); /*在左子樹中遞歸查找*/ else return SearchBST(bt-rchild,k); /*在右子樹中遞歸查找*/ ,2. 二叉排序樹的插入和生成 在二叉排序樹中插入一個新記錄,要保證插入后仍滿足BST性質。其插入過程是：若二叉排序樹T為空,則創(chuàng)建一個key域為k的結點,將它作為根結點；否則將k和根結點的關鍵字

17、比較,若二者相等,則說明樹中已有此關鍵字k,無須插入,直接返回0；若kkey,則將k插入根結點的左子樹中,否則將它插入右子樹中。對應的遞歸算法InsertBST()如下：,int InsertBST(BSTNode * /*插入到右子樹中*/ ,二叉排序樹的生成,是從一個空樹開始,每插入一個關鍵字,就調用一次插入算法將它插入到當前已生成的二叉排序樹中。從關鍵字數(shù)組A0.n-1生成二叉排序樹的算法CreatBST()如下： BSTNode *CreatBST(KeyType A,int n) /*返回樹根指針*/ BSTNode *bt=NULL; /*初始時bt為空樹*/ int i=0; w

18、hile (in) InsertBST(bt,Ai); /*將Ai插入二叉排序樹T中*/ i+; return bt; /*返回建立的二叉排序樹的根指針*/ ,例10.2 已知一組關鍵字為25,18,46,2,53,39,32,4,74,67,60,11。按表中的元素順序依次插入到一棵初始為空的二叉排序樹中,畫出該二叉排序樹,并求在等概率的情況下查找成功的平均查找長度。 解：生成的二叉排序樹如右圖所示。,3. 二叉排序樹的刪除 刪除操作必須首先進行查找,假設在查找過程結束時,已經保存了待刪除結點及其雙親結點的地址。指針變量p指向待刪除的結點,指針變量q指向待刪除結點p的雙親結點。刪除過程如下：

19、 (1) 若待刪除的結點是葉子結點,直接刪去該結點。如圖(a)所示,直接刪除結點9。這是最簡單的刪除結點的情況。,(2) 若待刪除的結點只有左子樹而無右子樹。根據(jù)二叉排序樹的特點,可以直接將其左子樹的根結點放在被刪結點的位置。如圖(b)所示,*p作為*q的右子樹根結點,要刪除*p結點,只需將*p的左子樹(其根結點為3)作為*q結點的右子樹。,(3) 若待刪除的結點只有右子樹而無左子樹。與(2)情況類似,可以直接將其右子樹的根結點放在被刪結點的位置。如圖(c)所示,*p作為*q的左子樹根結點,要刪除*p結點,只需將*p的右子樹(其根結點為8)作為*q結點的右子樹。,(4) 若待刪除的結點同時有左

20、子樹和右子樹。根據(jù)二叉排序樹的特點,可以從其左子樹中選擇關鍵字最大的結點或從其右子樹中選擇關鍵字最小的結點放在被刪去結點的位置上。假如選取左子樹上關鍵字最大的結點,那么該結點一定是左子樹的最右下結點。如圖(d)所示,若要刪除*p(其關鍵字為5)結點,找到其左子樹最右下結點4,它的雙親結點為2,用它代替*p結點,并將其原來的左子樹(其根結點為3)作為原來的雙親結點2的右子樹。,BST樹的刪除, 若p是葉子結點： 直接刪除p，如圖9-5(b)所示。 若p只有一棵子樹(左子樹或右子樹)：直接用p的左子樹(或右子樹)取代p的位置而成為f的一棵子樹。即原來p是f的左子樹，則p的子樹成為f的左子樹；原來p

21、是f的右子樹，則p的子樹成為f的右子樹, 若p既有左子樹又有右子樹 ：處理方法有以下兩種，可以任選其中一種。 用p的直接前驅結點代替p。即從p的左子樹中選擇值最大的結點s放在p的位置(用結點s的內容替換結點p內容)，然后刪除結點s。s是p的左子樹中的最右邊的結點且沒有右子樹，對s的刪除同 用p的直接后繼結點代替p。即從p的右子樹中選擇值最小的結點s放在p的位置(用結點s的內容替換結點p內容)，然后刪除結點s。s是p的右子樹中的最左邊的結點且沒有左子樹，對s的刪除同,刪除二叉排序樹結點的算法DeleteBST()如下(指針變量p指向待刪除的結點,指針變量q指向待刪除結點*p的雙親結點)： voi

22、d Delete1(BSTNode *p,BSTNode * /*釋放原*r的空間*/ ,void Delete(BSTNode * /*p結點既沒有左子樹又沒有右子樹的情況*/ ,int DeleteBST(BSTNode * ,10.3.2 平衡二叉樹(AVL) 若一棵二叉樹中每個結點的左、右子樹的高度至多相差1,則稱此二叉樹為平衡二叉樹。在算法中,通過平衡因子(balancd factor,用bf表示)來具體實現(xiàn)上述平衡二叉樹的定義。平衡因子的定義是：平衡二叉樹中每個結點有一個平衡因子域,每個結點的平衡因子是該結點左子樹的高度減去右子樹的高度。從平衡因子的角度可以說,若一棵二叉樹中所有結

23、點的平衡因子的絕對值小于或等于1,即平衡因子取值為1、0或-1,則該二叉樹稱為平衡二叉樹。,平衡二叉樹和不平衡二叉樹,定義AVL樹的結點的類型如下： typedef struct node /*記錄類型*/ KeyType key; /*關鍵字項*/ int bf;/*增加的平衡因子*/ InfoType data; /*其他數(shù)據(jù)域*/ struct node *lchild,*rchild;/*左右孩子指針*/ BSTNode;,假定向平衡二叉樹中插入一個新結點后破壞了平衡二叉樹的平衡性,首先要找出插入新結點后失去平衡的最小子樹根結點的指針,然后再調整這個子樹中有關結點之間的鏈接關系,使之成

24、為新的平衡子樹。當失去平衡的最小子樹被調整為平衡子樹后,原有其他所有不平衡子樹無需調整,整個二叉排序樹就又成為一棵平衡二叉樹。 失去平衡的最小子樹是指以離插入結點最近,且平衡因子絕對值大于1的結點作為根的子樹。假設用A表示失去平衡的最小子樹的根結點,則調整該子樹的操作可歸納為下列四種情況：,(1) LL型調整,(2) RR型調整,(3) LR型調整,(4) RL型調整,例10.3 輸入關鍵字序列16,3,7,11,9,26,18,14,15,給出構造一棵AVL樹的步驟。,在平衡二叉樹上進行查找的過程和在二叉排序樹上進行查找的過程完全相同，因此，在平衡二叉樹上進行查找關鍵字的比較次數(shù)不會超過平衡

25、二叉樹的深度。 在最壞的情況下，普通二叉排序樹的查找長度為O(n)。那么，平衡二叉樹的情況又是怎樣的呢？下面分析平衡二叉樹的高度h和結點個數(shù)n之間的關系。,首先，構造一系列的平衡二叉樹T1，T2，T3，其中，Th（h=1，2，3，）是高度為h且結點數(shù)盡可能少的平衡二叉樹，如圖10.12中所示的T1，T2，T3和T4。為了構造Th，先分別構造Th-1和Th-2，使Th以Th-1和Th-2作為其根結點的左、右子樹。對于每一個Th，只要從中刪去一個結點，就會失去平衡或高度不再是h（顯然，這樣構造的平衡二叉樹在結點個數(shù)相同的平衡二叉樹中具有最大高度）。,圖10.12 結點個數(shù)n最少的平衡二叉樹,然后，

26、通過計算上述平衡二叉樹中的結點個數(shù)，來建立高度 與結點個數(shù)之間的關系。設N(h)為Th的結點數(shù)，從圖10.12中 可以看出有下列關系成立： N(1)=1，N(2)=2，N(h)=N(h-1)+N(h-2)+1 當h1時，此關系類似于定義Fibonacci數(shù)的關系： F(1)=1，F(xiàn)(2)=1，F(xiàn)(h)=F(h-1)+F(h-2) 通過檢查兩個序列的前幾項就可發(fā)現(xiàn)兩者之間的對應關系： N(h)=F(h+2)-1 由于Fibonacci數(shù)滿足漸近公式：F(h)= 其中， 故由此可得近似公式：N(h)= 即：hlog2(N(h)+1) 所以，含有n個結點的平衡二叉樹的平均查找長度為O(log2n)。

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

28、除根結點外,其他所有結點的n大于等于m/2-1,且小于等于m-1；ki(1in)為該結點的關鍵字且滿足kiki+1；pi(0in)為該結點的孩子結點指針且滿足pi(0in-1)結點上的關鍵字大于等于ki且小于ki+1,pn結點上的關鍵字大于kn。 (5) 所有葉子結點都在同一層上,即B-樹是所有結點的平衡因子均等于0的多路查找樹。,一棵5階B-樹,在B-樹的存儲結構中,各結點的類型定義如下： #define MAXM 10/*定義B-樹的最大的階數(shù)*/ typedef int KeyType; /*KeyType為關鍵字類型*/ typedef struct node /*B-樹結點類型定義*

29、/ int keynum; /*結點當前擁有的關鍵字的個數(shù)*/ KeyType keyMAXM; /*1.keynum存放關鍵字,0不用*/ struct node *parent; /*雙親結點指針*/ struct node *ptrMAXM;/*孩子結點指針數(shù)組0.keynum*/ BTNode;,B-樹的查找 在B-樹中查找給定關鍵字的方法類似于二叉排序樹上的查找,不同的是在每個記錄上確定向下查找的路徑不一定是二路(即二叉)的,而是n+1路的。因為記錄內的關鍵字序列是有序的數(shù)量key1.n,故既可以用順序查找,也可以用折半查找。在一棵B-樹上順序查找關鍵字為k的方法為：,將k與根結點中

30、的keyi進行比較： (1) 若k=keyi,則查找成功； (2) 若kkey1,則沿著指針ptr0所指的子樹繼續(xù)查找； (3) 若keyikkeyi+1,則沿著指針ptri所指的子樹繼續(xù)查找； (4) 若kkeyn,則沿著指針ptrn所指的子樹繼續(xù)查找。,2. B-樹的插入 將關鍵字k插入到B-樹的過程分兩步完成： (1) 利用前述的B-樹的查找算法找出該關鍵字的插入結點(注意B-樹的插入結點一定是葉子結點)。 (2) 判斷該結點是否還有空位置,即判斷該結點是否滿足nm-1,若該結點滿足nm-1,說明該結點還有空位置,直接把關鍵字k插入到該結點的合適位置上(即滿足插入后結點上的關鍵字仍保持有

31、序)；,若該結點有n=m-1,說明該結點已沒有空位置,需要把結點分裂成兩個。 分裂的做法是,取一新結點,把原結點上的關鍵字和k按升序排序后,從中間位置(即m/2=(m+1)/2之處)把關鍵字(不包括中間位置的關鍵字)分成兩部分,左部分所含關鍵字放在舊結點中,右部分所含關鍵字放在新結點中,中間位置的關鍵字連同新結點的存儲位置插入到父親結點中。如果父結點的關鍵字個數(shù)也超過Max,則要再分裂,再往上插,直至這個過程傳到根結點為止。,例如 關鍵字序列為： 1,2,6,7,11,4,8,13,10,5,17,9,16,20,3,12,14,18,19,15。 創(chuàng)建一棵5階B-樹。 建立B-的過程如下圖所

32、示。,3. B-樹的刪除 B-樹的刪除過程與插入過程類似,只是稍為復雜一些。要使刪除后的結點中的關鍵字個數(shù)m/2-1,將涉及到結點的“合并”問題。在B-樹上刪除關鍵字k的過程分兩步完成： (1) 利用前述的B-樹的查找算法找出該關鍵字所在的結點。 (2) 在結點上刪除關鍵字k分兩種情況：一種是在葉子結點上刪除關鍵字；另一種是在非葉子結點上刪除關鍵字。,(3) 在非葉子結點上刪除關鍵字的過程：假設要刪除關鍵字keyi(1in),在刪去該關鍵字后,以該結點ptri所指子樹中的最小關鍵字keymin來代替被刪關鍵字keyi所在的位置(注意ptri所指子樹中的最小關鍵字keymin一定是在葉子結點上)

33、,然后再以指針ptri所指結點為根結點查找并刪除keymin(即再以ptri所指結點為B-樹的根結點,以keymin為要刪除的關鍵字,然后再次調用B-樹上的刪除算法),這樣也就把在非葉子結點上刪除關鍵字k的問題轉化成了在葉子結點上刪除關鍵字keymin的問題。,(4) 在B-樹的葉子結點上刪除關鍵字共有以下三種情況： 假如被刪結點的關鍵字個數(shù)大于Min,說明刪去該關鍵字后該結點仍滿足B-樹的定義,則可直接刪去該關鍵字。 假如被刪結點的關鍵字個數(shù)等于Min,說明刪去關鍵字后該結點將不滿足B-樹的定義,此時若該結點的左(或右)兄弟結點中關鍵字個數(shù)大于Min,則把該結點的左(或右)兄弟結點中最大(或

34、最小)的關鍵字上移到雙親結點中,同時把雙親結點中大于(或小于)上移關鍵字的關鍵字下移到要刪除關鍵字的結點中,這樣刪去關鍵字k后該結點以及它的左(或右)兄弟結點都仍舊滿足B-樹的定義。, 假如被刪結點的關鍵字個數(shù)等于Min,并且該結點的左和右兄弟結點(如果存在的話)中關鍵字個數(shù)均等于Min,這時,需把要刪除關鍵字的結點與其左(或右)兄弟結點以及雙親結點中分割二者的關鍵字合并成一個結點。如果因此使雙親結點中關鍵字個數(shù)小于Min,則對此雙親結點做同樣處理,以致于可能直到對根結點做這樣的處理而使整個樹減少一層。,例如,對于上例生成的B-樹,給出刪除8,16,15,4等四個關鍵字的過程。,10.3.4

35、B+樹 在索引文件組織中,經常使用B-樹的一些變形,其中B+樹是一種應用廣泛的變形。一棵m階B+樹滿足下列條件： (1) 每個分支結點至多有m棵子樹。 (2) 除根結點外,其他每個分支結點至少有(m+1)/2棵子樹。 (3) 根結點至少有兩棵子樹,至多有m棵子樹。 (4) 有n棵子樹的結點有n個關鍵字。,(5) 所有葉子結點包含全部(數(shù)據(jù)文件中記錄) 關鍵字及指向相應記錄的指針(或存放數(shù)據(jù)文件分塊后每塊的最大關鍵字及指向該塊的指針),而且葉子結點按關鍵字大小順序鏈接(可以把每個葉子結點看成是一個基本索引塊,它的指針不再指向另一級索引塊,而是直接指向數(shù)據(jù)文件中的記錄)。 (6) 所有分支結點(可

36、看成是索引的索引)中僅包含它的各個子結點(即下級索引的索引塊)中最大關鍵字及指向子結點的指針。,一棵4階的B+樹,m階的B+樹和m階的B-樹,定義中的前三點是相同的,主要的差異是： (1) 在B+樹中,具有n個關鍵字的結點含有n棵子樹,即每個關鍵字對應一棵子樹,而在B-樹中,具有n個關鍵字的結點含有(n+1)棵子樹。 (2) 在B+樹中,每個結點(除根結點外)中的關鍵字個數(shù)n的取值范圍是m/2n m,根結點n的取值范圍是1nm；而在B-樹中,它們的取值范圍分別是m/2-1n m-1和1nm-1。 (3) B+樹中的所有葉子結點包含了全部關鍵字,即其他非葉子結點中的關鍵字包含在葉子結點中,而在B

37、-樹中,葉子結點包含的關鍵字與其他結點包含的關鍵字是不重復的。,(4) B+樹中所有非葉子結點僅起到索引的作用,即結點中的每個索引項只含有對應子樹的最大關鍵字和指向該子樹的指針,不含有該關鍵字對應記錄的存儲地址。而在B-樹中,每個關鍵字對應一個記錄的存儲地址。 (5) 通常在B+樹上有兩個頭指針,一個指向根結點,另一個指向關鍵字最小的葉子結點,所有葉子結點鏈接成一個不定長的線性鏈表。,10.4 哈希表查找 10.4.1 哈希表的基本概念 哈希表(Hash Table)又稱散列表,是除順序表存儲結構、鏈接表存儲結構和索引表存儲結構之外的又一種存儲線性表的存儲結構。哈希表存儲的基本思路是：設要存儲

38、的對象個數(shù)為n,設置一個長度為m(mn)的連續(xù)內存單元,以線性表中每個對象的關鍵字ki(0in-1)為自變量,通過一個稱為哈希函數(shù)的函數(shù)h(ki),把ki映射為內存單元的地址(或稱下標)h(ki),并把該對象存儲在這個內存單元中。h(ki)也稱為哈希地址(又稱散列地址)。把如此構造的線性表存儲結構稱為哈希表。,但是存在這樣的問題,對于兩個關鍵字ki和kj(ij),有kikj(ij),但h(ki)=h(kj)。我們把這種現(xiàn)象叫做哈希沖突。 通常把這種具有不同關鍵字而具有相同哈希地址的對象稱做“同義詞”,由同義詞引起的沖突稱作同義詞沖突。在哈希表存儲結構的存儲中,同義詞沖突是很難避免的,除非關鍵字

39、的變化區(qū)間小于等于哈希地址的變化區(qū)間,而這種情況當關鍵字取值不連續(xù)時是非常浪費存儲空間的。通常的實際情況是關鍵字的取值區(qū)間遠大于哈希地址的變化區(qū)間。,歸納起來： (1)哈希函數(shù)是一個映象,即：將關鍵字的集合映射到某個地址集合上,它的設置很靈活,只要這個地址集合的 大小不超出允許范圍即可； (2)由于哈希函數(shù)是一個壓縮映象,因此,在一般情況下,很容易產生“沖突”現(xiàn)象,即：key1key2,而 f(key1) = f(key2)。 (3) 很難找到一個不產生沖突的哈希函數(shù)。一般情況下,只能選擇恰當?shù)墓：瘮?shù),使沖突盡可能少地產生。,10.4.2 哈希函數(shù)構造方法 構造哈希函數(shù)的目標是使得到的哈希地

40、址盡可能均勻地分布在n個連續(xù)內存單元地址上,同時使計算過程盡可能簡單以達到盡可能高的時間效率。 1. 直接定址法 直接定址法是以關鍵字k本身或關鍵字加上某個數(shù)值常量c作為哈希地址的方法。直接定址法的哈希函數(shù)h(k)為： h(k)=k+c (c0) 這種哈希函數(shù)計算簡單,并且不可能有沖突發(fā)生。當關鍵字的分布基本連續(xù)時,可用直接定址法的哈希函數(shù)；否則,若關鍵字分布不連續(xù)將造成內存單元的大量浪費。,2. 除留余數(shù)法 除留余數(shù)法是用關鍵字k除以某個不大于哈希表長度m的數(shù)p所得的余數(shù)作為哈希地址的方法。除留余數(shù)法的哈希函數(shù)h(k)為： h(k)=k mod p (mod為求余運算,pm) p最好取小于m的質數(shù)(素數(shù))。,3. 數(shù)字分析法 該方法是提取關鍵字中取值較均勻的數(shù)字位作為哈希地址的方法。它適合于所有關鍵字值都已知的情況,并需要對關鍵字中每一位的取值分布情況進行分析。 例如,對于一組關鍵字： 92317602,92326875,92739628,92343634,92706816, 92774638,92381262,92394220 通過分析可知,每個關鍵字從左到右的第1、2、3位和第6位取值較集中,不宜作為哈希函數(shù),剩余的第4、5、7和8位取值較分散,可根據(jù)實際需要取其中的若干位作為哈希地址。若取最