算法與數(shù)據(jù)結(jié)構(gòu)：第九章 查找表（集合）

1、數(shù)據(jù)結(jié)構(gòu)-第九章 查找1第九章 查找表（集合） 查找運(yùn)算是計(jì)算機(jī)中最常用的操作之一，計(jì)算機(jī)大約有40%的運(yùn)算與查找有關(guān)。被查找的數(shù)據(jù)對(duì)象邏輯結(jié)構(gòu)可認(rèn)為是集合，選取不同的存儲(chǔ)結(jié)構(gòu)，查找以及其它操作的效率也會(huì)有所不同。9.1 概念和術(shù)語(yǔ)9.2 靜態(tài)查找表9.3 動(dòng)態(tài)查找表9.4 哈希表本章學(xué)習(xí)要點(diǎn)、習(xí)題與上機(jī)作業(yè)數(shù)據(jù)結(jié)構(gòu)-第九章 查找29.1 相關(guān)概念和術(shù)語(yǔ)術(shù)語(yǔ)查找表 同一類(lèi)型的記錄(數(shù)據(jù)元素)的集合。 數(shù)據(jù)元素之間存在著松散的關(guān)系。為了提高查找的效率，可在元素之間人為地附加某種確定的關(guān)系。關(guān)鍵字 記錄(數(shù)據(jù)元素)中的某個(gè)數(shù)據(jù)項(xiàng)的值。 主關(guān)鍵字 該關(guān)鍵字可以唯一地標(biāo)識(shí)一個(gè)記錄。 次關(guān)鍵字 該關(guān)鍵字

2、不能唯一標(biāo)識(shí)一個(gè)記錄。查找 指定某個(gè)值，在查找表中確定是否存在一個(gè)記錄，該記錄的關(guān)鍵字等于給定值。靜態(tài)查找表 對(duì)查找表的查找僅是以查詢(xún)?yōu)槟康?，不改?dòng)查找表中的數(shù)據(jù)。動(dòng)態(tài)查找表 在查找的過(guò)程中同時(shí)插入不存在的記錄，或刪除某個(gè)已存在的記錄。查找成功 查找表中存在滿(mǎn)足查找條件的記錄。查找不成功 查找表中不存在滿(mǎn)足查找條件的記錄。數(shù)據(jù)項(xiàng)1 數(shù)據(jù)項(xiàng)2 記錄（數(shù)據(jù)元素）數(shù)據(jù)結(jié)構(gòu)-第九章 查找3內(nèi)查找 整個(gè)查找過(guò)程都在內(nèi)存中進(jìn)行。外查找 在查找過(guò)程中需要訪問(wèn)外存。平均查找長(zhǎng)度ASL（ Average Search Length ） 查找方法時(shí)效的度量 為確定記錄在查找表中的位置，需將關(guān)鍵字和給定值比較次數(shù)的

3、期望值。查找成功時(shí)的ASL計(jì)算方法： n：記錄的個(gè)數(shù) pi：查找第i個(gè)記錄的概率， ( 不特別聲明時(shí)認(rèn)為等概率 pi =1/n ) ci：找到第i個(gè)記錄所需的比較次數(shù)本章約定：關(guān)鍵字的類(lèi)型為整型typedef int KeyType;typedef struct KeyType key;ElemType;數(shù)據(jù)結(jié)構(gòu)-第九章 查找4查找表上的基本操作1）查找表初始化： InitTable(&T)2）銷(xiāo)毀查找表： DestroyTable(&T)3）檢索某個(gè)特定的數(shù)據(jù)元素： SearchTable(T, key)4）插入一個(gè)數(shù)據(jù)元素： InsertTable(&T, e);5）刪去某個(gè)數(shù)據(jù)元素： D

4、eleteTable(&T, key);6）遍歷： TraverseTable(T, Visit();數(shù)據(jù)結(jié)構(gòu)-第九章 查找59.2 靜態(tài)查找表9.2.1 順序表的查找9.2.2 有序表的查找9.2.3 靜態(tài)樹(shù)表的查找9.2.4 索引順序表的查找數(shù)據(jù)穩(wěn)定，變動(dòng)很少的查找表數(shù)據(jù)結(jié)構(gòu)-第九章 查找69.2.1 順序表的查找 靜態(tài)查找表以順序表表示 0 1 2 n ST.elem0.n a1 a2 an算法描述typedef struct ElemType *elem;int length;SSTable;keyint Search_Seq1( SSTable ST, KeyType key) i=

5、1； while (i=ST.length & ST.elemi.key!=key) i+;if (i=ST.length) return i; else return 0;/Search_Seq1int Search_Seq2( SSTable ST, KeyType key) ST.elem0.key=key; for (i=ST.length; ST.elemi.key!=key; i-)；return i;/Search_Seq2數(shù)據(jù)結(jié)構(gòu)-第九章 查找7程序設(shè)計(jì)技巧 設(shè)置監(jiān)視哨，查找時(shí)每一步不必檢測(cè)位置是否越界，提高算法效率。性能分析空間：一個(gè)輔助空間。時(shí)間： 1) 查找成功時(shí)的平均查

