數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)集-第九章查找

數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容一、教學(xué)內(nèi)容：1、 線性表的查找；2、 樹表查找；3、 哈希表查找。二、教學(xué)要求：1、熟練掌握順序表和有序表的查找算法及其性能分析方法；2、熟練掌握二叉排序樹的構(gòu)造和查找算法及其性能分析方法；3、理解AVL樹的維護(hù)平衡方法；4、 理解B_樹、B+的特點(diǎn)、查找及構(gòu)造方法；5、 熟練掌握哈希函數(shù)的構(gòu)造及解決沖突的方法。第9章查找9.1基本概念9.2靜態(tài)查找表9.3動態(tài)查找表9.4哈希表第9章查找教材第8、11和12章省略，因《操作系統(tǒng)》課程會涉及。9.1基本概念——若表中存在特定元素，稱查找成功，應(yīng)輸出該記錄；——否則，稱查找不成功（也應(yīng)輸出失敗標(biāo)志或失敗位置）查找表查找查找成功查找不成功靜態(tài)查找動態(tài)查找關(guān)鍵字主關(guān)鍵字次關(guān)鍵字——由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合?！樵?Searching)特定元素是否在表中。——只查找，不改變集合內(nèi)的數(shù)據(jù)元素?！炔檎遥指淖儯ㄔ鰷p）集合內(nèi)的數(shù)據(jù)元素?！涗浿心硞€數(shù)據(jù)項(xiàng)的值，可用來識別一個記錄

(預(yù)先確定的記錄的某種標(biāo)志)

——可以唯一標(biāo)識一個記錄的關(guān)鍵字例如“學(xué)號”例如“女”是一種數(shù)據(jù)結(jié)構(gòu)——識別若干記錄的關(guān)鍵字（2）對查找表常用的操作有哪些？查詢某個“特定的”數(shù)據(jù)元素是否在表中；查詢某個“特定的”數(shù)據(jù)元素的各種屬性；在查找表中插入一元素；從查找表中刪除一元素。

（3)有哪些查找方法？

查找方法取決于表中數(shù)據(jù)的排列方式;討論：（1）查找的過程是怎樣的？

給定一個值K，在含有n個記錄的文件中進(jìn)行搜索，尋找一個關(guān)鍵字值等于K的記錄，如找到則輸出該記錄，否則輸出查找不成功的信息。例如查字典針對靜態(tài)查找表和動態(tài)查找表的查找方法也有所不同?！疤囟ǖ摹?關(guān)鍵字明確：查找的過程就是將給定的K值與文件中各記錄的關(guān)鍵字項(xiàng)進(jìn)行比較的過程。所以用比較次數(shù)的平均值來評估算法的優(yōu)劣。稱為平均查找長度（ASL：averagesearchlength）。其中：n是文件記錄個數(shù)；Pi是查找第i個記錄的查找概率（通常取等概率,即Pi=1/n）;Ci是找到第i個記錄時所經(jīng)歷的比較次數(shù)。統(tǒng)計意義上的數(shù)學(xué)期望值物理意義：假設(shè)每一元素被查找的概率相同，則查找每一元素所需的比較次數(shù)之總和再取平均，即為ASL。顯然，ASL值越小，時間效率越高。（4）如何評估查找方法的優(yōu)劣？針對靜態(tài)查找表的查找算法主要有：

9.2靜態(tài)查找表靜態(tài)查找表的抽象數(shù)據(jù)類型參見教材P216。一、順序查找（線性查找）二、折半查找（二分或?qū)Ψ植檎遥┤?、靜態(tài)樹表的查找四、分塊查找（索引順序查找）一、順序查找（Linearsearch，又稱線性查找）（1）順序表的機(jī)內(nèi)存儲結(jié)構(gòu)：typedefstruct{

ElemType*elem;

//表基址，0號單元留空。表容量為全部元素

intlength;

//表長，即表中數(shù)據(jù)元素個數(shù)}SSTable;順序查找：即用逐一比較的辦法順序查找關(guān)鍵字，這顯然是最直接的辦法。

對順序結(jié)構(gòu)如何線性查找？見下頁之例或教材P216；對單鏈表結(jié)構(gòu)如何線性查找？函數(shù)雖未給出，但也很容易編寫；只要知道頭指針head就可以“順藤摸瓜”；對非線性樹結(jié)構(gòu)如何順序查找?可借助各種遍歷操作！順序查找演示（2）算法的實(shí)現(xiàn)：技巧：把待查關(guān)鍵字key存入表頭或表尾（俗稱“哨兵”），這樣可以加快執(zhí)行速度。例：若將待查找的特定值key存入順序表的首部（如0號單元），則順序查找的實(shí)現(xiàn)方案為：從后向前逐個比較！intSearch_Seq(SSTableST,KeyTypekey){

//在順序表ST中，查找關(guān)鍵字與key相同的元素；若成功，返回其位置信息，否則返回0

ST.elem[0].key=key;

//設(shè)立哨兵，可免去查找過程中每一步都要檢測是否查找完畢。當(dāng)n>1000時，查找時間將減少一半。

for(i=ST.length;ST.elem[i].key!=key;--i);

//不要用for(i=n;i>0;--i)或for(i=1;i<=n;i++)

returni;

//若到達(dá)0號單元才結(jié)束循環(huán)，說明不成功，返回0值(i=0)。成功時則返回找到的那個元素的位置i。}//Search_Seq——返回特殊標(biāo)志，例如返回空記錄或空指針。前例中設(shè)立了“哨兵”，就是將關(guān)鍵字送入末地址ST.elem[0].key使之結(jié)束并返回i=0。討論②

查找效率怎樣計算？——用平均查找長度ASL衡量。討論①

查不到怎么辦？討論③如何計算ASL？分析：查找第1個元素所需的比較次數(shù)為1；查找第2個元素所需的比較次數(shù)為2；……查找第n個元素所需的比較次數(shù)為n；總計全部比較次數(shù)為：1＋2＋…＋n=(1+n)n/2未考慮查找不成功的情況：查找哨兵所需的比較次數(shù)為n+1這是查找成功的情況若求某一個元素的平均查找次數(shù)，還應(yīng)當(dāng)除以n（等概率），即：ASL＝（1＋n）/2

，時間效率為O(n)二、折半查找（又稱二分查找或?qū)Ψ植檎遥﹥?yōu)點(diǎn)：算法簡單，且對順序結(jié)構(gòu)或鏈表結(jié)構(gòu)均適用。缺點(diǎn)：

