1、數據結構C語言描述（慕課版）第6章 查找編著：張同珍 & 學校： 上海交通大學查找靜態查找動態查找哈希方法靜態查找表：相對穩定、鮮有變化的數據，其中數據稱為靜態的。靜態數據的存儲僅需朝著有利于查找的目標來完成，最便利的存儲方式是順序存儲，相應的查找技術稱為靜態查找技術。高級語言中數組可以實現順序存儲。順序查找算法：010203元素從1下標存到n下標，0下標作為哨兵位。當要查找數據x時，首先將x存入哨兵位，然后從n下標開始向前一直到0下標去匹配x。當和x匹配成功位置大于0時表示x存在, 查找成功；當和x匹配成功位置等于0時表示x不存在，查找不成功。哨兵位保證了即便數據中沒有x，x也能在哨兵位被找

2、到，哨兵位起到了阻止下標越界的擋板作用。順序查找算法代碼：void main() int a11=0, 72, 90, 25, 60, 30, 70, 80,19, 20, 35, i, x;printf(Input the data you want to seek: );scanf(%d, &x);a0 = x;for (i=10; i=0; i-)if (ai=x) break; /比較成功，退出循環if (i=0) printf(%d doesnt exist! %d , x, i);else printf(%d exists! %d , x, i);待查找元素如果不存在：從n下標比到

3、了0下標，元素比較次數為n+1。待查找元素如果存在：當查找的元素為倒數第一個元素時，比較次數為1；當查找元素為倒數第二個元素時，比較次數為2，以此類推，當查找元素為第一個元素時，比較次數為n。每個元素如果被查找的概率相同(均為1/n)，則平均查找時間即其數學期望，為：(1+2+3+n)*1/n=(n+1)/2順序查找算法時間復雜度分析：因此無論查找成功與否，時間復雜度均為O(n)。首先在序列中間位置匹配x, 匹配成功，則結束；匹配不成功，當待查數據x大于中間位置元素，在序列后一半中繼續匹配；當待查數據x小于中間位置元素，在序列前一半中繼續匹配；折半查找算法思路：當數據元素序列有序時，可以采用更

4、快速方法。分析：int find(Type a, int low, int high, Type x) while (low=high) mid = (low+high)/2; if (x=amid) break; /查找成功 else if (xamid) /x小于中間位置元素 high = mid -1; else /x大于中間位置元素 low = mid +1; if (lowdata) return t;if (xdata)return find1(t-left, x);elsereturn find1(t-right,x);查找程序實現：/非遞歸算法struct node * fin

5、d2(struct node *t, int x) while (t) if (x=t-data) return t;if (xdata) t=t-left;else t=t-right; return NULL; 時間復雜度為二叉查找樹的高度。二叉查找樹基本操作-插入：插入實際上也是一個查找操作，搜索用于插入的空結點的具體位置。如在圖中插入45，相繼和80、40、50比較，查找到空結點為50的左子結點位置。特殊地：當根結點為空時，新插入結點作為根結點。特點：插入的時間消耗也是二叉樹的高度。插入程序實現：void insert(struct node *r, int x)struct node