6、找長(zhǎng)度 設(shè)表中各記錄查找概率相等 ASLs(n)= =(1+2+ . +n)/n =(n+1)/2 2)查找不成功時(shí)的平均查找長(zhǎng)度 ASLf =n+1算法特點(diǎn)算法簡(jiǎn)單，對(duì)表中元素排列順序無(wú)任何要求n很大時(shí)查找效率較低改進(jìn)措施：非等概率查找時(shí)，可將查找概率高的記錄盡量排在表前部。逐個(gè)查找的方法也可用于線性鏈表表示的靜態(tài)查找表思考：若采用線性鏈表存儲(chǔ)靜態(tài)查找表，為避免每一步的越界檢測(cè)，用什么形式的鏈表為好：?jiǎn)捂湵?、單循環(huán)鏈表、雙循環(huán)鏈表？數(shù)據(jù)結(jié)構(gòu)-第九章 查找89.2.2 有序表的查找 滿(mǎn)足 ri.key ri+1.key, 1 i n 仍可用順序查找，但在找不到時(shí)不需比較到表尾，只需比較到比給定

7、值大的記錄就可終止。折半(對(duì)半/二分)查找法 0 1 2 3 4 5 6 7 8 9 10 11 05 13 19 21 37 56 64 75 80 88 92 low mid high =(low+high)/2 K=21 l h m K=85 l h m 1 11 6 1 11 6 1 5 3 7 11 9 4 5 4 10 11 10 10 9數(shù)據(jù)結(jié)構(gòu)-第九章 查找9算法描述int Search_Bin ( SSTable ST, keytype key) low= 1; high = ST.length; / 置區(qū)間初值 while ( low = high ) mid = ( lo

8、w+high )/2; if (key=ST.elemmid.key) return mid; / 找到待查元素 else if ( key50)key，將其右孩子作為當(dāng)前結(jié)點(diǎn)，轉(zhuǎn)1）； 若Kdata. key ) ) return ( T ) ; else if ( LT( key , T -data. key ) ) return (SearchBST ( T - lchild, key ); else return (SearchBST ( T - rchild, key ); /SearchBST P228-9.5（a）452453122890 Tkey=28 查找成功key=32 查

9、找失敗null數(shù)據(jù)結(jié)構(gòu)-第九章 查找22452453122890T32fStatus SearchBST(BiTree T, KeyType key, BiTree f, BiTree &p)/f指向當(dāng)前結(jié)點(diǎn)的雙親,初始調(diào)用值為NULL。/查找成功，p指向該結(jié)點(diǎn)，并返回TRUE；/查找失敗，p指向查找路徑上的最后一個(gè)結(jié)點(diǎn)，并返回FALSE if (!T) p=f; return FALSE; else if EQ(key, T-data.key) p=T; return TRUE; else if LT(key, T-data.key) return SearchBST(T-lchild, k

10、ey, T, p ); else return SearchBST(T-rchild, key, T, p);/SearchBST P228-9.5(b)Status InsertBST (BiTree &T,ElemType e) if (!SearchBST(T, e.key, NULL, P) s=(BiTree)malloc(sizeof(BiTNode); s-data=e; s-lchild=s-rchild=NULL; if (!T) T=s; else if LT(e.key, p-data.key) p-lchild = s; else p-rchild = s; retur

11、n TRUE; else return FALSE /InsertBST P228-9.62) 插入數(shù)據(jù)結(jié)構(gòu)-第九章 查找233) 生成 從空樹(shù)出發(fā)，反復(fù)調(diào)用插入操作InsertBST即可。例 10， 18， 3， 8， 12， 2， 7， 31010181018310183810183812101838122101838122710183812273數(shù)據(jù)結(jié)構(gòu)-第九章 查找244) 刪 除 53 20 90 10 50 86 95 4 12 41 52 88 91 30 45 87 89 92 39(1)(2)(2)(3)被刪除結(jié)點(diǎn)為*p的不同情況分析： p是葉子結(jié)點(diǎn)：修改其雙親指針即可 p只

12、有左孩子：用p的左子樹(shù)代替以p為根的子樹(shù) p只有右孩子：用p的右子樹(shù)代替以p為根的子樹(shù)p有兩個(gè)孩子：找到p的中序后繼(或前趨)結(jié)點(diǎn)q； q的數(shù)據(jù)復(fù)制給p； 刪除只有右孩子(或左孩子)/無(wú)孩子的q。數(shù)據(jù)結(jié)構(gòu)-第九章 查找254. 性能分析給定樹(shù)的形態(tài)，等概率查找成功時(shí)的ASL=ci /n最差(單支樹(shù))：(n+1)/2最好(類(lèi)似折半查找的判定樹(shù))：log2(n+1)-1隨機(jī)：1+4log2n關(guān)鍵字有序出現(xiàn)時(shí)，構(gòu)造出“退化”的二叉排序樹(shù)，樹(shù)深為n，各種操作代價(jià)O(n)。避免方法：采用平衡二叉樹(shù)40245512371224374055數(shù)據(jù)結(jié)構(gòu)-第九章 查找269.3.2 平衡二叉樹(shù)(AVL樹(shù))1.平衡

13、二叉樹(shù)的定義 或者是空樹(shù)，或者是滿(mǎn)足如下性質(zhì)的二叉排序樹(shù)： 1)它的左、右子樹(shù)的高度之差的絕對(duì)值不超過(guò)1； 2)其左右子樹(shù)本身又各是一棵平衡二叉樹(shù)。二叉樹(shù)上結(jié)點(diǎn)的平衡因子： 該結(jié)點(diǎn)的左子樹(shù)高度減去右子樹(shù)的高度。平衡二叉樹(shù)不一定是理想的最矮狀態(tài)。平衡二叉樹(shù)39 048 136 -116 045 176 -163 0非平衡二叉樹(shù)36 -214 064 255 -156 0數(shù)據(jù)結(jié)構(gòu)-第九章 查找272. 定理一個(gè)具有n個(gè)結(jié)點(diǎn)的平衡二叉樹(shù)的高度h為 log2(n+1) hloga(sqrt(5)*(n+1)-2 a=(1sqrt(5)/2 結(jié)論：最壞情況下，AVL樹(shù)的高度約為1.44log2n，而完全

14、平衡的二叉樹(shù)高度約為log2n，因此AVL樹(shù)是接近最優(yōu)的，其平均查找長(zhǎng)度與log2n 同數(shù)量級(jí)。3. 結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu) lchild bf key otherinfo rchild lchild：左孩子指針 rchild：右孩子指針 bf：平衡因子 key：記錄的關(guān)鍵字datatypedef struct KeyType key; ElemTypetypedef struct BSTNode ElemType data; int bf; struct BSTNode *lchile,*rchild;BSTNode, * BSTree;數(shù)據(jù)結(jié)構(gòu)-第九章 查找284. 在平衡二叉樹(shù)上的操作1) 查找