ASL太長，時間效率太低。這是一種容易想到的查找方法。先給數(shù)據(jù)排序（例如按升序排好），形成有序表，然后再將key與正中元素相比，若key小，則縮小至右半部內(nèi)查找；再取其中值比較，每次縮小1/2的范圍，直到查找成功或失敗為止。對順序表結(jié)構(gòu)如何編程實(shí)現(xiàn)折半查找算法？

——見下頁之例，或見教材（P219）對單鏈表結(jié)構(gòu)如何折半查找？

——無法實(shí)現(xiàn)！因全部元素的定位只能從頭指針head開始對非線性(樹)結(jié)構(gòu)如何折半查找？

——可借助二叉排序樹來查找（屬動態(tài)查找表形式）。

如何改進(jìn)？討論④順序查找的特點(diǎn)：②運(yùn)算步驟：(1)low=1,high=11,mid=6，待查范圍是[1,11]；(2)若ST.elem[mid].key<key，說明key[mid+1,high]，則令：low=mid+1;重算mid＝(low+high)/2；.(3)若ST.elem[mid].key>

key，說明key[low,mid-1]，則令：high=mid–1;重算mid；(4)若ST.elem[mid].key=key，說明查找成功，元素序號=mid;結(jié)束條件：（1）查找成功：ST.elem[mid].key=key

（2）查找不成功：high≤low

（意即區(qū)間長度小于0）解：①先設(shè)定3個輔助標(biāo)志:

low,high,mid，折半查找舉例：Low指向待查元素所在區(qū)間的下界high指向待查元素所在區(qū)間的上界mid指向待查元素所在區(qū)間的中間位置

已知如下11個元素的有序表：

（0513192137566475808892）,請查找關(guān)鍵字為21

和85的數(shù)據(jù)元素。顯然有：mid=(low+high)/2二分查找演示討論①若關(guān)鍵字不在表中，怎樣得知和停止？——典型標(biāo)志是：當(dāng)查找范圍的上界≤下界時停止查找。討論②二分查找的效率（ASL）1次比較就查找成功的元素有1個（20），即中間值；2次比較就查找成功的元素有2個（21），即1/4處（或3/4）處；3次比較就查找成功的元素有4個（22），即1/8處（或3/8）處…4次比較就查找成功的元素有8個（23），即1/16處（或3/16）處………則第m次比較時查找成功的元素會有（2m-1）個；為方便起見，假設(shè)表中全部n個元素＝2m-1個，此時就不討論第m次比較后還有剩余元素的情況了。全部比較總次數(shù)為1×20＋2×21＋3×22＋4×23…＋m×2m—1

＝推導(dǎo)過程平均每個數(shù)據(jù)的查找時間還要除以n，所以：（詳細(xì)推導(dǎo)過程見教材P221的附錄1）課堂練習(xí)（多項(xiàng)選擇）：Ａ．采用鏈?zhǔn)酱尜A結(jié)構(gòu) Ｂ．記錄的長度≤128Ｃ．采用順序存貯結(jié)構(gòu)Ｄ．記錄按關(guān)鍵字遞增有序√√使用折半查找算法時，要求被查文件：思考：假設(shè)在有序線性表a[20]上進(jìn)行折半查找，則平均查找長度為

。查找過程可用二叉樹描述：每個記錄用一個結(jié)點(diǎn)表示；結(jié)點(diǎn)中值為該記錄在表中位置，這個描述查找過程的二叉樹稱為判定樹。n個元素的表的折半查找的判定樹是唯一的，即：判定樹由表中元素個數(shù)決定。

找到有序表中任一記錄的過程就是：走了一條從根結(jié)點(diǎn)到與該記錄相應(yīng)的結(jié)點(diǎn)的路徑。

比較的關(guān)鍵字個數(shù)：為該結(jié)點(diǎn)在判定樹上的層次數(shù)。

查找成功時比較的關(guān)鍵字個數(shù)最多不超過樹的深度d:d=log2n+1

若所有結(jié)點(diǎn)的空指針域設(shè)置為一個指向一個方形結(jié)點(diǎn)的指針，稱方形結(jié)點(diǎn)為判定樹的外部結(jié)點(diǎn)；對應(yīng)的，圓形結(jié)點(diǎn)為內(nèi)部結(jié)點(diǎn)。

查找不成功的過程就是走了一條從根結(jié)點(diǎn)到外部結(jié)點(diǎn)的路徑。折半查找效率分析法（參見教材P220）：三、分塊查找（索引順序查找）這是一種順序查找的另一種改進(jìn)方法。先讓數(shù)據(jù)分塊有序，即分成若干子表，要求每個子表中的數(shù)值（用關(guān)鍵字更準(zhǔn)確）都比后一塊中數(shù)值?。ǖ颖韮?nèi)部未必有序）。然后將各子表中的最大關(guān)鍵字構(gòu)成一個索引表，表中還要包含每個子表的起始地址（即頭指針）。索引表最大關(guān)鍵字起始地址2212138920334244382448605874498653第1塊第2塊第3塊224886例：2248861713特點(diǎn)：塊間有序，塊內(nèi)無序查找步驟分兩步進(jìn)行：①對索引表使用折半查找法（因?yàn)樗饕硎怯行虮恚?；②確定了待查關(guān)鍵字所在的子表后，在子表內(nèi)采用順序查找法（因?yàn)楦髯颖韮?nèi)部是無序表）；查找效率：ASL=Lb+Lw對索引表查找的ASL對塊內(nèi)查找的ASLS為每塊內(nèi)部的記錄個數(shù)，n/s即塊的數(shù)目例如當(dāng)n=9，s=3時，ASLbs=3.5,而折半法為3.1,順序法為5分塊查找演示5.實(shí)現(xiàn)程序下面函數(shù)以二分法查找塊,以順序法查找分塊內(nèi)的方法,實(shí)現(xiàn)了線性表的分塊查找。其中參數(shù)a為順序存儲的線性表,idx為索引表,v為要查找的給定值,m為總塊數(shù)。

