實(shí)現(xiàn)數(shù)據(jù)的存儲和查找是計(jì)算機(jī)最常見的應(yīng)用

1、第八章 查找（Searching）實(shí)現(xiàn)數(shù)據(jù)的存儲和查找是計(jì)算機(jī)最常見的應(yīng)用。本章介紹 查找的概念 常用查找方法及其實(shí)現(xiàn)順序查找 二分查找 散列法查找的概念 查找表：同類型元素（記錄）構(gòu)成的集合，每個(gè)元素具有一個(gè)關(guān)鍵字域。 關(guān)鍵字：記錄中用以標(biāo)識一個(gè)記錄的值。能夠唯一標(biāo)識一個(gè)記錄的關(guān)鍵字稱為主關(guān)鍵字（碼）。 查找（搜索）：給定一個(gè)值，在查找表中確定是否存在一個(gè)記錄，其關(guān)鍵字等于給定的值。 如果存在，則查找成功，結(jié)果是相應(yīng)記錄的內(nèi)容，或者記錄的位置； 如果不存在，則查找失敗，結(jié)構(gòu)是空記錄或者空指針。使用庫函數(shù)查找假設(shè)查找表由形如（姓名，電話號碼）的記錄構(gòu)成，如（“Zhang Heng”，84111

2、099），（“Wang Heng”，84031234），（“Zhang Min”，84110088）等標(biāo)準(zhǔn)模版庫STL(standard template library)提供了一種支持存儲和快速查詢這種二元組形式記錄的“有序關(guān)聯(lián)容器”map。map phones;phones.insert(pair(Zhang Heng， 84111099)iterator find (const key_type& value)int main() map phones; /初始化一個(gè)map容器 phonesZhang Heng = 84111099; /插入記錄 phonesWang Heng

3、= 84031234; phonesZhang Min = 84110088; phonesLin Jie = 84113030; phonesMei Jie = 84112034; map:iterator cur =phones.find(Zhang Min); if (cur != phones.end() /如果查找失敗，cur指向容器“末尾”，否則指向找到的記錄 cout Zhang Mins phone is (*cur).second endl; else cout Zhang Min doesnt exist in phones. endl; 如何實(shí)現(xiàn)查找呢？ 查找方法與查找表

4、的“結(jié)構(gòu)”密切相關(guān)； 查找問題的目標(biāo)：合理組織數(shù)據(jù)，實(shí)現(xiàn)高效查找。 查找的效率： 主要操作：關(guān)鍵碼比較； 主要時(shí)間指標(biāo)：平均查找長度ASL（Average Search Length）; 其它指標(biāo)：存儲空間，算法復(fù)雜程度。 靜態(tài)查找表：查找過程不會改變查找表； 動態(tài)查找表：查找過程會改變查找表；靜態(tài)查找表 靜態(tài)查找表一經(jīng)建立結(jié)構(gòu)不會改變； 主要操作是查找: search(ST, key); 初始條件：靜態(tài)查找表ST存在，key為給定關(guān)鍵字； 操作結(jié)果：若ST中存在關(guān)鍵字等于key的記錄，則返回該記錄或者記錄在表中的位置，否則，返回“空”。 數(shù)據(jù)組織方式： 順序表或者線性鏈表，查找方式為順序查找

5、； 查找表有序，使用順序表表示；查找方式為折半查找； 索引順序表，使用分塊查找； 關(guān)鍵字類型typedef int KeyType; /關(guān)鍵字為整型typedef char* KeyType; /關(guān)鍵字為串型 記錄類型typdef struct KeyType key; /關(guān)鍵字域 /其它域 ElemType；順序查找 查找表的結(jié)構(gòu)：順序表或者線性鏈表；/靜態(tài)查找表的順序存儲結(jié)構(gòu) typdef struct ElemType * elem; /數(shù)據(jù)元素存儲空間基址 /建表時(shí)按實(shí)際長度分配，0號單元留空 int length; /表長度 SSTable；查找方法查找方法：順序查找（：順序查找（S

6、equential SearchSequential Search），即從），即從表的第一個(gè)元素開始，順序比較記錄的關(guān)鍵字與給定表的第一個(gè)元素開始，順序比較記錄的關(guān)鍵字與給定的的keykey是否相同，若相等，則返回記錄的位序，否則，是否相同，若相等，則返回記錄的位序，否則，返回，表示不存在。返回，表示不存在。 順序查找的實(shí)現(xiàn)（使用監(jiān)視哨）：int Search_Seq(SSTable ST，KeyType key) /在順序表ST中順序查找其關(guān)鍵字等于key的數(shù)據(jù)元素。 /若找到，則函數(shù)值為該元素在表中的位置，否則為0。 ST.elem0.key = key; /0號單元作為監(jiān)視哨 for (

7、 i=ST.length; ST.elemi.key!=key; -i ); /從后往前找, 比較至多進(jìn)行到i=0 return i； /找不到時(shí)，i為0 / Search_Seq 監(jiān)視哨：一個(gè)用于終止 循環(huán)的單元，循環(huán)在這里終止表示一個(gè)特殊的終止條件?？梢院喕吔鐥l件檢測。順序查找的性能 使用關(guān)鍵字的比較次數(shù)衡量查找的性能； 查找成功的平均查找長度ASL：對于含有n個(gè)記錄的表，查找成功時(shí)的平均查找長度 ASLsucc Pi為查找表中第i個(gè)記錄的概率，且Pi =1； Ci為找到表中其關(guān)鍵字與給定值相等的第i個(gè)記錄時(shí)，和給定值已進(jìn)行過比較的關(guān)鍵字個(gè)數(shù)。 對于上述算法，Ci=n-i+1; 假定每個(gè)

8、記錄的查找概率相同，即Pi=1/n, 則ASLsucc = iniiCP1=)-(nininn1=21+=1+1 查找失敗需要比較n+1次； 平均查找長度：假定查找成功概率為p,查找失敗的概率為 q=1-p, 則平均查找長度為)(-()(-(1+21=1+1+21+npnpnp順序查找的特點(diǎn)：順序查找的特點(diǎn)：P結(jié)構(gòu)簡單，算法簡單；查找表的插入簡單；結(jié)構(gòu)簡單，算法簡單；查找表的插入簡單；平均檢索時(shí)間長。平均檢索時(shí)間長。折半查找（Binary Search ） 存儲結(jié)構(gòu)：查找表按照關(guān)鍵碼有序，使用順序表存儲； 搜索方法：比較給定關(guān)鍵字與查找表中間記錄（的關(guān)鍵字）， 若相等，則查找成功； 若給定關(guān)鍵

9、字小于中間記錄，則到左半部子表查找；否則， 到右半部子表查找 當(dāng)查找子表為空時(shí)，查找失敗。折半查找示例例如：已知如下11個(gè)數(shù)據(jù)元素的有序表(關(guān)鍵字即為數(shù)據(jù)元素的值)： (05，13，19，21，37，56，64，75，80，88，92) low mid high 現(xiàn)要查找關(guān)鍵字為21和85的數(shù)據(jù)元素。 假設(shè)指針low和high分別指示待查元素所在范圍的下界和上界，指針mid指示區(qū)間的中間位置，即 mid=(low+high)/2。 在此例中，low和high的初值分別為1和11，即1，11為待查范圍。 折半查找示例 查找21的過程：05 13 19 21 37 56 64 75 80 88 9

10、2 low (1) mid (6) high(11)05 13 19 2l 37 56 64 75 80 88 92 low mid high05 13 19 2l 37 56 64 75 80 88 92 low high midmid=(low+high)/22119,轉(zhuǎn)到右半子表, low=mid+1折半查找示例 查找85：05 13 19 21 37 56 64 75 80 88 92 l o w m i d highlow mid high low highmidhigh lowST.elemmid.keykey 令low=mid+1ST.elemmid.keykey 令high=m

11、id-1highlow, 查找范圍空，查找失敗。折半查找的實(shí)現(xiàn)int Search_Bin(SSTable ST，KeyType key) /在有序表ST中折半查找其關(guān)鍵字等于key的數(shù)據(jù)元素。 /若找到，則函數(shù)值為該元素在表中的位置，否則為0。 low=1; high=ST.lenqth； /置區(qū)間初值 while (low=high) mid = (low+high)/2 if (key= ST.elemmid.key) return mid; /找到待查元素 else if (keydata.key) return (T)； /查找結(jié)束查找結(jié)束 else if (keydata.key)

12、 return (SearchBST(T-lchild，key)； /在左子樹中繼續(xù)查找在左子樹中繼續(xù)查找 else return (SearchBST(T-rchild，key)； / 在右子樹中繼續(xù)查找在右子樹中繼續(xù)查找/SearchBST typedef struct BinTreeNode ElemType data; struct BinTreeNode *lchild, *rchild;/左右孩子指針左右孩子指針 BinTreeNode, *BinTree ;在插入之前先使用搜索算法在樹中檢查要插入元素是否存在。 搜索成功: 樹中已有這個(gè)元素，不再插入搜索不成功: 樹中原來沒有關(guān)鍵

13、碼等于給定值的結(jié)點(diǎn)，把新元素加到搜索操作停止的地方插入插入88： 從空樹出發(fā)，經(jīng)過一系列的查找插入操作之后，可生成一棵二叉查找樹。設(shè)查找的關(guān)鍵字序列為45，24，53，45，12，24，9，則生成的二叉查找樹如下所示454524452453452453124524531290 (a)空樹；空樹； (b)插入插入45； (c)插入插入24； (d)插入插入53； (e)插入插入12； (f)插入插入90。 Status Insert (BinTree& ptr， const ElemType & x,) /二叉搜索樹插入算法,若樹中不存在x.key, 則插入否則返回FALSE i

14、f ( ptr = NULL ) /空二叉樹 ptr = (BiTree)mlloc(sizeof(BinTreeNode); /創(chuàng)建 x 結(jié)點(diǎn) if ( ptr = NULL ) exit (1); else ptr-data = x; ptr-lchild=ptr-rchild=NULL; return TRUE else if ( x.key ptrdata.key ) /在右子樹插入 return Insert ( ptrrchild, x); else return FALSE; /樹中存在關(guān)鍵字x.key二叉查找樹的刪除78的前驅(qū)二叉查找樹的刪除 在二叉搜索樹中刪除一個(gè)結(jié)點(diǎn)時(shí)，必須

15、確保二叉搜索樹的性質(zhì)不會失去。 刪除葉結(jié)點(diǎn)，只需將其雙親結(jié)點(diǎn)指向它的指針清零，再釋放它即可。 被刪結(jié)點(diǎn)無右子樹，可以拿它的左子女結(jié)點(diǎn)頂替它的位置，再釋放它。 被刪結(jié)點(diǎn)無左子樹，可以拿它的右子女結(jié)點(diǎn)頂替它的位置，再釋放它。 被刪結(jié)點(diǎn)左、右子樹都存在，可以在它的左子樹中尋找中序下的最后一個(gè)結(jié)點(diǎn)(關(guān)鍵碼最大),用它的值填補(bǔ)到被刪結(jié)點(diǎn)中，再來處理這個(gè)結(jié)點(diǎn)的刪除問題。qFCPQSpcsFSCQpcq刪除結(jié)點(diǎn)刪除結(jié)點(diǎn)P:1.1.尋找尋找P P的直接前驅(qū)的直接前驅(qū)S, S, 則則S S無右子結(jié)點(diǎn)；無右子結(jié)點(diǎn)；2.2.用結(jié)點(diǎn)用結(jié)點(diǎn)S S代替代替P;P;3.3.刪除結(jié)點(diǎn)刪除結(jié)點(diǎn)S S.1. q = p; s =

16、 p-lchild; /q為為s s的父結(jié)點(diǎn)的父結(jié)點(diǎn) while(s-rchild)q=s;s=s-rchild；2. p-data= s-data;3. If(p=q) q-lchild = s-lchild; /p p為為s s的父結(jié)點(diǎn)，的父結(jié)點(diǎn)，s s的左子結(jié)點(diǎn)成為的左子結(jié)點(diǎn)成為p p的左子結(jié)點(diǎn)的左子結(jié)點(diǎn) else q-rchild = s-lchild; delete s; 二叉查找樹性能分析 在二叉排序樹上查找其關(guān)鍵字等于給定值的結(jié)點(diǎn)的過程，是從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑上比較關(guān)鍵字過程，所以，和給定值比較的關(guān)鍵字個(gè)數(shù)等于路徑長度li加1(或結(jié)點(diǎn)所在層次數(shù))；比較次數(shù)為2li+1; 與給定

17、值比較的關(guān)鍵字個(gè)數(shù)不超過樹的深度。 同一個(gè)關(guān)鍵字集合的二叉查找樹有很多，樹的深度與樹的形態(tài)有關(guān)。 含有n個(gè)結(jié)點(diǎn)的二叉排序樹的平均查找長度和樹的形態(tài)有關(guān)。由關(guān)鍵字序列(45,24,53,12,37,93)構(gòu)成 深度為深度為3 3由關(guān)鍵字序列(12,24,37,45,53,93)構(gòu)成深度為深度為6 6成功查找等同于順序查找成功查找等同于順序查找假定每個(gè)結(jié)點(diǎn)的查找概率相同，則成功查找的平均查找長度假定每個(gè)結(jié)點(diǎn)的查找概率相同，則成功查找的平均查找長度：ASL(a)succ =(1+3+3+5+5+5)/6=22/6ASL(b) succ=(1+3+5+7+9+11)/6=36/645241237539

18、3(a)122437455393(b)退化的二叉查找樹擴(kuò)充的二叉查找樹452412375393圈稱為內(nèi)部結(jié)點(diǎn)，表示關(guān)鍵字集合的圈稱為內(nèi)部結(jié)點(diǎn)，表示關(guān)鍵字集合的一個(gè)值，對應(yīng)查找成功；一個(gè)值，對應(yīng)查找成功；方框?yàn)橥獠拷Y(jié)點(diǎn)，表示不屬于關(guān)鍵字方框?yàn)橥獠拷Y(jié)點(diǎn)，表示不屬于關(guān)鍵字集的值，對應(yīng)查找失敗集的值，對應(yīng)查找失敗;外部結(jié)點(diǎn)數(shù)等于內(nèi)部結(jié)點(diǎn)數(shù)加一；外部結(jié)點(diǎn)數(shù)等于內(nèi)部結(jié)點(diǎn)數(shù)加一；假定每個(gè)內(nèi)部結(jié)點(diǎn)的查找概率相同，則成功查找的平均查找假定每個(gè)內(nèi)部結(jié)點(diǎn)的查找概率相同，則成功查找的平均查找長度長度：ASLsucc =(1+3+3+5+5+5)/6=22/6假定查找每個(gè)外部結(jié)點(diǎn)的概率相同，則平均查找長度假定查找每個(gè)外

19、部結(jié)點(diǎn)的概率相同，則平均查找長度：ASLunsuc = (6+6+6+6+4+6+6)/7= 40/7二叉查找樹的查找效率與樹的形態(tài)有關(guān)；二叉查找樹的查找效率與樹的形態(tài)有關(guān)； 如果二叉樹是如果二叉樹是“線性的線性的”，則效率與順序查，則效率與順序查找相當(dāng)；找相當(dāng)； 如果二叉查找樹的形態(tài)與折半查找的判定樹如果二叉查找樹的形態(tài)與折半查找的判定樹相同，則平均查找長度是相同，則平均查找長度是O(log n);平衡二叉樹平衡二叉樹（Balanced Binary Trees）又稱AVL: 它或者是一棵空樹， 或者是具有下列性質(zhì)的二叉樹： 它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對

20、值不超過1。二叉樹上結(jié)點(diǎn)的平衡因子BF(Balance Factor)定義為該結(jié)點(diǎn)的左子樹的深度減去它的右子樹的深度.一顆二叉樹是平衡的當(dāng)且僅當(dāng)每個(gè)結(jié)點(diǎn)的平衡因子的絕對值不大于1。一棵有n 個(gè)結(jié)點(diǎn)的平衡二叉搜索樹，其高度可保持在O(log2n)，平均搜索長度也可保持在O(log2n)。1100-110-10102-10100-10-20010在根結(jié)點(diǎn)失去平衡右子樹不平衡平衡二叉查找樹的構(gòu)造設(shè)關(guān)鍵字序列為(13，24，37，90，53) 013-113024-213-124037013024037-224-2370131900532413-237-153090-124013053037090調(diào)整

21、，調(diào)整，左旋轉(zhuǎn)左旋轉(zhuǎn)調(diào)整，調(diào)整，右旋轉(zhuǎn)右旋轉(zhuǎn)調(diào)整，調(diào)整，左旋轉(zhuǎn)左旋轉(zhuǎn)左旋轉(zhuǎn) 結(jié)點(diǎn)A是插入后失去平衡的最高層結(jié)點(diǎn)，插入后A的右子樹的右子樹偏高，則進(jìn)行左旋轉(zhuǎn)。(b)右子樹的右子樹偏高右子樹的右子樹偏高h(yuǎn)hh+1BACEDhhhACEBD(a) 插入到插入到C的右子樹的右子樹hhh+1CEABD(c)左旋轉(zhuǎn)左旋轉(zhuǎn) 右旋轉(zhuǎn) 結(jié)點(diǎn)A是插入后失去平衡的最高層結(jié)點(diǎn)，插入后A的左子樹的左子樹偏高，則進(jìn)行右旋轉(zhuǎn)。hhhACEBDhh+1BACEDhhh+1CEABDh(a) 插入到插入到B的左子樹的左子樹 (b)左子樹的左子樹偏高左子樹的左子樹偏高 (c)右旋轉(zhuǎn)右旋轉(zhuǎn) 插入后右子樹的左子樹偏高先右旋轉(zhuǎn)左旋轉(zhuǎn)插

22、入后左子樹的右子樹偏高右旋轉(zhuǎn)先左旋轉(zhuǎn)16163163773167311731616119371693711269161118183163167391826117261611997161471126269113151831816731171491615112626149AVL樹的插入Status insertAVL(BSTree &T, ElemType e, Boolean &taller)/T指向AVL樹的根。若T中不存在關(guān)鍵字為e.key的紀(jì)錄，/則插入e, 并返回1，并進(jìn)行平衡處理；否則，返回0。/taller表示插入后樹的高度是否增加。if (!T) /插入新結(jié)點(diǎn)，樹的

23、高度增加 (BSTree)malloc(sizeof(BSTNode); T-data=e; T-lchild=T-rchild=NULL; T-bf = EH; taller=TRUE; else typedef struct BSTNode ElemType data; int bf; /平衡因子平衡因子 struct BSTNode *lchild, *rchild; /左右孩子指針左右孩子指針 BSTNode, *BSTree ;if (e.key=T-data.key) /不插入 taller = FALSE; return 0; if (e.key data.key) /插入T的左

24、子樹 if (!insertAVL(T-lchild, e, taller) return 0; / 未插入 if (taller) /插入后高度增加, 檢查是否失去平衡 switch(T-bf) case LH: /插入前左子樹較高，插入后左子樹偏高，失去平衡 LeftBalance(T); taller = FALSE; break; case EH: /插入后左子樹較高T-bf = LH; taller = TRUE; break; case RH: /插入前右子樹較高，插入后等高，未失去平衡T-bf = EH; taller = FALSE; break; else /右子樹插入; r

25、eturn 1; void LeftBalance (BSTree &T) /T的左子樹偏高，對所指的二叉樹做左平衡旋轉(zhuǎn)， /最后T指向新的根結(jié)點(diǎn) lc = T-lchild; / lc指向T的左子樹 switch (lc-bf) /檢查左子樹的平衡度 case LH: /左子樹的左子樹偏高，右旋轉(zhuǎn) T-bf = lc -bf = EH; R_Rotate(T); break; case RH: /插入左子樹的右子樹上，左子樹的右子樹偏高 LeftRightRotate(T); 旋轉(zhuǎn)的實(shí)現(xiàn)void R_Rotate(BSTNode &p)/ 對以*p為根的二叉查找樹/右旋轉(zhuǎn)，

26、p指向新的 根結(jié)點(diǎn) lc = p -lchild; p-lchild = lc-rchild; lc-rchild = p; p = lc; hh+1BACEhhhh+1CEABDplcDpvoid LeftRightBalance(BSTree &T)/對T指向的結(jié)點(diǎn)為根的子樹做左右雙旋轉(zhuǎn)，算法結(jié)束時(shí)T指向新的根結(jié)點(diǎn) lc = T - lchild; rd=lc-rchild;Tlcrdswitch (rd-bf) /修改平衡因子修改平衡因子 case LH: T-bf = RH; lc-bf = EH; case EH: T-bf = EH; lc-bf = EH; case RH

27、: T-bf = EH; lc-bf = LH; rd-bf = EH; L_Rotate(T-lchild); R_Rotate(T);AVL樹的性能 設(shè)在新結(jié)點(diǎn)插入前AVL樹的高度為h，結(jié)點(diǎn)個(gè)數(shù)為 n，則平均查找的時(shí)間是O(h)。對于AVL樹來說，h是多大？ 設(shè)Nh 是高度為h 的AVL樹的最小結(jié)點(diǎn)數(shù)。根的一棵子樹的高度為h-1，另一棵子樹的高度為h-2，這兩棵子樹也是高度平衡的。因此有 N0 = 0 (空樹) N1 = 1 (僅有根結(jié)點(diǎn)) Nh = Nh-1 + Nh-2 +1 , h 1 可以證明，對于 h 0，有 Nh = Fh+2 -1 成立 Fibonacci數(shù)滿足公式251,+

28、=51其中hhF n個(gè)結(jié)點(diǎn)的個(gè)結(jié)點(diǎn)的AVL樹的最大高度為樹的最大高度為21+5=-)(lognhAVL樹查找時(shí)間復(fù)雜度樹查找時(shí)間復(fù)雜度 O(log n)多級索引結(jié)構(gòu) 當(dāng)數(shù)據(jù)對象個(gè)數(shù) n 很大，或者數(shù)據(jù)量很大，由于內(nèi)存容量的限制，數(shù)據(jù)對象不能全部存儲在內(nèi)存，這時(shí)可采用索引方法來實(shí)現(xiàn)存儲和搜索。 稠密索引：一個(gè)索引項(xiàng)對應(yīng)數(shù)據(jù)表中一個(gè)對象的索引結(jié)構(gòu)。數(shù)據(jù)表可以是無序的。稱為索引非順序結(jié)構(gòu)。 稀疏索引：當(dāng)對象在外存中有序存放或者分塊有序時(shí)，可以把所有 n 個(gè)對象分為 b 個(gè)子表(塊)存放，一個(gè)索引項(xiàng)對應(yīng)數(shù)據(jù)表中一個(gè)子表。索引項(xiàng)記錄了子表中最大關(guān)鍵碼以及該子表在數(shù)據(jù)區(qū)中的起始位置。稱為索引順序結(jié)構(gòu)。 對

29、索引順序結(jié)構(gòu)進(jìn)行查找時(shí)，可分為兩級查找： 有序索引表上的查找； 子表的查找 當(dāng)數(shù)據(jù)對象數(shù)目特別大，索引表本身也很大，在內(nèi)存中放不下，需要分批多次讀取外存才能把索引表搜索一遍。 在此情況下，可以建立索引的索引，稱為二級索引。二級索引可以常駐內(nèi)存，二級索引中一個(gè)索引項(xiàng)對應(yīng)一個(gè)索引塊，登記該索引塊的最大關(guān)鍵碼及該索引塊的存儲地址 如果二級索引在內(nèi)存中也放不下，需要分為許多塊多次從外存讀入?？梢越⒍壦饕乃饕凶鋈壦饕?。這時(shí)，訪問外存次數(shù)等于讀入索引次數(shù)再加上1次讀取對象m路搜索樹 這種多級索引結(jié)構(gòu)形成一種 m 叉樹。樹中每一個(gè)分支結(jié)點(diǎn)表示一個(gè)索引塊，它最多存放 m 個(gè)索引項(xiàng)，每個(gè)索引項(xiàng)分別給

30、出各子樹結(jié)點(diǎn) (低一級索引塊) 的最大關(guān)鍵碼和結(jié)點(diǎn)地址 樹的葉結(jié)點(diǎn)中各索引項(xiàng)給出在數(shù)據(jù)表中存放的對象的關(guān)鍵碼和存放地址。這種m叉樹用來作為多級索引，就是m路搜索樹。 m路搜索樹可能是靜態(tài)索引結(jié)構(gòu)，即結(jié)構(gòu)在初始創(chuàng)建，數(shù)據(jù)裝入時(shí)就已經(jīng)定型；也可能是動態(tài)索引結(jié)構(gòu)，即在整個(gè)系統(tǒng)運(yùn)行期間，樹的結(jié)構(gòu)隨數(shù)據(jù)的增刪及時(shí)調(diào)整，以保持最佳的搜索效率。下圖所示為一棵B-樹351391271111181991645347378432FFFFFFFFFFFFB-樹 B-樹是一種平衡的多路查找樹。 一棵m階的B-樹或者空，或者是滿足下列性質(zhì)的m階樹： 樹中每個(gè)結(jié)點(diǎn)至多有m棵子樹； 若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少有兩棵子樹；

31、 除根之外的所有非終端結(jié)點(diǎn)至少有m/2棵子樹； 所有的非終端結(jié)點(diǎn)中包含下列信息數(shù)據(jù) (n, A0, K1, A1, K2, A2, , Kn, An） n為關(guān)鍵字個(gè)數(shù)，Ki為關(guān)鍵字，KiKi+1, Ai為指向子樹的指針，且子樹上的關(guān)鍵字均小于Ki+1，Aj所指子樹上的關(guān)鍵字均大于Kj 所有的葉子結(jié)點(diǎn)都出現(xiàn)在同一層次上，并且不帶信息(可以看作是外部結(jié)點(diǎn)或查找失敗的結(jié)點(diǎn))。 下圖所示為一棵4階的B-樹351391271111181991645347378432FFFFFFFFFFFF每個(gè)節(jié)點(diǎn)上至少有每個(gè)節(jié)點(diǎn)上至少有1 1個(gè)關(guān)鍵字，最多個(gè)關(guān)鍵字，最多有有3 3個(gè)關(guān)鍵字個(gè)關(guān)鍵字B-樹的搜索 從根結(jié)點(diǎn)開

32、始，在結(jié)點(diǎn)內(nèi)搜索；可使用順序或折半查找； 如果結(jié)點(diǎn)內(nèi)查找成功，則結(jié)束；否則，確定結(jié)點(diǎn)所在的子樹； 沿指針到子結(jié)點(diǎn)上查找，直至查找成功或者到達(dá)葉結(jié)點(diǎn)，查找失敗。351391271111181991645347378432FFFFFFFFFFFF查找47查找23B-樹查找分析 B-樹主要用于文件的索引，查找效率主要取決于讀取外存的次數(shù)；（內(nèi)存存取速度以微秒（百萬分之一秒）為單位，外存存取速度以毫秒（千分之一秒）為單位）； 查找過程中，每次需要將一個(gè)結(jié)點(diǎn)從外存讀到內(nèi)存，然后結(jié)點(diǎn)內(nèi)的查找在內(nèi)存進(jìn)行； 查找過程中讀取結(jié)點(diǎn)次數(shù)與樹的高度成正比； 估算N個(gè)關(guān)鍵字B-樹的最高層數(shù)或者h(yuǎn)層m階B-樹最少結(jié)點(diǎn)數(shù)：

33、 第一層最少1個(gè)結(jié)點(diǎn)，第二層最少2個(gè)，第三層最少2m/2, ,h+1層至少2m/2h-1, h+1層葉結(jié)點(diǎn)數(shù)是關(guān)鍵字?jǐn)?shù)N加1，故N+1 2m/2h-1， 示例：若B-樹的階數(shù) m = 199，關(guān)鍵碼總數(shù) N = 1999999，則B-樹的高度 h 不超過 log100 1000000 +1= 4 如果提高B-樹的階數(shù) m，可以減少樹的高度，從而減少讀入結(jié)點(diǎn)的次數(shù)，因而可減少讀磁盤的次數(shù)另一方面, 外存的讀取是按頁或塊進(jìn)行的，m不可太大,否則 ,或者一個(gè)結(jié)點(diǎn)不可一次讀入，或者內(nèi)存放不下一個(gè)結(jié)點(diǎn) m值的選擇：應(yīng)使得在B-樹中找到關(guān)鍵碼 x 的時(shí)間總量達(dá)到最小。 這個(gè)時(shí)間由兩部分組成： 從磁盤中讀入

34、結(jié)點(diǎn)所用時(shí)間 在結(jié)點(diǎn)中搜索 x 所用時(shí)間B-樹的插入 B-樹是從空樹起，逐個(gè)插入關(guān)鍵碼而生成的 插入在某個(gè)葉結(jié)點(diǎn)開始。如果在關(guān)鍵碼插入后結(jié)點(diǎn)中的關(guān)鍵碼個(gè)數(shù)超出了上界 m-1，則結(jié)點(diǎn)需要“分裂”，否則可以直接插入 例如，從空樹開始建立3階B-樹插入139分裂，分裂，中間關(guān)中間關(guān)鍵字移鍵字移到父結(jié)到父結(jié)點(diǎn)點(diǎn)插入插入36后結(jié)點(diǎn)分裂，中間后結(jié)點(diǎn)分裂，中間關(guān)鍵字移到父結(jié)點(diǎn)關(guān)鍵字移到父結(jié)點(diǎn)插入插入101后結(jié)點(diǎn)分裂，中后結(jié)點(diǎn)分裂，中間關(guān)鍵字移到父結(jié)點(diǎn)間關(guān)鍵字移到父結(jié)點(diǎn)父結(jié)點(diǎn)進(jìn)一步父結(jié)點(diǎn)進(jìn)一步分裂，中間關(guān)分裂，中間關(guān)鍵字移到父結(jié)鍵字移到父結(jié)點(diǎn)，成為新的點(diǎn)，成為新的根節(jié)點(diǎn)根節(jié)點(diǎn) 實(shí)現(xiàn)結(jié)點(diǎn)“分裂”的原則是： 設(shè)結(jié)

35、點(diǎn) p 中已經(jīng)有 m-1 個(gè)關(guān)鍵碼，當(dāng)再插入一個(gè)關(guān)鍵碼后結(jié)點(diǎn)中的狀態(tài)為 ( m, P0, K1, P1, K2, P2, , Km, Pm) 其中 Ki Ki+1, 1 i 52*627, 因此,產(chǎn)生沖突 不可避免 因此，在建造哈希表的任務(wù)是 要設(shè)計(jì)一個(gè)“好”的哈希函數(shù); 要設(shè)計(jì)一種處理沖突的方法。散列函數(shù)的構(gòu)造構(gòu)造散列函數(shù)時(shí)的幾點(diǎn)要求： 散列函數(shù)的定義域必須包括需要存儲的全部關(guān) 鍵碼，如果散列表允許有 m 個(gè)地址時(shí), 其值域 必須在 0 到 m-1 之間。 散列函數(shù)計(jì)算出來的地址應(yīng)能均勻分布在整個(gè) 地址空間中：若 key 是從關(guān)鍵碼集合中隨機(jī)抽 取的一個(gè)關(guān)鍵碼，散列函數(shù)應(yīng)能以同等概率取 0

36、到 m-1 中的每一個(gè)值。 散列函數(shù)應(yīng)是簡單的，能在較短的時(shí)間內(nèi)計(jì)算 出結(jié)果。常用散列函數(shù)構(gòu)造方法1直接定址法 取關(guān)鍵字或關(guān)鍵字的某個(gè)線性函數(shù)值為散列地址。即： H(key)=akey+b 其中a和b為常數(shù)。 例如, 有一組關(guān)鍵碼如下： 383001, 383002, ,散列函數(shù)為這類散列函數(shù)是一對一的映射，一般不會產(chǎn)生沖突。但是，它要求散列地址空間的大小與關(guān)鍵碼集合的大小相同數(shù)字分析法:假設(shè)關(guān)鍵字是以r為基的數(shù)(如：以10為基的十進(jìn)制數(shù))，若哈希表中可能出現(xiàn)的關(guān)鍵宇都是事先知道的，則可取關(guān)鍵字的若干數(shù)位組成哈希地址。例如，關(guān)鍵字集合為例如，關(guān)鍵字集合為 04383002 04383078 0

37、4383079 04345002 04379085 04328059 04379066 83個(gè)關(guān)鍵字，可以取關(guān)鍵字的個(gè)關(guān)鍵字，可以取關(guān)鍵字的兩位表示其散列地址：前六位兩位表示其散列地址：前六位中每一位都集中，最后兩位最中每一位都集中，最后兩位最均勻故取最后兩位作為散列均勻故取最后兩位作為散列地址：地址：h(04383001) =1, . h(043830079) =79, h(04379085) =85, h(04328059) = 59, h(04379066) = 66 3除留余數(shù)法 取關(guān)鍵字被某個(gè)不大于哈希表表長m的數(shù)p除后所得余數(shù)為哈希地址。即 H(key)=key MOD p pm

38、這是一種最簡單，也最常用的構(gòu)造哈希函數(shù)的方法。 使用除留余數(shù)法時(shí)，對p的選擇很重要。若p選的不好，容易產(chǎn)生同義詞。參見P256. 由經(jīng)驗(yàn)得知：一般情況下可以選p為小于基本區(qū)域長度的最大質(zhì)數(shù)。 除余法常用于其它方法的最后一步，以使函數(shù)值均勻分布于0與m-1之間。4平方取中法 取關(guān)鍵字平方后的中間r位為哈希地址。 通常在選定哈希函數(shù)時(shí)不一定能知道關(guān)鍵字的全部情況，取其中哪幾位也不一定合適，而一個(gè)數(shù)平方后的中間幾位數(shù)和數(shù)的每一位都相關(guān)，由此使隨機(jī)分布的關(guān)鍵字得到的哈希地址也是隨機(jī)的。 例：Key = 1234567891234567892 = 15241578750190521h(123456789

39、) = 8750 處理沖突的方法 “處理沖突”：當(dāng)一個(gè)關(guān)鍵字的哈希地址不空時(shí)，為該關(guān)鍵字的記錄找到另一個(gè)“空”的哈希地址。 解決沖突的基本方法：開地址法和拉鏈法. 開地址法:當(dāng)沖突發(fā)生時(shí)，用某種方法在基本區(qū)域內(nèi)形成一個(gè)探查地址序列，沿著這個(gè)探查地址序列一個(gè)個(gè)單元查找，直至找到一個(gè)開放的地址（空地址），然后在開放地址插入 根據(jù)探查序列的不同生成方法，分為線性探查法，平方探查法和隨機(jī)探查法等。 線性探查法: 當(dāng)沖突發(fā)生時(shí), 從下一個(gè)地址順序查找,直至找到一個(gè)空地址. 散列表應(yīng)想象成循環(huán)的. 因此, 探查序列為 Hi=(H(key)+di) mod m , di=1，2，3，m-1， 故稱線性探測.

40、 例：關(guān)鍵碼為 Burke, Ekers, Broad, Blum, Attlee, Alton, Hecht, Ederly。散列函數(shù)是：取其第一個(gè)字母在字母表中的（相對于）位置。 H(x) = ord (x) - ord (A) Attlee Burke Broad Blum EkersAlton Ederly Hecht 處理沖突的開地址法當(dāng)表中當(dāng)表中i，i+1，i+2位置上已填有記錄時(shí)，下一個(gè)哈希地位置上已填有記錄時(shí)，下一個(gè)哈希地址為址為i、i+1，i+2和和i+3的記錄都將填入的記錄都將填入i+3的位置，這種在的位置，這種在處理沖突過程中發(fā)生的兩個(gè)非同義詞的探查序列匯集到一處理沖突過

41、程中發(fā)生的兩個(gè)非同義詞的探查序列匯集到一起的現(xiàn)象稱作起的現(xiàn)象稱作“二次聚集二次聚集”二次聚集將增加查找長度二次聚集將增加查找長度a與c間的空隙單元填入后a,b和c的同義詞均填入d平方探查法 避免二次聚集的方法是使探查的步長具有一定的隨機(jī)性； 平方探查法：沖突發(fā)生時(shí)，探查序列為 Hi=(H(key)+di)MOD m， di=12，22，k2，(km/2) 平方探查可以減少二次聚集。 問題：能否探查到開地址呢？如果m是素?cái)?shù)，則平方探查序列能探查一半的地址。 使用公式1+3+(2i-1) = i2, 探查序列的平方運(yùn)算可用加法代替。 偽隨機(jī)數(shù)法：由一個(gè)偽隨機(jī)數(shù)生成器生成探查步長序列di 。條件是由

42、同一個(gè)seed生成相同的偽隨機(jī)數(shù)序列。 再哈希法：沖突發(fā)生時(shí)，使用另一個(gè)哈希函數(shù)計(jì)算下一個(gè)探查地址。其他開地址法散列表的刪除-開地址法若把關(guān)鍵碼為Broad的表項(xiàng)真正刪除，把它所在位置的info域置為Empty，以后在搜索關(guān)鍵碼為Blum和Alton的表項(xiàng)時(shí)就查不下去，從而會錯(cuò)誤地判斷表中沒有關(guān)鍵碼為Blum和Alton的表項(xiàng)。若想刪除一個(gè)表項(xiàng)，只能給它做一個(gè)刪除標(biāo)記deleted，進(jìn)行邏輯刪除，不能把它真正刪去Attlee Burke Broad Blum EkersAlton Ederly Hecht 處理沖突的方法-鏈地址法鏈地址法：將所有關(guān)鍵字為同義詞的記錄存儲在同一線性鏈表中。011

43、427795568198420102311例：已知一組關(guān)鍵字為(19，14，23，01，68，20，84，27，55，11，10，79)，則按哈希函數(shù)H(key)=key MOD13和鏈地址法處理沖突構(gòu)造所得的哈希表如右圖0123456789101112處理沖突的方法-鏈地址法鏈地址法的表示 假設(shè)哈希函數(shù)產(chǎn)生的哈希地址在區(qū)間0，m-1上，則設(shè)立一個(gè)指針型向量 Chain ChainHashm； typedef struct Node KeyType key; struct Node *next; *Chain; 每個(gè)分量的初始狀態(tài)都是空指針。 凡哈希地址為i的記錄都插入到頭指針為ChainHa

44、shi的鏈表中。 鏈地址法的特點(diǎn)： 當(dāng)計(jì)錄很大時(shí)，可以節(jié)省空間；因?yàn)檫B續(xù)的哈希表需要分配額外空間以避免沖突。 在這里，表的長度可以小于關(guān)鍵字個(gè)數(shù)。 處理沖突簡單，沒有二次聚集； 刪除簡單； 如果紀(jì)錄較小，則指針占用空間不可忽視。如，指針，關(guān)鍵字各占一個(gè)字，則n個(gè)關(guān)鍵字，長度為n的哈希表需要3n個(gè)字的存儲空間。哈希表的查找及其分析 在哈希表上進(jìn)行查找的過程和哈希造表的過程基本一致。 給定K值，根據(jù)造表哈希函數(shù)h求得哈希地址h(K)， 若表中h(K)上沒有記錄，則查找不成功；否則 比較關(guān)鍵字，若和給定值相等，則查找成功；否則 根據(jù)造表時(shí)設(shè)定的處理沖突的方法找“下一地址”，直至表中相應(yīng)位置記錄的關(guān)鍵字等于給定值K或者此位置為“空” 為止。 查找過程是計(jì)算地址并且和相應(yīng)位置關(guān)鍵字比較的過程，把計(jì)算地址和比較關(guān)鍵字成為一次探查。用平均探查次數(shù)衡量哈希表的時(shí)間復(fù)雜度。 查找過程中的探查次數(shù)取決于下列三個(gè)因素：哈希函數(shù)，處理沖突的方法和哈希表的裝填因子，即哈希表的裝滿程度： 表中填入的記錄數(shù) 哈希表的長度對于開地址法， ，對于鏈地址法， 沒有上界。 假定哈希函數(shù)是均勻的，對于相同的沖突處理方法，平均