15、 查找方法同二叉排序樹(shù)。2) 插入 例 平衡二叉樹(shù)的生成過(guò)程 15 -1 15 -2 25 0 15 0 25 0 25 -1 15 0 35 0 35 0 25 -1 25 -2 25 -1 15 0 35 -1 15 0 35 -2 15 0 65 0 90 0 90 1 35 0 90 0 65 0在插入過(guò)程中采用平衡旋轉(zhuǎn)技術(shù)數(shù)據(jù)結(jié)構(gòu)-第九章 查找29調(diào)整范圍的確定 插入結(jié)點(diǎn)后，找到離插入結(jié)點(diǎn)最近且平衡因子絕對(duì)值超過(guò)1的祖先結(jié)點(diǎn)，則以該結(jié)點(diǎn)為根的子樹(shù)將是可能不平衡的最小子樹(shù)，可將重新平衡的范圍局限于這棵子樹(shù)。調(diào)整的規(guī)律 設(shè)失去平衡的最小子樹(shù)的根結(jié)點(diǎn)指針為aLL型平衡旋轉(zhuǎn)單向右旋（一次順時(shí)

16、針旋轉(zhuǎn)） A 1 A 2 B 0 B 0 B 1 A 0BLBRARARBRBL插入的結(jié)點(diǎn)ARBRBLa數(shù)據(jù)結(jié)構(gòu)-第九章 查找30RR型平衡旋轉(zhuǎn)單向左旋（一次逆時(shí)針旋轉(zhuǎn)） a A -1 A -2 B 0 B 0 B -1 A 0LR型平衡旋轉(zhuǎn)一次逆時(shí)針旋轉(zhuǎn)+一次順時(shí)針旋轉(zhuǎn) A 1 A 2 C 0 B 0 B -1 B 0 A -1 C 0 C 1BLBRALALBRBLBRBLALBLCLCRARBLCLCRARaBLCLARCR-110hhh-1h-1h-1h-1h-1h-1hhhhhhhhhhhhh數(shù)據(jù)結(jié)構(gòu)-第九章 查找31RL型平衡旋轉(zhuǎn)一次順時(shí)針旋轉(zhuǎn)+一次逆時(shí)針旋轉(zhuǎn) A -1 A -2

17、C 0 B 0 B 1 A 0 B -1 C 0 C 1例 3)刪除 （思路同插入）將刪除結(jié)點(diǎn)q轉(zhuǎn)化為q最多有一個(gè)孩子的情形，即若q有兩個(gè)孩子，則以其中序前驅(qū)/后繼結(jié)點(diǎn)r取代它，刪除r；若樹(shù)的平衡性被破壞，利用單一/雙重旋轉(zhuǎn)恢復(fù)。ALCRCLBRALCRCLBRALCLBRCRh-1hhhhhhh-1h-1h-1h-1h-1-110數(shù)據(jù)結(jié)構(gòu)-第九章 查找32以下表順序建立平衡二叉排序樹(shù)，并求在等概率情況下查找成功的平均查找長(zhǎng)度。（90,60,20,50,40,30,10,110,100,70,120,80）解 90 6020LL 60 20 90 50 40RL 60 40 9020 50 3