typedefstruct{intkey;intstart;intlen;}IDX;

intblk_search(a,idx,v,m)IDXidx[];inta[],v,m;{intlow=0,high=m-1,mid,i,h;while(low<=high){mid=(low+high)/2;if(v<idx[mid].key)high=mid-1;elseif(v>idx[mid].keylow=mid+1;

else

{low=mid;break;}}

if(low>=m)return(-1);i=idx[low].start;h=i+idx[low].len;while(i<h&&a[i]!=v)i++;if(a[i]!=v)i=-l;return(i);}

特點(diǎn)：一、二叉排序樹的定義二、二叉排序樹的插入與刪除三、二叉排序樹的查找分析四、平衡二叉樹五、B-樹和B+樹9.2動態(tài)查找表表結(jié)構(gòu)在查找過程中動態(tài)生成。要求：對于給定值key,若表中存在其關(guān)鍵字等于key的記錄，則查找成功返回；否則插入關(guān)鍵字等于key的記錄。典型的動態(tài)表———二叉排序樹一、二叉排序樹的定義（a）（b）練：下列2種圖形中，哪個不是二叉排序樹？----或是一棵空樹；或者是具有如下性質(zhì)的非空二叉樹：

（1）左子樹的所有結(jié)點(diǎn)均小于根的值；（2）右子樹的所有結(jié)點(diǎn)均大于根的值；（3）它的左右子樹也分別為二叉排序樹。討論：對(a)中序遍歷后的結(jié)果是什么？二、二叉排序樹的插入與刪除將數(shù)據(jù)元素構(gòu)造成二叉排序樹的優(yōu)點(diǎn)：①查找過程與順序結(jié)構(gòu)有序表中的折半查找相似，查找效率高；②中序遍歷此二叉樹，將會得到一個關(guān)鍵字的有序序列（即實(shí)現(xiàn)了排序運(yùn)算）；③如果查找不成功，能夠方便地將被查元素插入到二叉樹的葉子結(jié)點(diǎn)上，而且插入或刪除時只需修改指針而不需移動元素。注：若數(shù)據(jù)元素的輸入順序不同，則得到的二叉排序樹形態(tài)也不同！——這種既查找又插入的過程稱為動態(tài)查找。二叉排序樹既有類似于折半查找的特性，又采用了鏈表存儲，它是動態(tài)查找表的一種適宜表示。4524531290如果待查找的關(guān)鍵字序列輸入順序?yàn)椋海?4，53，45，45，12，24，90），2453451290查找成功，返回查找成功，返回討論1：二叉排序樹的插入和查找操作

則生成二叉排序樹的過程為：例：輸入待查找的關(guān)鍵字序列=（45，24，53，45，12，24，90）則生成的二叉排序樹形態(tài)不同：查找成功，返回查找成功，返回二叉排序樹的查找&插入算法如何實(shí)現(xiàn)？查找算法靜態(tài)查找算法動態(tài)查找算法（插入）二叉排序樹的靜態(tài)查找思想若二叉排序樹為空，則查找失敗，否則，先拿根結(jié)點(diǎn)值與待查值進(jìn)行比較，若相等，則查找成功，若根結(jié)點(diǎn)值大于待查值，則進(jìn)入左子樹重復(fù)此步驟，否則，進(jìn)入右子樹重復(fù)此步驟，若在查找過程中遇到二叉排序樹的葉子結(jié)點(diǎn)時，還沒有找到待查結(jié)點(diǎn)，則查找不成功。（2）二叉排序樹查找的算法實(shí)現(xiàn)1)遞歸函數(shù)

NODE*search(t,x)NODE*t;charx;{if(t==NULL)return(NULL);

else

{if(t->data==x)return(t);if(x<(t->data)return(search(t->lchild,x));

else

return(search(t->lchild,x));}}2)非遞歸函數(shù)

NODE*search(NODE*t,charx){NODE*p;

p=t;while(p!=NULL){if(p->data==x)return(p);if(x<p->data)p=p->lchild;else

p=p->rchlid;}printf(“找不到值為%x的結(jié)點(diǎn)!”,x);return(NULL);}二叉排序樹的動態(tài)查找算法查找算法：若二叉排序樹為空，則返回插入位置，否則，先拿根結(jié)點(diǎn)值與待查值進(jìn)行比較，若相等，則查找成功，若根結(jié)點(diǎn)值大于待查值，則進(jìn)入左子樹重復(fù)此步驟，否則，進(jìn)入右子樹重復(fù)此步驟。（P228算法9.5（b））插入算法：若二叉排序樹為空，則被查結(jié)點(diǎn)為新的根節(jié)點(diǎn)；否則，作為一個新的葉子結(jié)點(diǎn)插入在由查找返回的位置上。（P228算法9.6）二叉排序樹的建立對于已給定一待排序的數(shù)據(jù)序列,通常采用逐步插入結(jié)點(diǎn)的方法來構(gòu)造二叉排序樹,即只要反復(fù)調(diào)用二叉排序樹的插入算法即可，算法描述為：BiTree*Creat(intn)//建立含有n個結(jié)點(diǎn)的二叉排序樹{BiTree*BST=NULL;for(inti=1;i<=n;i++){scanf(“%d”,&x);//輸入關(guān)鍵字序列

InsertBST(BST,x);}return(BST);}二叉排序樹的生成演示二叉排序樹的刪除要刪除二叉排序樹中的p結(jié)點(diǎn)，分三種情況：p為葉子結(jié)點(diǎn)，只需修改p雙親f的指針f->lchild=NULL或f->rchild=NULLp只有左子樹或右子樹p只有左子樹，用p的左孩子代替p(1)(2)p只有右子樹，用p的右孩子代替p(3)(4)p左、右子樹均非空