6、 *tmp; if (!r) /如果查找樹的根為空，直接建立一個結點并作為根結點tmp = (struct node *)malloc(sizeof(struct node); tmp-data = x; tmp-left = NULL; tmp-right = NULL; root = tmp; return; if (x=r-data) return; /已經在二叉樹中插入程序實現：if (xdata) if (!r-left) /左子為空，插入位置即此地tmp = (struct node *)malloc(sizeof(struct node); tmp-data = x; tmp-l

7、eft = NULL; tmp-right = NULL; r-left = tmp; return; elseinsert(r-left, x); /左子不為空，插入以左子為根的查找樹中插入程序實現： else if (!r-right) tmp = (struct node *)malloc(sizeof(struct node); tmp-data = x; tmp-left = NULL; tmp-right = NULL; r-right = tmp; return;elseinsert(r-right, x); /右子不為空，插入以右子為根的查找樹中二叉查找樹基本操作刪除：首先搜索

8、待刪除結點的具體位置。如在圖中刪除35，刪除30、刪除80。231刪除有二子的結點：左子樹最大值或右子樹最小結點作為替身移到該位，如40。刪除有唯一子的結點：將子替代其位，如30。刪除葉子：直接刪除，如35。如上刪除分三種情況，采用不同方法處理：特點：刪除的時間消耗也是二叉樹的高度。刪除程序實現：void delElem(struct node *t, struct node *parent, int x)int childFlag; /用來保存沿左子還是右子，左子為-1，右子為1while (t)if (t-data = x) break;if (xdata) parent = t; chi

9、ldFlag = -1; t=t-left;else parent = t; childFlag = 1; t=t-right; if (!t) return; /無值為x的結點，結束刪除if (parent) /結點t不是根結點 if (!t-left & !t-right) /t為葉子結點 if (childFlag=-1) parent-left = NULL;else parent-right = NULL;free(t); return;if (t-left & !t-right) /t的左子不空，右子空 if (childFlag=-1) parent-left = t-left;

10、 else parent-right = t-left; free(t); return; if (！t-left & t-right) /t的左子不空，右子空 if (childFlag=-1) parent-left = t-right; else parent-right = t-right; free(t); return; /左右子都不為空，在左子樹中找最大結點作為替身結點 p = t-left; while (p-right) p=p-right; t-data = p-data; /替身結點值復制上去 parent = t; childFlag = -1; /以左子為根，刪除替身

11、結點，替身結點無右子 delElem(t-left, t, p-data); 刪除程序實現：else /結點t是根結點 if (!t-left & !t-right) /t為葉子結點 root = NULL; free(t); return; if (t-left & !t-right) /t的左子不空，有子空 root = t-left; free(t); return; if (!t-left & t-right) /t的右子不空，左子空 root = t-right; free(t); return; 刪除程序實現：/左右子都不為空，在左子樹中找最大結點作為替身結點p = t-left;

12、while (p-right) p=p-right;t-data = p-data; /替身結點值復制上去parent = t; childFlag = -1; /以左子為根，刪除替身結點，替身結點無右子delElem(t-left, t, p-data); 問題：在集合中查找第i個順序統計量。靜態表：順序存儲并排序，在下標i-1處找到目標，時間花費為數組排序的時間。動態表：使用二叉查找樹存儲。查找第1小元素，順著根一路左子下去，找到最左側結點即為最小結點，時間復雜度是二叉樹的高度；查找第n小元素即最大元素，順著根一路右子下去，找到最右側結點即為最大結點，時間復雜度也是樹的高度。對每個結點增加

13、一個size字段，記錄以該結點為根的二叉查找樹中結點的個數。如何找第i小結點（不是1或者n） ？首先和根比較，如果根的size小于i則結果為無第i小結點，結束查找。查找方式：如果根的size值等于i，則沿其右子找最右側結點就是第i小結點。特別地，如果沒有右子，根自己為第i小結點；如果根的size值大于i，那么看它的左子如果左子的size小于i,則看右子，問題變成在右子樹中找第k小結點，其中k=i-(上面左子的size+父結點1)。特別地，如果k=0，則根結點就是第i小的結點。如果左子的size大于或者等于i,則在以左子為根的二叉查找樹中重復以上操作去找第i小結點。每層最多檢查兩個結點，時間消耗

14、樹高的兩倍。特點：如：在圖中找第3小元素：根80的size=8，比3大，找左子40；40的size=4，比3大，找左子30；30的size=2，比3小，故找40的右子50；在50子樹中找第3-(2+1)=0個結點，因此50的父結點40就是第3小的結點。如：在圖中找第6小元素：根80的size=8，比6大，找左子40；40的size=4，比6小，找父結點80的右子150；在以150為根的子樹中找第6-(4+1)=1個最小的值，這樣，順著150一路左子找最左側結點100，它就是第6小結點。第二種方法：對二叉樹做一次中序遍歷，顯然遍歷結果序列是從小到大有序的。如果將該結果放入一個數組中，下標為i-1

15、的元素即第i小元素。時間消耗為中序遍歷花費，時間復雜度為O(n)；數組為額外空間消耗，空間復雜度為O(n)。特殊的二叉查找樹平衡二叉查找樹紅黑樹B樹、B+樹二叉查找樹樹高的各種情況：樹高最高情況：極端情況，如左、右單支樹，即每層只有一個結點。樹高n。樹高最矮情況：滿二叉樹、完全二叉樹、共k層但前k-1層滿第k層不滿?；蛘呷苯Y點只出現在最后兩層的某些情況。條件逐漸松弛二叉查找樹樹高的各種情況：結點的平衡因子：一個結點的平衡因子等于其左子樹的高度減去其右子樹的高度。平衡二叉樹：如果一棵二叉樹中所有結點的平衡因子的絕對值不超過1，即為-1，0，1這三種情況，則這棵二叉樹為平衡二叉樹。平衡二叉樹不一定

16、最矮，最矮的也不一定平衡。元素插入到平衡二叉樹中，可能造成不平衡。如單支樹就是在元素的逐次插入中形成的非平衡二叉樹。平衡二叉查找樹的插入：插入時平衡因子的變化：如果父結點平衡因子變為0，說明原本的左右子樹一邊高一邊低，現在低的長高了，變得和高的一樣了，自下而上的傳導行為停止，祖父包括更上層祖先結點的平衡因子保持不變；如果是由右子樹傳導上來，說明右子樹高度增加了1，父結點平衡因子減1；如果父結點平衡因子變為非0，傳導依然按照來自左子樹加1、右子樹減1的原則向祖父結點傳導，當某一層祖先結點的平衡因子變為0或者到達根結點，傳導結束；當某一層祖先結點平衡因子超出-1,0,1范圍，停下待調整。如果是由左

17、子樹傳導上來，說明左子樹高度增加了1，父結點平衡因子加1；新插入結點的平衡因子為0，自下而上往祖先結點傳導：某結點平衡因子不在-1、0、+1的范圍內，該結點稱為沖突結點。插入后，在平衡因子值向上傳導的過程中，一旦發現沖突結點，就停下來調整。沖突結點：一種情況的調整示例：各種情況的調整分析：LL、RR型一次旋轉LR、RL型二次旋轉LR、RL型二次旋轉LR、RL型二次旋轉LR、RL型二次旋轉平衡二叉樹的刪除：有兩個孩子的結點在刪除時，可以找個替身結點，最終轉化為刪除葉子或有一個孩子結點的情況。010203刪除分為葉子結點；有一個孩子的結點；有兩個孩子的結點。分以下情況討論對結點平衡因子影響:當刪除

18、結點的父結點平衡因子原本為0，即其左右子樹一樣高，為h。當刪除結點的父結點平衡因子原本為1，即其左子樹高為h、右子樹矮為h-1。當刪除結點的父結點平衡因子原本為-1，即其左子樹矮為h-1、右子樹高為h。各種情況詳細討論:當刪除結點的父結點平衡因子原本為0，即其左右子樹一樣高，為h。01當左子樹中有結點刪除，父結點的平衡因子減1，變為-1以父結點為根的子樹的高度仍為h，未變，平衡因子變化傳導結束。02當右子樹中有結點刪除，父結點的平衡因子加1，變為+1，以父結點為根的子樹的高度仍為h，未變，平衡因子變化傳導結束。當刪除結點的父結點平衡因子原本為1，即其左子樹高為h、右子樹矮為h-1。01當刪除父

19、結點的右子時，右子樹更矮一層，父結點的平衡因子加1，變為2，成為沖突結點，直接進入調整階段。調整后新的父結點平衡因子為0，繼續向上傳導。02當刪除父結點的左子時，左子樹變矮，父結點平衡因子變為0，以父結點為根的子樹變矮為h-1，平衡因子的變化還需要向父結點的父結點傳導，直到某一層父結點平衡因子由0變為非0或者到達根結點。各種情況詳細討論:各種情況詳細討論:當刪除結點的父結點平衡因子原本為-1，即其左子樹矮為h-1、右子樹高為h。刪除左子，平衡因子減1，變為-2，成為沖突結點，進入調整階段。調整后新的父結點平衡因子為0，調整繼續向上傳導。刪除右子，平衡因子加1，變為0，平衡因子變化向上層父結點的

20、父結點傳導，直到某一層父結點平衡因子由0變為非0或者到達根結點。總之，沖突結點的調整，根據LL、RR、LR、RL四種形態分別做和插入一樣的旋轉處理。平衡二叉樹的最大高度：假設H為二叉平衡樹的最大高度，n為結點的個數，則有： F(H+2)-1=n=F(H+3)-1其中F(m)為斐波那契數列1，1，2，3，5，8，13，21，。n取具體值的情況：02OPTION當n=2時， F(2+2)=3， F(2+3)=5，滿足2=2=4，故H=2；03OPTION當n=3時， F(2+2)=3， F(2+3)=5，滿足2=3=4，故H=2；04OPTION05OPTION當n=12時，F(5+2)=13，

21、F(5+3)=21，滿足12=12=20，故H=5。當n=1時， F(1+2)=2， F(1+3)=3，滿足1=1=2，故H=1；01OPTION最小高度情況之一是完全二叉樹，其高度為log2n +1， 如=時，最小高度為4。當n=20時，F(5+2)=13， F(5+3)=21，滿足12=20=20，故H=5，最小高度為log220 +1，也是5。反過來看：高度為3的平衡二叉樹，最少的結點個數為F(H+2)-1即F(5)-1=5-1=4、最多的結點個數為F(H+3)-1=8-1=7。特殊的二叉查找樹平衡二叉查找樹紅黑樹B樹、B+樹所有結點分為黑紅兩色，且滿足以下條件：樹中任何一個結點，在以它

22、為根的子樹中，由它到達子樹中任何一個空鏈域的路徑上黑結點個數相等。根結點是黑色的。任何紅結點不得有紅色孩子，下圖中底色透明的為紅結點，否則為黑結點。圖(b)中，50-30-20-左空鏈域，黑色結點3個；50-30-40-右空鏈域，黑色結點2個。故不是紅黑樹。231紅色結點只能有黑色孩子結點。黑結點可以有紅色孩子結點或者黑色孩子結點。任何路徑上黑色結點可以連續，但紅結點不可以連續。特點分析：從紅黑樹中的某個結點出發，在眾多的到空鏈域的路徑中，最長的一條是紅黑均勻相間的，最短的一條是全為黑結點的，最長的一條和最短的一條比，前者長度是后者的一倍。因此在后序操作過程中，如果時間花費為樹的高度，則最長和

23、最短差別最多是一倍。當一個結點插入一個二叉查找樹中時，總是插入到某個路徑末端的空鏈域上，原本的空鏈域指向這個新的結點，新結點是葉子結點。按照紅黑樹條件，新加入的結點肯定是紅結點，否則從根到這個新結點的路徑上，黑結點的個數就多出一個了。紅黑樹的插入：例如：左邊紅黑樹中，插入結點88，因父結點85為黑色，插入后仍為紅黑樹，插入結束。當父結點為紅色時，產生連續紅結點，需要調整。父結點無兄弟父結點有兄弟各種情況的分析和調整：父結點無兄弟01030204新結點、父結點、祖父結點形成LL形態新結點、父結點、祖父結點形成RR形態新結點、父結點、祖父結點形成LR形態新結點、父結點、祖父結點形成RL形態1. 父

24、結點無兄弟： 插入10后：LL型（RR型類似）1. 父結點無兄弟 插入18后：LR型（RL型類似）2.父結點有兄弟： 父有紅兄弟父有黑兄弟：初始不可能，調整時某個中間過程可能出現。插入時，父結點為紅色，故祖父結點只能是黑色；因新結點、父結點都為紅色，新結點又是葉子，故從祖父到其下所有空鏈域上黑色結點個數只能是1，這時父結點不可能有黑色兄弟；父結點兄弟只能是紅色，且一定是個葉子；否則祖父結點在父結點兄弟方向路徑上黑結點個數至少有2個。處理方法：直接對祖父和父、父兄結點換色，讓祖父結點變為紅色，父和父兄結點變為黑色。如插入51， 父有紅兄。第一次調整：2.父結點有兄弟： 父有紅兄弟第二次調整：父有

25、黑兄弟處理方法：當無兄弟情況，按照LL、RR、LR、RL分別處理。 如處理到某個中間狀態，為左圖所示：父紅父有黑兄2.父結點有兄弟： 父有黑兄弟，調整時某個中間過程可能出現。紅黑樹的刪除：刪除可以歸為刪除葉子結點、只有一個孩子的結點和有兩個孩子的結點。有兩個孩子的結點刪除時，可以先找個替身結點，和替身結點交換位置并交換顏色后再刪除替身結點。因為交換了顏色，在紅黑樹中仍保持各個位置顏色不變，刪除變為刪葉子或者只有一個孩子的情況。刪除只有一個孩子的結點這個結點只能是黑色，孩子只能是紅色。否則從該結點向下各個空鏈域上黑結點個數不等。處理方法：孩子代替刪除結點的位置和顏色，處理結束。刪除的各種情況分析

26、：刪除葉子結點：葉子結點是紅結點： 直接刪除，仍為紅黑樹。如刪圖(a）中60。葉子結點是黑結點： 經過該黑結點到空鏈域的路徑上黑結點少一個，須調整。根據不同父、兄情況分別進行分析處理！父紅、兄黑、兄無子：處理方法：父、兄顏色互換。黑色上升后，補充了黑葉子鏈上的缺失。父紅、兄黑、兄有一子/兄的子必為紅色處理方法：LL型，做LL型旋轉調整。 因黑兄成為新的根，補充刪除結點路徑上黑結點的缺失。父紅、兄黑、兄有一子/兄的子必為紅色處理方法：LR型，先兄、兄子換色，再做LR型旋轉處理。父紅、兄黑、兄有兩子 /因刪黑葉子，兄兩子必都為紅色分LL或者RR型旋轉，旋轉后原兄和兩子換色。處理方法：父黑、兄黑、兄

27、無子處理方法：如果叔紅，先做祖父、叔、叔子的LL或者RR單旋、換色，然后做一次父及父兩子換色，刪除40的情況轉為父紅、兄黑、兄無子處理。父黑、兄黑、兄無子處理方法：兄變紅；如果叔黑，叔變紅。（從祖父結點往下到空鏈域的各條路徑上黑結點少1，如果祖父為根則結束，否則繼續看祖父、祖父的父親、祖父的兄弟是哪種關系。）父黑、兄黑、兄有一子 /一子必為紅子處理方法： LL、RR、LR、RL型進行相應旋轉調整。 旋轉前兄子染黑。父黑、兄黑、兄有兩子： /兩子必為紅色處理方法：分LL、RR型旋轉調整，旋轉前，兄一子變黑。（一子：LL、RR內子）父黑、兄紅、兄有兩子： /兩子必為黑色處理方法：分LL、RR型旋轉

28、調整，旋轉前，交換原兄和兄一子的顏色。（一子：LL、RR外子）特殊的二叉查找樹平衡二叉查找樹紅黑樹B樹、B+樹B樹是可用來建立索引的多路查找樹，也稱多路搜索樹。M階的B樹須滿足如下定義：02OPTION樹中如果有多個結點，根結點至少有兩個兒子、至多有M個兒子03OPTION或者為空、或者只有一個根結點、或者除了根還有多個結點。01OPTION04OPTION非葉子結點結構如下：(,0,1,1,1,2,2,2, )，其中：n為關鍵字的個數，有n個關鍵字就意味著有n+1個孩子，為關鍵字，為關鍵字為的數據在原始文件中的地址，(1)為在樹中關鍵字值小于的結點的地址，為在樹中關鍵字值大于的結點的地址。0

29、5OPTION葉子結點都在最后一層，且不帶任何信息，可以視做空結點、表示查找失敗。一個5階B樹：除了根有2個孩子，每個結點最少3個孩子。每個關鍵字后的空心箭頭表示其在原始數據文件中的地址。所有的關鍵字都會出現在圖中某個非葉子結點中。葉子結點其實都是空結點，是查找失敗的標志。B樹的查找：例一 找30首先從B樹的根結點入手，30關鍵字不在根結點中，值小于50，因此順50左側指針走向第二層的第一個結點，30在這個孩子結點中，為該孩子結點的第二個關鍵字，30關鍵字找到后，其右側空心箭頭即標志其在原始數據文件中的具體地址。B樹的查找：例二，找33首先從根開始，順著根到第一個孩子，33大于第一個孩子的第二

30、個關鍵字，因此再順30右側指針走到第三層的第三個結點，在第三個結點中，有關鍵字32和35，順32和35之間的指針走向第四層結點，發現指向第四層結點的指針為空，即告查找失敗，說明關鍵字為33的結點不在原始數據文件中。按查找方法，因關鍵字不存在，就會找到最后一層，將關鍵字插入到結點中，根據結點中關鍵字的個數做相應的處理。插入關鍵字按查找方法，找到第三層最后一個結點，將90插入到77和92之間，該結點關鍵字個數由3變為4，結束。插入關鍵字90插入后所在結點的孩子個數將大于5，將結點一分為二分裂后，將中間關鍵字上升到父結點，如果父結點關鍵字滿再次上升，這里父結點關鍵字未滿，結束。再插入關鍵字105新建

31、B樹視作結點逐個插入:首先是有一個空樹；插入60，成為只有一個根結點的樹，根結點目前只有兩個孩子；逐步插入70、80、90，依然只有一個根結點，目前根的孩子有5個。新建B樹視作結點逐個插入：依次插入65、75、63最后需要得到的一棵B樹。B樹的插入的思考：02OPTION為什么樹中根可以只有一個關鍵字即有兩個孩子；03OPTION插入操作如同查找，首先找到最后一層空結點位置，在其父結點處插入一個新的關鍵字；04OPTION如果情況需要就逐步向上進行結點分裂，樹的高度是在逐步插入的過程中分裂結點并向上建立新結點產生的。為什么定義樹可以為空；01OPTIONB樹的插入的時間消耗：插入后如果引起結點

32、分裂，最差情況是：分裂逐步上移，直到分裂根結點；從根結點逐步向下移動查找，需要比較的次數為B樹的高度；總的時間花費是兩倍于B樹的高度。B樹的刪除：欲在原始數據文件中刪除數據，只需要在其B樹索引文件中刪除該數據關鍵字，原始文件中數據可以暫時不做處理，留在后面做定期的批量數據清理維護。刪除：首先查找，查找待刪數據關鍵字在B樹中的哪個結點上，根據結點的情況，將刪除按照以下幾種情況分別處理：待刪的關鍵字在最下非葉子結點層，再下層就是空結點了。待刪的關鍵字在中間層，下層仍為非葉子結點層。圖1待刪的關鍵字在中間層，下層仍為非葉子結點層。找到待刪數據的關鍵字，順關鍵字左側孩子找到最大關鍵字或者順著關鍵字右子

33、找到最小關鍵字替代之，然后層層下移，直到找到的替身結點為最后一層非葉子結點。如刪除圖1中的關鍵字50。要刪除左圖中的關鍵字50，在其下一層找左側結點中找個最大關鍵字30上移，繼續下行，在原30位置的右側孩子中找個最小關鍵字32上移，最后刪除關鍵字的替身位置即如右圖中紅色塊的位置，這個按照上面情況1）就可以處理了。M階的B+樹定義如下：02OPTION每個結點至多有M個孩子。03OPTION04OPTION有k個孩子的結點有k個關鍵字，每個關鍵字的值代表其孩子結點中關鍵字的最大值。05OPTION葉子結點和中間結點不同，它的孩子是外部數據塊。06OPTION或者為空、或者只有一個根結點、或者除了

34、根還有多個結點。01OPTION一個3階B+樹的示例，其中M=3，L=4：插入和刪除關鍵字的操作和B樹類似，先查找后進行插入和刪除。在插入過程中也面臨著結點分裂的可能，在刪除的過程中也面臨著借用、合并的可能，各種情況的處理方式和B樹相同。B+樹的插入、刪除：B樹關鍵字和地址對應關系可能分布在任何結點中，所以查找可能停止在任何一層，時間花費小于等于樹的高度。B+由于關鍵字和數據塊地址對應關系全部存儲在葉子結點中，查找必須從根到達葉子結點，所以時間花費一定是樹的高度。B樹、B+樹的時間消耗比較：B+樹可以方便按照關鍵字順序遍歷：1. 用一個變量保存第一個葉子結點的地址作為頭指針。2. 每個葉子結點

35、尾部增加一個指針，指向右邊相鄰的第一個葉子結點的地址。3. 最后一個葉子結點中的該指針指向空。需要按序訪問時，順著頭指針便能訪問到所有結點。B+樹中階數M和數據塊大小L的計算：計算機讀寫磁盤一次為一個磁盤塊，通常大小為4KB（4*1024）字節。B+樹可以設計為一個磁盤塊對應B+樹中的一個結點，對應一個數據塊。例如一個例子：一個記錄200個字節、每個記錄中關鍵字的大小為16個字節、磁盤塊號為4個字節、磁盤中原始數據文件中有1000000個記錄。M的計算：L的計算：原始數據文件中有1000000個記錄：最少需要1000000/L=50000個數據塊最多需要1000000/（L/2）=100000

36、個數據塊查找時間最壞即B+樹樹高最大的情況: 最多100000個數據塊，意味著葉子結點要有100000個關鍵字。第一層最少1個結點、第二層最少2個結點、第三層最少2*102個、第四層最少2*102*102=20808個，但20808100000，第五層為數據塊層，所以最壞情況B樹樹高為4層。01020304外存上的文件中，數據量大，通常按原始順序存放。索引文件按照索引關鍵字順序存儲關鍵字和數據在原始文件中地址的對應關系。為了加快數據的查找速度，建立索引文件是最普遍的做法。查找時先在索引文件中按關鍵字查找，找到該關鍵字對應的數據地址，再到原始數據文件中讀取。查找靜態查找動態查找哈希方法無論靜態還

37、是動態查找，都通過對數據關鍵字值的比較來完成；查找時間的消耗也和數據的規模有關，如順序查找時間消耗為O(n)、折半查找和平衡二叉樹查找為O(log2 )。能否查找時間耗費和規模n無關？哈希方法哈希方法：對關鍵字key，通過函數映射H(key)計算出關鍵字為key的數據在內存中的存儲地址。哈希方法相關概念：映射到的內存空間是一個能存m個數據的連續存儲空間，這個連續空間稱哈希表、m稱哈希表的大小。映射函數H(key)稱哈希函數。實際存儲的元素和哈希表大小的比值=稱為負載系數。不同的數據映射到不同的地址、高負載系數，可達到最理想的時間復雜度O(1)。但上面兩個條件常常矛盾、不可兼得。以上“哈?！眱勺忠渤Ｒ浴吧⒘小贝?，有散列函數、散列表理想的哈希函數：010203計算速度快。哈希到的地址均勻、沖突少。哈希表的負載率高。盡量減少空間的浪費。好的哈希函數需要滿足以下條件：哈希函數的選擇沒有統一的方法，和實際數據元素值的特點和分布有關。哈希