18、0LL 40 20 6010 30 50 90 110 100RL 40 20 6010 30 50 100 90 110 70數(shù)據(jù)結(jié)構(gòu)-第九章 查找33RL 40 20 9010 30 60 100 50 70 110 120RR 40 20 9010 30 60 110 50 70 100 120 80RL 60 40 90 20 50 70 11010 30 80 100 120ASL=(11+22+43+54)/12 =37/12數(shù)據(jù)結(jié)構(gòu)-第九章 查找349.3.3 B-樹(shù) B-樹(shù)是一種平衡的多路查找樹(shù)?？蓱?yīng)用于文件系統(tǒng)。 海量數(shù)據(jù)存放在外存中，不可能一次全部調(diào)入內(nèi)存。因此，要多次 訪

19、問(wèn)外存。但硬盤(pán)的驅(qū)動(dòng)受機(jī)械運(yùn)動(dòng)的制約，速度慢。所以，主要矛盾變?yōu)闇p少訪外次數(shù)。 1970 年由 R bayer 和 E macreight 提出用B_ 樹(shù)作為索引組織文件。提高訪問(wèn)速度、減少時(shí)間開(kāi)銷(xiāo)。內(nèi)存數(shù)據(jù)結(jié)構(gòu)-第九章 查找35例: 用二叉樹(shù)組織文件，當(dāng)文件的記錄個(gè)數(shù)為 100000時(shí)，要找到給定關(guān)鍵字的記錄，需訪問(wèn)外存17次（log2100,000）。502510751535609020304055708095索引文件數(shù)據(jù)文件文件頭(可常駐內(nèi)存)文件訪問(wèn)示意圖：索引文件、數(shù)據(jù)文件存在盤(pán)上數(shù)據(jù)結(jié)構(gòu)-第九章 查找361. 定義 一棵 m 階B - 樹(shù)，或?yàn)榭諛?shù)，或?yàn)闈M(mǎn)足下列特性的 m 叉樹(shù)：

20、1) 樹(shù)中每個(gè)結(jié)點(diǎn)最多有 m 棵子樹(shù)； 2) 若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則最少有兩棵子樹(shù)； 3) 除根之外的所有非終端結(jié)點(diǎn)最少有 m / 2 棵子樹(shù)； 4) 所有非終端結(jié)點(diǎn)包含 （n,A0,K1,A1,K2,Kn,An）信息數(shù)據(jù)；其中n為結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)，Ai為指向子樹(shù)的指針，Ki為關(guān)鍵字。 5) 所有葉子結(jié)點(diǎn)在同一層上，且不帶信息。 B-樹(shù)是一種 平衡 的 多路 查找數(shù)據(jù)結(jié)構(gòu)-第九章 查找37 結(jié)點(diǎn)結(jié)構(gòu) (n, A0, K1, A1, K2, A2,., Kn, An) 例 一棵4階B-樹(shù) (m=4 ) 1 40 非葉根則2m棵子樹(shù) 1 20 3 49 58 72 1 10 1 25 2 41

21、43 1 51 1 65 1 99 m/2 m棵子樹(shù)葉FFFFFFFFFFFFF數(shù)據(jù)結(jié)構(gòu)-第九章 查找382. B-樹(shù)的用途 當(dāng)內(nèi)存中不可能容納所有數(shù)據(jù)記錄時(shí)，在磁盤(pán)等直接存取設(shè)備上組織動(dòng)態(tài)的查找表。B-樹(shù)的根結(jié)點(diǎn)可以始終置于內(nèi)存中；其余非葉結(jié)點(diǎn)放置在外存上，每一結(jié)點(diǎn)可作為一個(gè)讀取單位（頁(yè)/塊）選取較大的階次m，降低樹(shù)的高度，減少外存訪問(wèn)次數(shù)B-樹(shù)的信息組織方法每個(gè)記錄的其它信息與關(guān)鍵字一起存儲(chǔ)。查到關(guān)鍵字即可獲取記錄的完整信息。將記錄的外存地址(頁(yè)指針)與關(guān)鍵字一起存儲(chǔ)。查到關(guān)鍵字時(shí)，還需根據(jù)該頁(yè)指針訪問(wèn)外存。數(shù)據(jù)結(jié)構(gòu)-第九章 查找393. B-樹(shù)的存儲(chǔ)定義B樹(shù)節(jié)點(diǎn)定義#define m 3

22、 /B-樹(shù)的階typedef struct BTNode int keynum; /關(guān)鍵字個(gè)數(shù) struct BTNode *parent; /雙親指針 KeyType keym+1; /0號(hào)未用 struct BTNode *ptrm+1; Record *recptrm+1; BTNode, *BTree;查找結(jié)果描述typedef struct BTNode *pt; int i; /1.m int tag; /1成功，0失敗Result;數(shù)據(jù)結(jié)構(gòu)-第九章 查找404. B-樹(shù)上的基本運(yùn)算1)查找算法思想 設(shè)查找時(shí)給定值為K，從根結(jié)點(diǎn)開(kāi)始(a)在當(dāng)前結(jié)點(diǎn)*p中順序或者折半查找 若找到某個(gè)