沿p左子樹的根C的右子樹分支找到S，S的右子樹為空法1：令*p的左子樹為*f的左子樹，*p的右子樹為*s的右子樹；法2：令*s代替*p將S的左子樹成為S的雙親Q的右子樹，用S取代p(5)若C無右子樹，用C取代p(6)FCCLSSLQLPPRQPRFCCLSSLQLPPRQ法2:FCCLSSLQLPPRQ法1:例：請從下面的二叉排序樹中刪除結(jié)點(diǎn)P。SSLSQPLP中序遍歷：QSPLPSQPL中序遍歷：QSPL(2)SPPLQ中序遍歷：PLPSQSPLQ中序遍歷：PLSQ(1)63421815634215刪除18中序遍歷：PPRSQSPRQ中序遍歷：PRSQ(3)SPPRQ中序遍歷：QSPPRSQPR中序遍歷：QSPR(4)SQPRP6342181215刪除1263421815FPCPRCLQQLSSL中序遍歷：CLC……QLQSLSPPRFFSCPRCLQQLSL中序遍歷：CLC……QLQSLSPRF(5)FPCPRCL中序遍歷：CLCPPRFFCPRCL中序遍歷：CLCPRF(6)1036241812156342181215刪除10二叉排序樹刪除演示1)二叉排序樹上查找某關(guān)鍵字等于給定值的結(jié)點(diǎn)過程，其實(shí)就是走了一條從根到該結(jié)點(diǎn)的路徑。

比較的關(guān)鍵字次數(shù)＝此結(jié)點(diǎn)的層次數(shù);

最多的比較次數(shù)＝樹的深度（或高度），即log2n+12)一棵二叉排序樹的平均查找長度為：三、二叉排序樹的查找分析其中：ni是每層結(jié)點(diǎn)個數(shù)；

Ci是結(jié)點(diǎn)所在層次數(shù)；m為樹深。最壞情況：即插入的n個元素從一開始就有序，

——變成單支樹的形態(tài)！此時樹的深度為n;ASL=(n+1)/2

此時查找效率與順序查找情況相同。最好情況：即：與折半查找中的判定樹相同（形態(tài)比較均衡）3）對有n個關(guān)鍵字的二叉排序樹的平均查找長度:

設(shè)每種樹態(tài)出現(xiàn)概率相同，查找每個關(guān)鍵字也是等概率的。則ASL求解過程可推導(dǎo)。（詳見教材P232）樹的深度為：log2n+1；ASL=log2(n+1)–1；與折半查找相同。結(jié)論：二叉排序樹的ASL≤2（1＋1/n）lnn一般情況：（與logn同階）問題：如何提高二叉排序樹的查找效率？

盡量讓二叉樹的形狀均衡平衡二叉樹四、平衡二叉樹平衡二叉樹又稱AVL樹，它是具有如下性質(zhì)的二叉樹：為了方便起見，給每個結(jié)點(diǎn)附加一個數(shù)字，給出該結(jié)點(diǎn)左子樹與右子樹的高度差。這個數(shù)字稱為結(jié)點(diǎn)的平衡因子balance。這樣，可以得到AVL樹的其它性質(zhì)：即|左子樹深度-右子樹深度|≤1左、右子樹是平衡二叉樹；所有結(jié)點(diǎn)的左、右子樹深度之差的絕對值≤1(a)平衡樹(b)不平衡樹例：判斷下列二叉樹是否AVL樹？任一結(jié)點(diǎn)的平衡因子只能?。?1、0或

1；如果樹中任意一個結(jié)點(diǎn)的平衡因子的絕對值大于1，則這棵二叉樹就失去平衡，不再是AVL樹；對于一棵有n個結(jié)點(diǎn)的AVL樹，其高度保持在O(log2n)數(shù)量級，ASL也保持在O(log2n)量級。00011-1-120001-1如果在一棵AVL樹中插入一個新結(jié)點(diǎn)，就有可能造成失衡，此時必須重新調(diào)整樹的結(jié)構(gòu)，使之恢復(fù)平衡。我們稱調(diào)整平衡過程為平衡旋轉(zhuǎn)?，F(xiàn)分別介紹這四種平衡旋轉(zhuǎn)。平衡旋轉(zhuǎn)可以歸納為四類：

LL平衡旋轉(zhuǎn)

RR平衡旋轉(zhuǎn)

LR平衡旋轉(zhuǎn)

RL平衡旋轉(zhuǎn)若在A的左子樹的左子樹上插入結(jié)點(diǎn)，使A的平衡因子從1增加至2，需要進(jìn)行一次順時針旋轉(zhuǎn)。(以B為旋轉(zhuǎn)軸）ABCABC若在A的右子樹的右子樹上插入結(jié)點(diǎn)，使A的平衡因子從-1增加至-2，需要進(jìn)行一次逆時針旋轉(zhuǎn)。(以B為旋轉(zhuǎn)軸）2）RR平衡旋轉(zhuǎn)：ABCABC1）LL平衡旋轉(zhuǎn)：若在A的右子樹的左子樹上插入結(jié)點(diǎn)，使A的平衡因子從-1增加至-2，需要先進(jìn)行順時針旋轉(zhuǎn)，再逆時針旋轉(zhuǎn)。(以插入的結(jié)點(diǎn)C為旋轉(zhuǎn)軸）4）RL平衡旋轉(zhuǎn)：ABCABCABC若在A的左子樹的右子樹上插入結(jié)點(diǎn)，使A的平衡因子從1增加至2，需要先進(jìn)行逆時針旋轉(zhuǎn)，再順時針旋轉(zhuǎn)。(以插入的結(jié)點(diǎn)C為旋轉(zhuǎn)軸）ABCABCABC3）LR平衡旋轉(zhuǎn)：這種調(diào)整規(guī)則可以保證二叉排序樹的次序不變013037024例：請將下面序列構(gòu)成一棵平衡二叉排序樹：

（13，24，37，90，53）013037-113024-124-213需要RR平衡旋轉(zhuǎn)(繞B逆轉(zhuǎn),B為根）090-124-137053190-237需要RL平衡旋轉(zhuǎn)(繞C先順后逆）037090053037090053

五、B-樹和B+樹一、B-樹的基本概念

1.定義

一棵m階的B-樹,或?yàn)榭諛?或?yàn)闈M足下列特性的m叉樹:(l)所有的非終端結(jié)點(diǎn)的結(jié)構(gòu)如下:

其中,①k1,k2,...,kn為n個按從小到大順序排列的鍵值;②p0,pl,p2,...,pn為(n+1)個指針,用于指向該結(jié)點(diǎn)的(n+l)棵子樹,p0所指向子樹中的所有關(guān)鍵字的值均小于kl,pn所指向子樹中的所有關(guān)鍵字的值均大于kn,pi(1≤i≤n-1)所指向子樹中的所有關(guān)鍵字的值均大于ki且小于ki+1;③n(n≤m-1)為鍵值的個數(shù),即子樹個數(shù)為(n+l)。

(2)樹中每個結(jié)點(diǎn)至多有m棵子樹。

(3)除非根結(jié)點(diǎn)為葉子結(jié)點(diǎn),否則至少有兩棵子樹。

(4)除根之外的所有非終端結(jié)點(diǎn)至少有┌m/2┐棵子樹。

(5)所有葉子結(jié)點(diǎn)在同一個層次上,且不含有任何信息。

np0k1p1k2p2…kipi…knpn2.說明(1)對于非根結(jié)點(diǎn)的所有分支結(jié)點(diǎn),n的取值范圍為┌m/2┐-1≤n≤m-1。(2)對于根結(jié)點(diǎn),n的取值范圍為1≤n≤m－1。(3)對于葉子結(jié)點(diǎn),其子樹均為空樹(即沒有子結(jié)點(diǎn)),又規(guī)定不含有任何信息:所,可以把它看作不在樹中的外部結(jié)點(diǎn)。(4)B-樹的階m可以事先任意指定,一旦指定后,就固定不變。

2-3樹的含義圖9-13是一棵由10個鍵值生成的四階B_樹的示意圖,該樹共有四層,所有葉子點(diǎn)均在第四層上。1501301951251552709023540atbcdfgeh圖9-13B-樹3758085二、B-樹的查找1.查找方法

由B-樹的定義可知,在B-樹上進(jìn)行查找的過程與二叉排序樹的查找類似。根據(jù)給定的鍵值k,先在根結(jié)點(diǎn)的鍵值的集合中采用順序(當(dāng)m較小時)或二分(當(dāng)m較大時)查找方法進(jìn)行查找。若有k=ki,則查找成功,根據(jù)相應(yīng)的指針即可取得記錄:否則,若k在ki和ki+1之間,取指針pi所指的結(jié)點(diǎn),重復(fù)這個查找過程,直到在某結(jié)點(diǎn)中查找成功,或在某結(jié)點(diǎn)處出現(xiàn)pi

為空,查找失敗.例如，在圖9-13所示B_樹中查找關(guān)鍵字80和38。2.性能分析在B-樹上進(jìn)行查找需比較的結(jié)點(diǎn)數(shù)最多為B-樹的高度,B-樹的高度與B-樹的階m和鍵值總數(shù)N有關(guān),下面就來討論它們之間的關(guān)系。(1)若B-樹的高度為h+1,則h+1層(即葉結(jié)點(diǎn)所在的層)的結(jié)點(diǎn)數(shù)為N+1。因?yàn)槊總€非葉結(jié)點(diǎn)中的指針數(shù)等于其中的鍵值數(shù)加1,因此有:

結(jié)點(diǎn)總數(shù)=指針總數(shù)+1=(鍵值總數(shù)N+非葉結(jié)點(diǎn)數(shù))+l(h+1)層的結(jié)點(diǎn)數(shù)=葉結(jié)點(diǎn)數(shù)=結(jié)點(diǎn)總數(shù)－非葉結(jié)點(diǎn)數(shù)=N+1。(2)根據(jù)B-樹的定義,B-樹的第一層(即根結(jié)點(diǎn))的結(jié)點(diǎn)數(shù)至少為1個,第二層的結(jié)點(diǎn)數(shù)至少為2,第三層的結(jié)點(diǎn)數(shù)至少為2*┌m/2┐,第四層的結(jié)點(diǎn)數(shù)至少為2*(┌m/2┐)2,以此類推,第h+1層的結(jié)點(diǎn)數(shù)至少為2*(┌m/2┐)h-1。(3)綜上所述,可得到如下不等式:h≤1+log┌m/2┐(N+1)/2三、B-樹的插入

在B-樹中插入一個鍵值k,不是在樹中添加一個葉子結(jié)點(diǎn),而是首先在最低層的某個非終端結(jié)點(diǎn)中添加一個鍵值。且要使插入的結(jié)點(diǎn)中的鍵值字個數(shù)≤m－1,將涉及到結(jié)點(diǎn)的“分裂"問題。1.插入方法

首先要經(jīng)過一個從樹根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的查找過程,如果鍵值k已在樹中,則不用做其他事;否則,找出插入位置,然后再進(jìn)行插入。對于葉子結(jié)點(diǎn)處于第(h+1)層的樹,插入的位置總是在第h層。若結(jié)點(diǎn)的關(guān)鍵字值個數(shù)不超過(m-l),直接把鍵值插就行了;否則需要把結(jié)點(diǎn)分裂成兩個。分裂的做法是,取一新結(jié)點(diǎn),把原結(jié)點(diǎn)上的鍵和k按升序排序后,從中間位置(即┌m/2┐之處)把鍵值(不包括中間位置的鍵值)成兩部分,左部分所含鍵值放在舊結(jié)點(diǎn)中,右部分所含鍵值放在新結(jié)點(diǎn)中,中間位置鍵值連同新結(jié)點(diǎn)的存儲位置插入到父親結(jié)點(diǎn)中。如果父結(jié)點(diǎn)的鍵值個數(shù)也超過(m-l),要再分裂,再往上插,直至這個過程傳到根結(jié)點(diǎn)為止。306580253540556070758550(a)插入前的3階B_樹30252835406580556070758550(b)插入28后的B_樹3038252835658055607075855040(c)插入38后的B_樹305065805560707585382520283540(d)插入20后的B_樹圖9-14B_樹的插入B樹生成過程演示四、B-樹的刪除

B-樹的刪除過程與插入過程類似,只是稍為復(fù)雜一些。要使刪除后的結(jié)點(diǎn)中的鍵值個數(shù)≥┌m/2┐,將涉及到結(jié)點(diǎn)的“合并"問題。

1.刪除方法

在深度為(h+l)的m階B-樹中刪除一個鍵值k,首先要查到鍵值k所在的結(jié)點(diǎn)及在結(jié)點(diǎn)中的位置。若k所在結(jié)點(diǎn)的層數(shù)小于h,則把該結(jié)點(diǎn)的右邊(或左邊)指針?biāo)缸訕渲械淖钚?或最大)鍵值與k對調(diào),使k移到第h層,這樣可根據(jù)k所在結(jié)點(diǎn)為第h層結(jié)點(diǎn)的情況進(jìn)行刪除,從B_樹上第h層結(jié)點(diǎn)中刪除一個鍵值后,使得該結(jié)點(diǎn)的值個數(shù)n減1,此時應(yīng)分以下三種情況進(jìn)行處理:(1)若刪除后結(jié)點(diǎn)中鍵值數(shù)目n≥┌m/2┐－1,在該結(jié)點(diǎn)中刪去鍵值k連同右邊的指針.

(2)若刪除后結(jié)點(diǎn)中鍵值數(shù)目n<┌m/2┐－1,且左(或右)兄弟結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)目＞┌m/2┐－1,則把左(或右)兄弟結(jié)點(diǎn)中最大(或最小)鍵值移到父結(jié)點(diǎn)中,再把父結(jié)點(diǎn)大于(或小于)上移鍵值的鍵值下移到被刪關(guān)鍵字所在結(jié)點(diǎn)中。(3)若刪除后結(jié)點(diǎn)中鍵值數(shù)目n<┌m/2┐－1,及其左、右兄弟結(jié)點(diǎn)的鍵值數(shù)目都等于┌m/2┐－1,則就必須進(jìn)行結(jié)點(diǎn)的“合并”,即把應(yīng)刪的鍵值刪去后,將該結(jié)點(diǎn)中的剩余鍵值和指針連同父結(jié)點(diǎn)中指向該結(jié)點(diǎn)指針的左邊(或右邊)一個鍵值ki一起合并到左兄弟(或右兄弟)結(jié)點(diǎn)中,將ki從父結(jié)點(diǎn)中刪去。如果因此使父結(jié)點(diǎn)中關(guān)鍵字?jǐn)?shù)目<┌m/2┐－1,則對此父結(jié)點(diǎn)做同樣處理,以致于可能直到對根結(jié)點(diǎn)做這樣的處理而使整個樹減少一層。3065802535405560707585503065802540556070758550(a)由圖9-14(a)刪除35后的3階B_樹30657525405560708050(b)刪除85后的B_樹306525405560707550(c)刪除80后的B_樹5065707530405560(d)刪除25后的B_樹圖9-15B_樹的刪除B-樹刪除過程演示9.4.2B+樹一、B+樹定義