23、i，滿(mǎn)足keyi=K，則查找成功，返回p、i、1 否則，確定滿(mǎn)足keyiKptri)，將此結(jié)點(diǎn)作為當(dāng)前結(jié)點(diǎn)，轉(zhuǎn)(a)例 K=43（查找成功） K=60（查找失?。?shù)據(jù)結(jié)構(gòu)-第九章 查找41Result SearchBTree(BTree T, KeyType K) p = T; q = NULL; found = FALSE; i =0; /q指向p的雙親 while (p & ! found) i = Search(p, K); /在p-key1.keynum中找i, / 使得keyi=K0 & p-keyi=K ) found = TRUE; else q = p; p = p-ptri;

24、 if (found) return (p,i,1); else return (q,i,0);/SearchBTree算法描述422) 插入算法思想 設(shè)插入的關(guān)鍵字為K(a)在B-樹(shù)中查找K，若查找到，則返回 否則查找失敗，查找操作定位于某個(gè)最低層的非葉結(jié)點(diǎn)(q,i)，在相應(yīng)的位置插入偶對(duì)K, (b)keynum加1，若當(dāng)前結(jié)點(diǎn)未溢出(keynumparent)， 將偶對(duì)(keym/2, q1)插入該父結(jié)點(diǎn)， 以該父結(jié)點(diǎn)為當(dāng)前結(jié)點(diǎn)q，轉(zhuǎn)(b)數(shù)據(jù)結(jié)構(gòu)-第九章 查找43例1 m=4的B-樹(shù) 插入K=47 1 40 1 20 3 49 58 72 110 1 25 3 414347 151 16

25、5 199例2 插入K=45 1 40 1 20 3 49 58 72 110 1 25 4 41434547 151 165 199 (41) 43 (45 47)qqm/2 數(shù)據(jù)結(jié)構(gòu)-第九章 查找44 1 40 (43) 49 (58 72) 1 20 4 43 49 58 72 110 1 25 1 41 2 4547 151 165 199 2 40 49 1 20 1 43 2 58 72 110 1 25 1 41 2 4547 151 165 199 若由底向上至根結(jié)點(diǎn)仍需分裂時(shí)，需要構(gòu)造新的根結(jié)點(diǎn)，B-樹(shù)會(huì)增加一層。q1q1qq數(shù)據(jù)結(jié)構(gòu)-第九章 查找453) 生成算法思想 從空

26、樹(shù)起，逐個(gè)插入關(guān)鍵字得到。4) 刪 除算法思想 設(shè)刪除的關(guān)鍵字為K(a)在B-樹(shù)中查找K，若未查找到，則返回 否則 查找成功，查找操作定位于某個(gè)結(jié)點(diǎn)q， 且q-keyi為K(b)若q結(jié)點(diǎn)不是最下層的非葉結(jié)點(diǎn)，則查找q-ptri所指子樹(shù)的最小關(guān)鍵字x，用x替換keyi，使問(wèn)題轉(zhuǎn)換為刪除最下層的非葉結(jié)點(diǎn)上的關(guān)鍵字?jǐn)?shù)據(jù)結(jié)構(gòu)-第九章 查找46 刪除K=49 2 40 49 1 20 1 43 2 58 72 110 1 25 1 41 2 4547 151 165 199(c) 刪除h層上的關(guān)鍵字，分三種情況處理：其所屬結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)m/2-1：簡(jiǎn)單刪除 m=4，K=70 1 50 1 50 145

27、 27080 145 180ptri子樹(shù)的最左下關(guān)鍵字(49的后繼)數(shù)據(jù)結(jié)構(gòu)-第九章 查找47其所屬結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)=m/2-1， 其左/右兄弟結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)m/2-1 m=4，K=10 2 13 30 2 15 30 110 21517 135 113 117 135 其所屬結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)=m/2-1， 其左/右兄弟結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)=m/2-1 1100 1120 2160190 2110120 2160190向兄弟“借”2 110 1501 150“合并”數(shù)據(jù)結(jié)構(gòu)-第九章 查找48 “連接”時(shí)出現(xiàn)的較為復(fù)雜情況的處理： m=4，刪除K=80 1 100 1 100 1 50 1 150 1

28、 150 125 180 1120 1170 22550 1120 1170 2 100 150 22550 1120 1170“合并”“合并”數(shù)據(jù)結(jié)構(gòu)-第九章 查找495. B-樹(shù)的高度及性能分析定理 對(duì)于任一棵具有n(n0)個(gè)關(guān)鍵字的m (m2)階B-樹(shù)，其樹(shù)高h(yuǎn)至多為logt(n+1)/2)+1。其中t=m/2決定B-樹(shù)上操作的時(shí)間開(kāi)銷(xiāo)的兩個(gè)主要因素外存的訪問(wèn)次數(shù)O(h) O(logtn)CPU的在結(jié)點(diǎn)上的比較定位時(shí)間O(hm)/ O(h*log2m)前者起主導(dǎo)作用作為外存上的動(dòng)態(tài)查找表，m越大，則B-樹(shù)的高度越小，時(shí)間性能越好；僅在內(nèi)存中使用的B-樹(shù)必須取較小的m，通常取最小值m=3數(shù)