1.定義

一棵m階的B+樹滿足下列條件:(1)每個分支結(jié)點(diǎn)至多有m棵子樹。(2)除根結(jié)點(diǎn)外,其他每個分支結(jié)點(diǎn)至少有└(m+1)/2┘棵子樹。(3)根結(jié)點(diǎn)至少有兩棵子樹,至多有m棵子樹。(4)有n棵子樹的結(jié)點(diǎn)有n個鍵值。(5)所有葉結(jié)點(diǎn)包含全部(數(shù)據(jù)文件中記錄)鍵值及指向相應(yīng)記錄的指針(或存放據(jù)文件分塊后每塊的最大鍵值及指向該塊的指針),而且葉結(jié)點(diǎn)按鍵值大小順序鏈接(可以把每個葉結(jié)點(diǎn)看成是一個基本索引塊,它的指針不再指向另一級索引塊,而是直指向數(shù)據(jù)文件中的記錄)。(6)所有分支結(jié)點(diǎn)(可看成是索引的索引)中僅包含它的各個子結(jié)點(diǎn)(即下級索引索引塊)中最大鍵值及指向子結(jié)點(diǎn)的指針.對于m階的B+樹和m階的B-樹,定義中的前三點(diǎn)是相同的,主要的差異是:(1)在B+樹中,具有n個關(guān)鍵字的結(jié)點(diǎn)則含有n棵子樹,即每個關(guān)鍵字對應(yīng)一棵子樹,而在B-樹中,具有n個鍵值的結(jié)點(diǎn)含有(n+1)棵子樹;(2)在B+樹中,每個結(jié)點(diǎn)(除樹根結(jié)點(diǎn)外)中的鍵值個數(shù)n的取值范圍是┌m/2┐≤n≤m,根結(jié)點(diǎn)n的取值范圍是1≤n≤m;而在B_樹中,它們的取值范圍分別是┌m/2┐－1≤n≤m－l和l≤n≤m－1。(3)B+樹中的所有葉子結(jié)點(diǎn)包含了全部鍵值,即其他非葉結(jié)點(diǎn)中的鍵值包含在葉結(jié)點(diǎn)中,而在B-樹中,葉結(jié)點(diǎn)包含的鍵值與其他結(jié)點(diǎn)包含的鍵值是不重復(fù)的。(4)B+樹中所有非葉結(jié)點(diǎn)僅起到索引的作用,即結(jié)點(diǎn)中的每個索引項(xiàng)只含有對應(yīng)子樹的最大關(guān)鍵字和指向該子樹的指針,不含有該鍵值對應(yīng)記錄的存儲地址。而在B-樹中,每個鍵值對應(yīng)一個記錄的存儲地址。(5)通常在B+樹上有兩個頭指針,一個指向根結(jié)點(diǎn),另一個指向鍵值最小的葉子結(jié)點(diǎn),所有葉結(jié)點(diǎn)鏈接成一個不定長的線性鏈表。40653540606555654045552025301530401015roothead圖9-16B+樹二、B+樹查找

在B+樹中可以采用兩種查找方式,一種是直接從最小鍵值開始進(jìn)行順序查找,另一種就是從B+樹的根結(jié)點(diǎn)開始進(jìn)行隨機(jī)查找。這種查找方式與B-樹的查找方法相似,只是在分支結(jié)點(diǎn)上的鍵值與查找值相等時,查找并不結(jié)束,要繼續(xù)查到葉結(jié)點(diǎn)為止,此時若查找成功,則按所給指針取出對應(yīng)記錄即可。因此,在B+樹中,不管查找成功與否,每次查找都是經(jīng)過了一條從樹根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑。

三、B+樹插入

與B-樹的插入操作相似,B+樹的插入也從葉子結(jié)點(diǎn)開始,當(dāng)插入后結(jié)點(diǎn)中的鍵值個數(shù)大于m時要分裂成兩個結(jié)點(diǎn),它們所含鍵值個數(shù)分別為┌(m+1)/2┐和└(m+1)/2┘,同時要使得它們的雙親結(jié)點(diǎn)中包含有這兩個結(jié)點(diǎn)的最大鍵值和指向它們的指針。若雙親結(jié)點(diǎn)的鍵值數(shù)目因此而大于m,應(yīng)繼續(xù)分裂,依此類推。四、B+樹刪除

B+樹的刪除也是從葉子結(jié)點(diǎn)開始,當(dāng)葉結(jié)點(diǎn)中最大鍵值被刪除時,分支結(jié)點(diǎn)中的值可以作為“分界鍵值”存在。若因刪除操作而使結(jié)點(diǎn)中鍵值個數(shù)少于┌m/2┐時,則從兄弟結(jié)點(diǎn)中調(diào)劑鍵值或和兄弟結(jié)點(diǎn)合并,其過程和B-樹相似。9.4哈希查找表一、哈希表的概念二、哈希函數(shù)的構(gòu)造方法三、沖突處理方法四、哈希表的查找及分析

前面介紹的所有查找都是基于待查關(guān)鍵字與表中元素進(jìn)行比較而實(shí)現(xiàn)的查找方法，查找的效率依賴于查找過程中所進(jìn)行的比較次數(shù)。理想的情況是希望不經(jīng)過任何比較，一次便能得到所查記錄。哈希表它既是一種查找方法，又是一種存貯方法哈希表：即散列存儲結(jié)構(gòu)。

散列法存儲的基本思想：建立關(guān)鍵碼字與其存儲位置的對應(yīng)關(guān)系，或者說，由關(guān)鍵碼的值決定數(shù)據(jù)的存儲地址。優(yōu)點(diǎn)：查找速度極快（O(1)）,查找效率與元素個數(shù)n無關(guān)！例1：若將學(xué)生信息按如下方式存入計算機(jī)，如：將2001011810201的所有信息存入V[01]單元；將2001011810202的所有信息存入V[02]單元；……將2001011810231的所有信息存入V[31]單元。欲查找學(xué)號為2001011810216的信息，便可直接訪問V[16]！一、哈希表的概念例2：

有數(shù)據(jù)元素序列(14，23，39，9，25，11)，若規(guī)定每個元素k的存儲地址H（k）＝k，請畫出存儲結(jié)構(gòu)圖。（注：H（k）＝k稱為散列函數(shù)）解：根據(jù)散列函數(shù)H（k）＝k，可知元素14應(yīng)當(dāng)存入地址為14的單元，元素23應(yīng)當(dāng)存入地址為23的單元，……，對應(yīng)散列存儲表（哈希表）如下：討論：如何進(jìn)行散列查找？根據(jù)存儲時用到的散列函數(shù)H(k)表達(dá)式，迅即可查到結(jié)果！例如，查找key=9,則訪問H(9)=9號地址，若內(nèi)容為9則成功；若查不到，應(yīng)當(dāng)設(shè)法返回一個特殊值，例如空指針或空記錄。

地址…9…11…14…232425…39…內(nèi)點(diǎn)：空間效率低！選取某個函數(shù)，依該函數(shù)按關(guān)鍵字計算元素的存儲位置，并按此存放；查找時，由同一個函數(shù)對給定值k計算地址，將k與地址單元中元素關(guān)鍵碼進(jìn)行比較，確定查找是否成功。通常關(guān)鍵碼的集合比哈希地址集合大得多，因而經(jīng)過哈希函數(shù)變換后，可能將不同的關(guān)鍵碼映射到同一個哈希地址上，這種現(xiàn)象稱為沖突。若干術(shù)語哈希方法(雜湊法)哈希函數(shù)(雜湊函數(shù))哈希表(雜湊表)

沖突哈希方法中使用的轉(zhuǎn)換函數(shù)稱為哈希函數(shù)(雜湊函數(shù))按上述思想構(gòu)造的表稱為哈希表(雜湊表)

有6個元素的關(guān)鍵碼分別為：（14，23，39，9，25，11）。選取關(guān)鍵碼與元素位置間的函數(shù)為H(k)=kmod7通過哈希函數(shù)對6個元素建立哈希表：253923914沖突現(xiàn)象舉例：6個元素用7個地址應(yīng)該足夠!H(14)=14%7=011H(25)=25%7=4H(11)=11%7=4有沖突！0123456所以，哈希方法必須解決以下兩個問題：1）構(gòu)造好的哈希函數(shù)（a）所選函數(shù)盡可能簡單，以便提高轉(zhuǎn)換速度；（b）所選函數(shù)對關(guān)鍵碼計算出的地址，應(yīng)在哈希地址集中大致均勻分布，以減少空間浪費(fèi)。2）制定一個好的解決沖突的方案查找時，如果從哈希函數(shù)計算出的地址中查不到關(guān)鍵碼，則應(yīng)當(dāng)依據(jù)解決沖突的規(guī)則，有規(guī)律地查詢其它相關(guān)單元。在哈希查找方法中，沖突是不可能避免的，只能盡可能減少。二、哈希函數(shù)的構(gòu)造方法常用的哈希函數(shù)構(gòu)造方法有：直接定址法除留余數(shù)法