29、據(jù)結(jié)構(gòu)-第九章 查找509.3.4 B+樹(shù) B+樹(shù)是一種B-樹(shù)的變形樹(shù)。廣泛應(yīng)用在文件系統(tǒng)中，特別是數(shù)據(jù)庫(kù)的VSAM文件系統(tǒng)中（IBM）。1. m階B+ 樹(shù)與 B- 樹(shù)的不同之處1)有 n 棵子樹(shù)的結(jié)點(diǎn)中有 n 個(gè)關(guān)鍵字；2)非葉結(jié)點(diǎn)可以看成是索引部分 索引集Ai ：第i個(gè)子結(jié)點(diǎn)的指針Ki ：第i個(gè)子結(jié)點(diǎn)的最大（或最?。╆P(guān)鍵字3)所有葉子結(jié)點(diǎn)中包含了全部關(guān)鍵字的信息及指向這些關(guān)鍵字記錄的指針，且葉子結(jié)點(diǎn)以關(guān)鍵字大小自小至大順序鏈接；數(shù)據(jù)集數(shù)據(jù)結(jié)構(gòu)-第九章 查找51結(jié)點(diǎn)結(jié)構(gòu)非葉結(jié)點(diǎn) ( A1, K1, .,Ai, Ki, ., An,Kn) 索引集Ai ：第i個(gè)子結(jié)點(diǎn)的指針Ki ：第i個(gè)子結(jié)點(diǎn)的

30、最大（或最?。╆P(guān)鍵字葉結(jié)點(diǎn) 全部關(guān)鍵字及指向關(guān)鍵字記錄的指針 數(shù)據(jù)集 2 15 334 40 47 58 672 79 853 90 96 1052 85 1323 33 67 852 105 1322 114 132示例：4階B+樹(shù)rootsqt指向關(guān)鍵字記錄的指針?biāo)饕瘮?shù)據(jù)集數(shù)據(jù)結(jié)構(gòu)-第九章 查找522. B+樹(shù)上的基本運(yùn)算1)查找方式1：從根結(jié)點(diǎn)開(kāi)始，利用索引集結(jié)構(gòu)，向下查找直到葉子結(jié)點(diǎn)方式2：從最小關(guān)鍵字開(kāi)始，沿葉結(jié)點(diǎn)數(shù)據(jù)集的鏈結(jié)構(gòu)順序查找2)插入 僅在葉子結(jié)點(diǎn)上進(jìn)行，關(guān)鍵字個(gè)數(shù)大于m則分裂3)刪除 也僅在葉子結(jié)點(diǎn)上進(jìn)行，關(guān)鍵字個(gè)數(shù)小于m/2時(shí)，需進(jìn)行合并數(shù)據(jù)結(jié)構(gòu)-第九章 查找539.

31、3.5 鍵樹(shù)(數(shù)字查找樹(shù)/字符樹(shù))1. 概念 將關(guān)鍵字分解為字符的多叉樹(shù)，多叉樹(shù)中的每個(gè)結(jié)點(diǎn)只代表關(guān)鍵字中的一個(gè)字符，葉結(jié)點(diǎn)用于表示字符串的結(jié)束符(如$)，并含有指向該關(guān)鍵字記錄的指針。從根到葉子的路徑上所有的結(jié)點(diǎn)對(duì)應(yīng)的字符連接起來(lái)就代表一個(gè)關(guān)鍵字。約定鍵樹(shù)是有序樹(shù)結(jié)束符小于任何字符例1 關(guān)鍵字集合beg,bell,big,log,long,nilblneiog$ll$gng$il$g$指向關(guān)鍵字記錄的指針葉結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)-第九章 查找54例2 6，71，78，99，235，243，467 2 4 6 7 9 0 2 4 3 4 6 $ 1 8 9 0 7 9 3 4 6 5 3 7 $ $ $

32、 6 1 8 9 5 3 7 $ $ $ $ $ $ $ $ $ $ 按純字符串考慮 按整形數(shù)考慮2. 鍵樹(shù)的存儲(chǔ)結(jié)構(gòu)及其操作1)雙鏈樹(shù) 以樹(shù)的孩子兄弟鏈表表示symbol ptr next字符 兄弟指針結(jié)點(diǎn)為leaf型：指向記錄的指針結(jié)點(diǎn)為nonleaf型：指向孩子指針數(shù)據(jù)結(jié)構(gòu)-第九章 查找55查找 設(shè)給定值為K1.m 成功查找的情況 K=LIU$ 從p=dst-ptr出發(fā) C L W Y Z 沿next域順序查找，直到某個(gè) 結(jié)點(diǎn)的symbol值等于K1； A I O 再沿該結(jié)點(diǎn)的ptr域進(jìn)入下一層 結(jié)點(diǎn)，查找K2； $ U 直至KM比較在葉結(jié)點(diǎn)處終止。 ASL=h(1+d)/2 d鍵樹(shù)中結(jié)

33、點(diǎn)的最大度 $不成功查找的情況 K=LIANGdstUA 終止 插入位置數(shù)據(jù)結(jié)構(gòu)-第九章 查找56插入 查找不成功時(shí)， 插入 $ A U N $ G $刪除 確認(rèn)查找成功后， 刪除 C L W Y Z A I O $ U $注意：結(jié)點(diǎn)只有一個(gè)孩子或是葉結(jié)點(diǎn)時(shí)才可刪除。數(shù)據(jù)結(jié)構(gòu)-第九章 查找572) Trie樹(shù)以多重鏈表表示 若從鍵樹(shù)中某個(gè)結(jié)點(diǎn)開(kāi)始到葉子結(jié)點(diǎn)的路徑上的每個(gè)結(jié)點(diǎn)中都只有一個(gè)孩子，則將該路徑上的所有結(jié)點(diǎn)壓縮成一個(gè)“葉子結(jié)點(diǎn)”，且葉子結(jié)點(diǎn)中存儲(chǔ)有指向記錄的指針。 分支結(jié)點(diǎn)：num有用指針的數(shù)量 ptr0.m指針數(shù)組葉子結(jié)點(diǎn)：key關(guān)鍵字 recptr指向?qū)?yīng)記錄的指針例 降低Trie樹(shù)

34、深度的一種途徑 選擇一種合適的分割方式。如前后交叉分割/取樣。 $ a b c l n z3 e i2 g l2begbellbignil o1 g n2loglong數(shù)據(jù)結(jié)構(gòu)-第九章 查找589.4 哈希表9.4.1 概述9.4.2 哈希函數(shù)的基本構(gòu)造方法9.4.3 處理沖突的常用方法9.4.4 哈希表的建立、查找及其ASL分析數(shù)據(jù)結(jié)構(gòu)-第九章 查找599.4.1 概述之前各種查找表的結(jié)構(gòu)特點(diǎn)： 記錄在表中的位置和它的關(guān)鍵字之間不存在一個(gè)確定的關(guān)系 查找的過(guò)程為給定值依次和集合中各個(gè)關(guān)鍵字進(jìn)行比較，查找的效率取決于和給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)。 不同的表示方法，其差別僅在于：關(guān)鍵字和給定值進(jìn)

35、行比較的順序不同。數(shù)據(jù)結(jié)構(gòu)-第九章 查找60哈希表的基本思想 在記錄的存儲(chǔ)地址和它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系；這樣，理想狀態(tài)不經(jīng)過(guò)比較，一次存取就能得到所查元素。術(shù)語(yǔ) 哈希表 一個(gè)有限的連續(xù)的地址空間，用以容納按哈希地址存儲(chǔ)的記錄。 哈希函數(shù) 記錄的存儲(chǔ)位置與它的關(guān)鍵字之間存在的一種對(duì)應(yīng)關(guān)系。 Loc(ri)=H(keyi) 沖突 對(duì)于keyikeyj， i j， 出現(xiàn)的H(keyi) = H(keyj)的現(xiàn)象。 數(shù)據(jù)結(jié)構(gòu)-第九章 查找61 同義詞 在同一地址出現(xiàn)沖突的各關(guān)鍵字。 哈希(散列)地址 根據(jù)設(shè)定的哈希函數(shù)H(key)和處理沖突的方法確定的記錄的存儲(chǔ)位置。 裝填因子 表中填入

36、的記錄數(shù)n和哈希表表長(zhǎng) m之比。 =n/m設(shè)計(jì)哈希表的過(guò)程 1)明確哈希表的地址空間范圍。即確定哈希函數(shù)的值域。 2)選擇合理的哈希函數(shù)。該函數(shù)要保證所有可能的記錄的哈希地址均在指定的值域內(nèi)，并使沖突的可能性盡量小。 3)設(shè)定處理沖突的方法。哈希表bb+(m-1)L數(shù)據(jù)結(jié)構(gòu)-第九章 查找629.4.2 哈希函數(shù)的基本構(gòu)造方法 構(gòu)造原則： 算法簡(jiǎn)單，運(yùn)算量??； 均勻分布，減少?zèng)_突。 若是非數(shù)字關(guān)鍵字，則需先對(duì)其進(jìn)行數(shù)字化處理。直接定址法 H(key)=a *key + b a、b為常數(shù) 特點(diǎn)：計(jì)算簡(jiǎn)單，沖突最少。此法僅適合于：地址集合的大小 = = 關(guān)鍵字集合的大小數(shù)字分析法 取關(guān)鍵字的若干數(shù)位

37、作為哈希地址。 假設(shè)關(guān)鍵字集合中的每個(gè)關(guān)鍵字都是由 s 位數(shù)字組成 (u1, u2, , us)，分析關(guān)鍵字集中的全體， 并從中提取分布均勻的若干位或它們的組合作為地址。此方法僅適合于：能預(yù)先估計(jì)出全體關(guān)鍵字的每一位上各種數(shù)字出現(xiàn)的頻度。數(shù)據(jù)結(jié)構(gòu)-第九章 查找63平方取中法 取關(guān)鍵字平方后的中間幾位作為哈希地址求“關(guān)鍵字的平方值” 的目的是“擴(kuò)大差別” ，同時(shí)平方值的中間各位又能受到整個(gè)關(guān)鍵字中各位的影響。此方法適合于: 關(guān)鍵字中的每一位都有某些數(shù)字重復(fù)出現(xiàn)頻度很高的現(xiàn)象。折疊法將關(guān)鍵字分割成位數(shù)相同的幾部分(最后一部分的位數(shù)可以不同)，然后取這幾個(gè)部分的疊加和(舍去進(jìn)位)作為哈希地址。此方法