乘余取整法數(shù)字分析法平方取中法折疊法隨機(jī)數(shù)法要求一：n個數(shù)據(jù)原僅占用n個地址，雖然散列查找是以空間換時間，但仍希望散列的地址空間盡量小。要求二：無論用什么方法存儲，目的都是盡量均勻地存放元素，以避免沖突。Hash(key)=a·key+b(a、b為常數(shù))優(yōu)點(diǎn)：以關(guān)鍵碼key的某個線性函數(shù)值為哈希地址，不會產(chǎn)生沖突.缺點(diǎn)：要占用連續(xù)地址空間，空間效率低。

例：關(guān)鍵碼集合為{100，300，500，700，800，900}，選取哈希函數(shù)為Hash(key)=key/100，則存儲結(jié)構(gòu)（哈希表）如下：01234567899008007005003001001、直接定址法Hash(key)=B*(A*keymod1)

(A、B均為常數(shù)，且0<A<1，B為整數(shù))特點(diǎn)：以關(guān)鍵碼key乘以A，取其小數(shù)部分，然后再放大B倍并取整，作為哈希地址。Hash(key)=keymodp(p是一個整數(shù))特點(diǎn)：以關(guān)鍵碼除以p的余數(shù)作為哈希地址。關(guān)鍵：如何選取合適的p？技巧：若設(shè)計的哈希表長為m，則一般取p≤m且為質(zhì)數(shù)

（也可以是不包含小于20質(zhì)因子的合數(shù)）。3、乘余取整法2、除留余數(shù)法（A*keymod1）就是取A*key的小數(shù)部分例：欲以學(xué)號最后兩位作為地址，則哈希函數(shù)應(yīng)為：

H(k)=100*(0.01*k%1)其實(shí)也可以用法2實(shí)現(xiàn)：H(k)=k%100特點(diǎn)：某關(guān)鍵字的某幾位組合成哈希地址。所選的位應(yīng)當(dāng)是：各種符號在該位上出現(xiàn)的頻率大致相同。34705243491487348269634852703486305349805834796713473919例：有一組（例如80個）關(guān)鍵碼，其樣式如下：4、數(shù)字分析法討論：①第1、2位均是“3和4”，第3位也只有“

7、8、9”，因此，這幾位不能用，余下四位分布較均勻，可作為哈希地址選用。位號：①②③④⑤⑥⑦②

若哈希地址取兩位（因元素僅80個），則可取這四位中的任意兩位組合成哈希地址，也可以取其中兩位與其它兩位疊加求和后，取低兩位作哈希地址。特點(diǎn)：對關(guān)鍵碼平方后，按哈希表大小，取中間的若干位作為哈希地址。理由：因?yàn)橹虚g幾位與數(shù)據(jù)的每一位都相關(guān)。例：2589的平方值為6702921，可以取中間的029為地址。6、折疊法特點(diǎn)：將關(guān)鍵碼自左到右分成位數(shù)相等的幾部分（最后一部分位數(shù)可以短些），然后將這幾部分疊加求和，并按哈希表表長，取后幾位作為哈希地址。適用于：每一位上各符號出現(xiàn)概率大致相同的情況。法1：移位法──將各部分的最后一位對齊相加。法2：間界疊加法──從一端向另一端沿分割界來回折疊后，最后一位對齊相加。例：元素42751896,用法1：427＋518＋96=1041

用法2：42751896—>724+518+69=13115、平方取中法7、隨機(jī)數(shù)法Hash(key)=random(key)(random為偽隨機(jī)函數(shù))適用于：關(guān)鍵字長度不等的情況。造表和查找都很方便。①執(zhí)行速度（即計算哈希函數(shù)所需時間）；②關(guān)鍵字的長度；③哈希表的大??；④關(guān)鍵字的分布情況；⑤查找頻率。小結(jié)：構(gòu)造哈希函數(shù)的原則：三、沖突處理方法常見的沖突處理方法有：開放定址法（開地址法）鏈地址法（拉鏈法）再哈希法（雙哈希函數(shù)法）建立一個公共溢出區(qū)1、開放定址法（開地址法）設(shè)計思路：有沖突時就去尋找下一個空的哈希地址，只要哈希表足夠大，空的哈希地址總能找到，并將數(shù)據(jù)元素存入。具體實(shí)現(xiàn)：Hi=(Hash(key)+di)modm(1≤i<m)

其中：

Hash(key)為哈希函數(shù)

m為哈希表長度

di

為增量序列1，2，…m-1，且di=i1.線性探測法含義：一旦沖突，就找附近（下一個）空地址存入。開放定址法建立散列表演示關(guān)鍵碼集為{47，7，29，11，16，92，22，8，3}，設(shè)：哈希表表長為m=11；哈希函數(shù)為Hash(key)=keymod11；擬用線性探測法處理沖突。建哈希表如下：解釋：①47、7（以及11、16、92）均是由哈希函數(shù)得到的沒有沖突的哈希地址；012345678910477△▲△△例：291116922283②Hash(29)=7，哈希地址有沖突，需尋找下一個空的哈希地址：由H1=(Hash(29)+1)mod11=8，哈希地址8為空，因此將29存入。③

另外，22、8、3同樣在哈希地址上有沖突，也是由H1找到空的哈希地址的。其中3

還連續(xù)移動了兩次（二次聚集）線性探測法的優(yōu)點(diǎn)：只要哈希表未被填滿，保證能找到一個空地址單元存放有沖突的元素；線性探測法的缺點(diǎn)：可能使第i個哈希地址的同義詞存入第i+1個哈希地址，這樣本應(yīng)存入第i+1個哈希地址的元素變成了第i+2個哈希地址的同義詞，……，因此，可能出現(xiàn)很多元素在相鄰的哈希地址上“堆積”起來，大大降低了查找效率。解決方案：可