38、適合于: 關(guān)鍵字的數(shù)字位數(shù)特別多。例：key = 110108380428895 895 428 380 108+) 110 895 824 380 801+) 11019213010移位疊加間界疊加數(shù)據(jù)結(jié)構(gòu)-第九章 查找64除留余數(shù)法 H(key) = key MOD p (pm) m: 哈希表的表長(zhǎng)； p: 最好為素?cái)?shù) ,更有利于“散列”為什么要對(duì) p 加限制？給定一組關(guān)鍵字為: 12, 39, 18, 24, 33, 21，若取 p=9, 則對(duì)應(yīng)的哈希函數(shù)值將為: 3, 3, 0, 6, 6, 3可見(jiàn)，若 p 中含質(zhì)因子 3, 則所有含質(zhì)因子 3 的關(guān)鍵字均映射到“3 的倍數(shù)”的地址上，

39、從而增加了“沖突”的可能。隨機(jī)數(shù)法 H(key) = random(key)此方法適合于:關(guān)鍵字長(zhǎng)度不等時(shí)的情況。數(shù)據(jù)結(jié)構(gòu)-第九章 查找659.4.3 處理沖突的常用方法1. 開(kāi)放定址法 (空缺編址法) Hi = ( H(key)+di ) MOD m 0 H(key) m-1 i=1,2, ., k (km-1) m:哈希表的表長(zhǎng)； di:增量序列 1)線性探測(cè)再散列 di= 1,2, ., m-1 缺陷：有聚集(堆積)現(xiàn)象非同義詞地址沖突。 2)二次探測(cè)再散列 di= 12, -12, 22, -22, 32,.,k2 k m/2 缺陷：不易探查到整個(gè)散列空間。 3)偽隨機(jī)探測(cè)再散列 di

40、 = 偽隨機(jī)數(shù)序列為產(chǎn)生沖突的地址尋找下一個(gè)哈希地址例數(shù)據(jù)結(jié)構(gòu)-第九章 查找66 4) 雙重散列函數(shù)探查法 di= i*h1(key) 0 i m- 1 要求：h1(key)的值與m互素。 m為素?cái)?shù)時(shí)， h1(key)可取1到m-1之間的任何數(shù)， 建議h1(key)=key mod (m-2) +1 m為2的方冪時(shí)， h1(key)可取1到m-1之間的任 何奇數(shù) 開(kāi)放定址法不宜執(zhí)行刪除操作2. 再哈希法 Hi = RHi(key) i=1,2, . , k RHi為不同的散列函數(shù)-1 -1-1 -1數(shù)據(jù)結(jié)構(gòu)-第九章 查找67例如: 關(guān)鍵字集合 19, 01, 23, 14, 55, 68, 1

41、1, 82, 36 設(shè)定哈希函數(shù) H(key) = key MOD 11 ( 表長(zhǎng)=11 )1901231455681901231468若采用線性探測(cè)再散列處理沖突若采用二次探測(cè)再散列處理沖突118236551182361 1 2 1 3 6 2 5 1數(shù)據(jù)結(jié)構(gòu)-第九章 查找683. 鏈地址法 為每個(gè)哈希地址建立一個(gè)單鏈表，存儲(chǔ)所有具有同義詞的記錄。 b b+L fire to b+(m-1)L seeks 沖突處理簡(jiǎn)單，無(wú)堆積現(xiàn)象，平均查找長(zhǎng)度較短；較適合于事先無(wú)法確定表長(zhǎng)的情況；可取1，當(dāng)結(jié)點(diǎn)信息規(guī)模較大時(shí)，節(jié)省空間刪除結(jié)點(diǎn)的操作易于實(shí)現(xiàn)4. 建立公共溢出區(qū)一個(gè)基本表 溢出表數(shù)據(jù)結(jié)構(gòu)-第九

42、章 查找699.4.4 哈希表的建立、查找及其ASL分析例 有一組關(guān)鍵字序列(38、59、125、168、216、719、455、20)，用函數(shù) H(key) = key MOD 10 將其按順序散列到哈希表 HT(0:9) 中，分別用三種方法解決沖突：線性再探測(cè)法、鏈地址法、公共溢出區(qū)法，畫(huà)出這三種方法建立的散列表，并分別求在等概率情況下查找成功和不成功的平均查找長(zhǎng)度。1)線性再探測(cè)法 0123456789 3859125216168719455201681687197194554552020ASL成功 = = = 281681+1+1+3+1+3+3+3ASL不成功 = = = 4.61046104+3+2+1+1+9+8+7+6+5數(shù)據(jù)結(jié)構(gòu)