數(shù)據(jù)結(jié)構(gòu)第九章查找

19.1基本概念9.2靜態(tài)查找表9.3動(dòng)態(tài)查找表9.4哈希表9.5B-樹(shù)和B+樹(shù)第九章查找教材第8、11和12章省略，因《操作系統(tǒng)》課程會(huì)涉及。2數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容39.1基本概念查找表——由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合

查找——查詢(Searching)特定元素是否在表中。查找成功——若表中存在特定元素，稱查找成功，應(yīng)輸出該記錄；查找不成功——否則，稱查找不成功（也應(yīng)輸出失敗標(biāo)志或失敗位置）是一種數(shù)據(jù)結(jié)構(gòu)49.1基本概念靜態(tài)查找動(dòng)態(tài)查找關(guān)鍵字主關(guān)鍵字——只查找，不改變集合內(nèi)的數(shù)據(jù)元素。——既查找，又改變（增減）集合內(nèi)的數(shù)據(jù)元素?！涗浿心硞€(gè)數(shù)據(jù)項(xiàng)的值，可用來(lái)識(shí)別一個(gè)記錄

(預(yù)先確定的記錄的某種標(biāo)志)——可以唯一標(biāo)識(shí)一個(gè)記錄的關(guān)鍵字例如“學(xué)號(hào)”例如“女”次關(guān)鍵字——識(shí)別若干記錄的關(guān)鍵字5討論2：對(duì)查找表常用的操作有哪些？

查詢某個(gè)“特定的”數(shù)據(jù)元素是否在表中；查詢某個(gè)“特定的”數(shù)據(jù)元素的各種屬性；在查找表中插入一元素；從查找表中刪除一元素。

討論討論1：查找的過(guò)程是怎樣的？

給定一個(gè)值K，在含有n個(gè)記錄的文件中進(jìn)行搜索，尋找一個(gè)關(guān)鍵字值等于K的記錄，如找到則輸出該記錄，否則輸出查找不成功的信息。“特定的”=關(guān)鍵字6討論3：有哪些查找方法？查找方法取決于表中數(shù)據(jù)的排列方式;討論：例如查字典針對(duì)靜態(tài)查找表和動(dòng)態(tài)查找表的查找方法也有所不同。7討論4：如何評(píng)估查找方法的優(yōu)劣？明確：查找的過(guò)程就是將給定的K值與文件中各記錄的關(guān)鍵字項(xiàng)進(jìn)行比較的過(guò)程。所以用比較次數(shù)的平均值來(lái)評(píng)估算法的優(yōu)劣。稱為平均查找長(zhǎng)度ASL。其中：n是文件記錄個(gè)數(shù)；Pi是查找第i個(gè)記錄的查找概率（通常取等概率,即Pi=1/n）;Ci是找到第i個(gè)記錄時(shí)所經(jīng)歷的比較次數(shù)。統(tǒng)計(jì)意義上的數(shù)學(xué)期望值物理意義：假設(shè)每一元素被查找的概率相同，則查找每一元素所需的比較次數(shù)之總和再取平均，即為ASL。顯然，ASL值越小，時(shí)間效率越高。AverageSearchLength8針對(duì)靜態(tài)查找表的查找算法主要有：9.2靜態(tài)查找表一、順序查找（線性查找）二、折半查找（二分或?qū)Ψ植檎遥ㄖ攸c(diǎn)與考點(diǎn)）三、分塊查找（索引順序查找）（第三種物理結(jié)構(gòu)）四、靜態(tài)樹(shù)表的查找9靜態(tài)查找表的定義（抽象數(shù)據(jù)類型）ADTStaticSearchTable{數(shù)據(jù)對(duì)象D:數(shù)據(jù)關(guān)系R：基本操作P：}ADTStaticSearchTable參見(jiàn)教材P2169.2靜態(tài)查找表109.2.1順序查找（又稱線性查找）順序查找：用逐一比較的辦法順序查找關(guān)鍵字，這顯然是最直接的辦法。對(duì)順序結(jié)構(gòu)如何線性查找？對(duì)單鏈表結(jié)構(gòu)如何線性查找？對(duì)非線性樹(shù)結(jié)構(gòu)如何順序查找?見(jiàn)下頁(yè)之例或教材P216從頭指針始“順藤摸瓜”借助各種遍歷操作！111順序表的存儲(chǔ)結(jié)構(gòu)(動(dòng)態(tài)數(shù)組）typedefstruct{ElemType*elem;

//表基址，0號(hào)單元留空。表容量為全部元素

intlength;//表長(zhǎng)，即表中數(shù)據(jù)元素個(gè)數(shù)

}SSTable;9.2.1順序查找（又稱線性查找）122算法的實(shí)現(xiàn)技巧：把待查關(guān)鍵字key存入表頭或表尾（俗稱“哨兵”），這樣可以加快執(zhí)行速度。例：若將待查找的特定值key存入順序表的首部（如0號(hào)單元），并從后向前逐個(gè)比較,就不必?fù)?dān)心“查不到”。9.2.1順序查找（又稱線性查找）13intSearch_Seq(SSTableST,KeyTypekey){ST.elem[0].key=key;

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

returni;}//Search_Seq2算法的實(shí)現(xiàn)//在順序表ST中，查找關(guān)鍵字與key相同的元素；若成功，返回其位置信息，否則返回0//設(shè)立哨兵，可免去查找過(guò)程中每一步都要檢測(cè)是否查找完畢。//找不到=不成功，返回值必為i=0；找得到=成功，返回值i正好代表所找元素的位置。//不要用for(i=1;i<=n;i++)

或for(i=n;i>0;--i)9.2.1順序查找（又稱線性查找）14討論1：查找失敗怎么辦？——返回特殊標(biāo)志，例如返回空記錄或空指針。前例中設(shè)立了“哨兵”，就是將關(guān)鍵字送入末地址ST.elem[0].key使之結(jié)束，并返回i=0。討論2：查找效率怎樣計(jì)算？——用平均查找長(zhǎng)度ASL衡量。4算法分析討論9.2.1順序查找（又稱線性查找）154算法分析討論討論3：如何計(jì)算ASL？分析：查找第1個(gè)元素所需的比較次數(shù)為1；查找第2個(gè)元素所需的比較次數(shù)為2；……查找第n個(gè)元素所需的比較次數(shù)為n；總計(jì)全部比較次數(shù)為：1＋2＋…＋n=(1+n)n/2未考慮查找不成功的情況：查找哨兵所需的比較次數(shù)為n+1這是查找成功的情況若求某一個(gè)元素的平均查找次數(shù)，還應(yīng)當(dāng)除以n（等概率），即：ASL＝（1＋n）/2，時(shí)間效率為O(n)9.2.1順序查找（又稱線性查找）16優(yōu)點(diǎn)：算法簡(jiǎn)單，且對(duì)順序結(jié)構(gòu)或鏈表結(jié)構(gòu)均適用。缺點(diǎn)：ASL太大，時(shí)間效率太低。5順序查找的特點(diǎn)：9.2.1順序查找（又稱線性查找）179.2.2、折半查找（二分查找）這是一種容易想到的查找方法。先給數(shù)據(jù)排序（例如按升序排好），形成有序表，然后再將key與正中元素相比，若key小，則縮小至右半部?jī)?nèi)查找；再取其中值比較，每次縮小1/2的范圍，直到查找成功或失敗為止。181、存儲(chǔ)結(jié)構(gòu)對(duì)順序表結(jié)構(gòu)如何編程實(shí)現(xiàn)折半查找算法？

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

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

——可借助二叉排序樹(shù)來(lái)查找（屬動(dòng)態(tài)查找表形式）。9.2.2、折半查找（二分查找）19解：①先設(shè)定3個(gè)輔助標(biāo)志:low,high,mid，顯然有：mid=(low+high)/2折半查找舉例：已知如下11個(gè)元素的有序表：Low指向待查元素所在區(qū)間的下界high指向待查元素所在區(qū)間的上界mid指向待查元素所在區(qū)間的中間位置（0513192137566475808892）,請(qǐng)查找關(guān)鍵字為21

和85的數(shù)據(jù)元素。9.2.2、折半查找（二分查找）20②運(yùn)算步驟：(1)low=1,high=11,故mid=6，待查范圍是[1,11]；(2)若ST.elem[mid].key<key，說(shuō)明key[mid+1,high]，則令：low=mid+1;重算mid＝(low+high)/2；.(3)若ST.elem[mid].key>key，說(shuō)明key[low,mid-1]，則令：high=mid–1;重算mid；(4)若ST.elem[mid].key=key，說(shuō)明查找成功，元素序號(hào)=mid;結(jié)束條件：（1）查找成功：ST.elem[mid].key=key

（2）查找不成功：high<low（意即區(qū)間長(zhǎng)度小于0）9.2.2、折半查找（二分查找）219.2.2、折半查找（二分查找）22討論1：若關(guān)鍵字不在表中，怎樣得知并及時(shí)停止查找？——典型標(biāo)志是：當(dāng)查找范圍的上界<下界時(shí)停止查找。討論2：如何計(jì)算二分查找的時(shí)間效率（ASL）？問(wèn)題討論9.2.2、折半查找（二分查找）23經(jīng)1次比較就查找成功的元素有1個(gè)（20），即中間值；經(jīng)2次比較就查找成功的元素有2個(gè)（21），即1/4處和3/4處；3次比較就查找成功的元素有4個(gè)（22），即1/8，3/8，5/8，7/8處4次比較就查找成功的元素有8個(gè)（23），即1/16處，3/16處…………則第m次比較時(shí)查找成功的元素應(yīng)該有（2m-1）個(gè)。全部比較總次數(shù)為1×20＋2×21＋3×22＋4×23…＋m×2m—1

＝推導(dǎo)過(guò)程注：為方便起見(jiàn)，假設(shè)表中全部n個(gè)元素剛好是2m-1個(gè)，此時(shí)暫不討論第m次比較后還有剩余元素的情況。9.2.2、折半查找（二分查找）24請(qǐng)注意：ASL的含義是“平均每個(gè)數(shù)據(jù)的查找時(shí)間”，而前式是n個(gè)數(shù)據(jù)查找時(shí)間的總和，所以：（詳細(xì)推導(dǎo)過(guò)程見(jiàn)教材P221的附錄1）推導(dǎo)過(guò)程9.2.2、折半查找（二分查找）25練習(xí)題課堂練習(xí)1（多選題）使用折半查找算法時(shí)，要求被查文件：Ａ．采用鏈?zhǔn)酱尜A結(jié)構(gòu)Ｂ．記錄的長(zhǎng)度≤12Ｃ．采用順序存貯結(jié)構(gòu)Ｄ．記錄按關(guān)鍵字遞增有序課堂練習(xí)2在有序線性表a[20]上進(jìn)行折半查找，則平均查找長(zhǎng)度為

?！獭?.79.2.2、折半查找（二分查找）26找到有序表中任一記錄的過(guò)程就是：走了一條從根結(jié)點(diǎn)到與該記錄對(duì)應(yīng)結(jié)點(diǎn)的路徑。比較的關(guān)鍵字個(gè)數(shù)為：該結(jié)點(diǎn)在判定樹(shù)上的層次數(shù)。查找成功時(shí)比較的關(guān)鍵字個(gè)數(shù)最多不超過(guò)樹(shù)的深度d:d=log2n+1查找不成功的過(guò)程就是：走了一條從根結(jié)點(diǎn)到外部結(jié)點(diǎn)的路徑。查找不成功最多比較次數(shù)也為d再用二分查找樹(shù)來(lái)分析ASL(參見(jiàn)教材P220）以（a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11）為例：a6a3a9判定樹(shù)由表中元素個(gè)數(shù)決定，且n個(gè)元素表的折半查找判定樹(shù)是唯一的。a1a10a7a4a11a8a2a527分塊查找（索引順序查找）討論：對(duì)順序查找除了折半改進(jìn)法外，還有無(wú)其他改進(jìn)算法？有，例如分塊查找法。順序查找其它改進(jìn)算法289.2.3分塊查找（索引順序查找）思路：先讓數(shù)據(jù)分塊有序，即分成若干子表，要求每個(gè)子表中的數(shù)據(jù)元素值都比后一塊中的數(shù)值?。ǖ颖韮?nèi)部未必有序）。然后將各子表中的最大關(guān)鍵字構(gòu)成一個(gè)索引表，表中還要包含每個(gè)子表的起始地址（即頭指針）。2448605874491312920334244388653822例：特點(diǎn)：塊間有序，塊內(nèi)無(wú)序29分塊查找過(guò)程舉例：索引表塊內(nèi)最大關(guān)鍵字各塊起始地址2212138920334244382448605874498653第1塊第2塊第3塊2248861713特點(diǎn)：塊間有序，塊內(nèi)無(wú)序查找：塊間折半，塊內(nèi)線性9.2.3分塊查找（索引順序查找）30查找步驟分兩步進(jìn)行：①對(duì)索引表使用折半查找法（因?yàn)樗饕硎怯行虮恚?；②確定了待查關(guān)鍵字所在的子表后，在子表內(nèi)采用順序查找法（因?yàn)楦髯颖韮?nèi)部是無(wú)序表）；9.2.3分塊查找（索引順序查找）31查找效率ASL分析對(duì)索引表查找的ASL對(duì)塊內(nèi)查找的ASLS為每塊內(nèi)部的記錄個(gè)數(shù)，n/s即塊的數(shù)目例如：當(dāng)n=9，s=3時(shí)

分塊法的ASLbs=3.5折半法的ASL≈log2n=3.1

順序法的ASL=(1＋n)/2=5ASL=Lb+Lw但折半法要預(yù)先全排序，仍需時(shí)間。9.2.3分塊查找（索引順序查找）討論：當(dāng)有序表中各記錄的查找概率不相等時(shí)，該如何查找？提醒：此時(shí)用折半查找法未必最優(yōu)?。▍⒁?jiàn)教材P222例）改進(jìn)：若將各記錄的概率看作是二叉樹(shù)之權(quán)值，則轉(zhuǎn)為研究帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)（類似最優(yōu)二叉樹(shù)）。

靜態(tài)最優(yōu)查找樹(shù)算法——時(shí)間代價(jià)高；實(shí)用算法：次優(yōu)查找樹(shù)9.2.4靜態(tài)樹(shù)表查找33CBDAE(a)BADCE(b)3E29D2301CBA例：有序表

對(duì)應(yīng)權(quán)值算法詳見(jiàn)教材P222—225不合理較合理9.2.4靜態(tài)樹(shù)表查找349.3動(dòng)態(tài)查找表特點(diǎn)：表結(jié)構(gòu)在查找過(guò)程中動(dòng)態(tài)生成。要求：對(duì)于給定值key,若表中存在其關(guān)鍵字等于key的記錄，則查找成功返回；否則插入關(guān)鍵字等于key的記錄。典型的動(dòng)態(tài)表———二叉排序樹(shù)35一、二叉排序樹(shù)的定義二、二叉排序樹(shù)的插入與刪除三、二叉排序樹(shù)的查找分析四、平衡二叉樹(shù)(難點(diǎn)）9.3動(dòng)態(tài)查找表典型的動(dòng)態(tài)表———二叉排序樹(shù)369.3.1

二叉排序樹(shù)的定義或是一棵空樹(shù)；或者是具有如下性質(zhì)的非空二叉樹(shù)：（1）左子樹(shù)的所有結(jié)點(diǎn)均小于根的值；（2）右子樹(shù)的所有結(jié)點(diǎn)均大于根的值；（3）它的左右子樹(shù)也分別為二叉排序樹(shù)。37例：下列2種圖形中，哪個(gè)不是二叉排序樹(shù)？（a）（b）想一想：對(duì)它中序遍歷之后是什么效果？74110265398510216473989.3.1二叉排序樹(shù)的定義384524531290查找成功，返回查找成功，返回例：輸入待查找的關(guān)鍵字序列=（45，24，53，45，12，24，90）查找不成功則插入樹(shù)中9.3.2、二叉排序樹(shù)的插入與刪除39如果改變輸入順序?yàn)椋?4，53，45，45，12，24，90），查找成功，返回查找成功，返回則生成的二叉排序樹(shù)形態(tài)不同2453451290這種既查找又插入的過(guò)程稱為動(dòng)態(tài)查找9.3.2、二叉排序樹(shù)的插入與刪除40①查找過(guò)程與順序結(jié)構(gòu)有序表中的折半查找相似，查找效率高；②中序遍歷此二叉樹(shù)，將會(huì)得到一個(gè)關(guān)鍵字的有序序列（即實(shí)現(xiàn)了排序運(yùn)算）；③如果查找不成功，能夠方便地將被查元素插入到二叉樹(shù)的葉子結(jié)點(diǎn)上，而且插入或刪除時(shí)只需修改指針而不需移動(dòng)元素。二叉排序樹(shù)既有類似于折半查找的特性，又采用了鏈表存儲(chǔ)，它是動(dòng)態(tài)查找表的一種適宜表示。將線性表構(gòu)造成二叉排序樹(shù)的優(yōu)點(diǎn)9.3.2、二叉排序樹(shù)的插入與刪除411二叉排序樹(shù)的查找&插入算法如何實(shí)現(xiàn)？思路：查找不成功，生成一個(gè)新結(jié)點(diǎn)s，插入到二叉排序樹(shù)中；查找成功則返回。SearchBST(K,&t){//K為待查關(guān)鍵字，t為根結(jié)點(diǎn)指針

p=t;//p為查找過(guò)程中進(jìn)行掃描的指針

while（p!=NULL）{case{K=p->data:{查找成功，return}

K<p->data:{q=p；p=p->L_child}//繼續(xù)向左搜索

K>p->data:{q=p；p=p->R_child}//繼續(xù)向右搜索

}

}//查找不成功則插入到二叉排序樹(shù)中程序：9.3.2、二叉排序樹(shù)的插入與刪除42s=(BiTree)malloc(sizeof(BiTNode));s->data=K;s->L_child=NULL;s->R_child=NULL;

//查找不成功，生成一個(gè)新結(jié)點(diǎn)s，插入到二叉排序樹(shù)葉子處case{

t=NULL：t=s;//若t為空，則插入的結(jié)點(diǎn)s作為根結(jié)點(diǎn)K<q->data:q->L_child=s;//若K比葉子小，掛左邊K>q->data:q->R_child=s;//若K比葉子大，掛右邊

}

returnOK}以上為查找、插入二合一的非遞歸程序該模塊就是“建樹(shù)”的非遞歸算法！9.3.2、二叉排序樹(shù)的插入與刪除43插入模塊（非遞歸方式）參見(jiàn)教材P228算法9.5（b）;查找模塊參見(jiàn)教材P228算法9.5（a）;該模塊就是“建樹(shù)”的非遞歸算法！9.3.2、二叉排序樹(shù)的插入與刪除對(duì)于二叉排序樹(shù)，刪除樹(shù)上一個(gè)結(jié)點(diǎn)相當(dāng)于刪除有序序列中的一個(gè)記錄，要求刪除后仍需保持二叉排序樹(shù)的特性。2二叉排序樹(shù)的刪除操作如何實(shí)現(xiàn)？如何刪除一個(gè)結(jié)點(diǎn)？假設(shè)：*p表示被刪結(jié)點(diǎn)的指針；PL和PR分別表示*P的左、右孩子指針；*f表示*p的雙親結(jié)點(diǎn)指針；并假定*p是*f的左孩子；則可能有三種情況：9.3.2、二叉排序樹(shù)的插入與刪除45*p為葉子：刪除此結(jié)點(diǎn)時(shí)，直接修改*f指針域即可；*p只有一棵子樹(shù)（或左或右）：令PL或PR為*f的左孩子即可；*p有兩棵子樹(shù)：情況最復(fù)雜→fpPLPR9.3.2、二叉排序樹(shù)的插入與刪除2二叉排序樹(shù)的刪除操作如何實(shí)現(xiàn)？46分析：設(shè)刪除前的中序遍歷序列為：….PLspPRf….//顯然p的直接前驅(qū)是s//s是p左子樹(shù)最右下方的結(jié)點(diǎn)希望刪除p后，其它元素的相對(duì)位置不變。有兩種解決方法：法1：令p的左子樹(shù)為f的左子樹(shù)，p的右子樹(shù)接為s的右子樹(shù)；//即fL=PL;SR=PR;法2：直接令s代替p//s為p左子樹(shù)最右下方的結(jié)點(diǎn)難點(diǎn)：*p有兩棵子樹(shù)時(shí)，如何進(jìn)行刪除操作？fpPLPRs9.3.2、二叉排序樹(shù)的插入與刪除47FCCLSSLQLPPRQPRFCCLSSLQLPPRQ法2:FCCLSSLQLPPRQ法1:例：請(qǐng)從下面的二叉排序樹(shù)中刪除結(jié)點(diǎn)P。SSL9.3.2、二叉排序樹(shù)的插入與刪除481二叉排序樹(shù)上查找某關(guān)鍵字等于結(jié)點(diǎn)值的過(guò)程，其實(shí)就是走了一條從根到該結(jié)點(diǎn)的路徑。比較的關(guān)鍵字次數(shù)＝此結(jié)點(diǎn)的層次數(shù);

最多的比較次數(shù)＝樹(shù)的深度（或高度），即log2n+19.3.3二叉排序樹(shù)的查找分析49其中：ni是每層結(jié)點(diǎn)個(gè)數(shù)；

Ci是結(jié)點(diǎn)所在層次數(shù)；m為樹(shù)深。最壞情況：插入的n個(gè)元素從一開(kāi)始就有序（單調(diào)增或減），

——變成了單支樹(shù)的形態(tài)！此時(shí)樹(shù)的深度為n;ASL=(n+1)/2與線性查找的ASL相同！2一棵二叉排序樹(shù)的平均查找長(zhǎng)度為：9.3.3二叉排序樹(shù)的查找分析50最壞情況：即插入的n個(gè)元素從一開(kāi)始就有序。（單支樹(shù)）此時(shí)樹(shù)深為n;ASL=(n+1)/2;與順序查找情況相同。最好情況：即：與折半查找中的判定樹(shù)相同（形態(tài)均衡）此時(shí)樹(shù)深為：log2n+1；ASL=log2(n+1)–1；與折半查找情況相同。一般情況：（與logn同階）思考：如何提高二叉排序樹(shù)的查找效率？ 盡量讓二叉樹(shù)的形狀均衡平衡二叉樹(shù)9.3.3二叉排序樹(shù)的查找分析9.3.4二叉排序樹(shù)操作代碼5152(a)平衡樹(shù)(b)不平衡樹(shù)平衡二叉樹(shù)的特點(diǎn)： 任一結(jié)點(diǎn)的平衡因子只能取：-1、0或1。對(duì)于一棵有n個(gè)結(jié)點(diǎn)的AVL樹(shù)，其高度保持在O(log2n)數(shù)量級(jí)，ASL也保持在O(log2n)量級(jí)。例：判斷下列二叉樹(shù)是否AVL樹(shù)？00011-1-120001-19.3.4平衡二叉樹(shù)53如果在一棵AVL樹(shù)中插入一個(gè)新結(jié)點(diǎn)，就有可能造成失衡，此時(shí)必須重新調(diào)整樹(shù)的結(jié)構(gòu)，使之恢復(fù)平衡。我們稱調(diào)整平衡過(guò)程為平衡旋轉(zhuǎn)。9.3.4平衡二叉樹(shù)54現(xiàn)分別介紹這四種平衡旋轉(zhuǎn)。平衡旋轉(zhuǎn)可以歸納為四類：

LL平衡旋轉(zhuǎn)

RR平衡旋轉(zhuǎn)

LR平衡旋轉(zhuǎn)

RL平衡旋轉(zhuǎn)9.3.4平衡二叉樹(shù)55若在A的左子樹(shù)的左子樹(shù)上插入結(jié)點(diǎn)，使A的平衡因子從1增加至2，需要進(jìn)行一次順時(shí)針旋轉(zhuǎn)。ABCABC1）LL平衡旋轉(zhuǎn)以B為旋轉(zhuǎn)軸9.3.4平衡二叉樹(shù)56若在A的右子樹(shù)的右子樹(shù)上插入結(jié)點(diǎn)，使A的平衡因子從-1增加至-2，需要進(jìn)行一次逆時(shí)針旋轉(zhuǎn)。2）RR平衡旋轉(zhuǎn)ABCABC以B為旋轉(zhuǎn)軸9.3.4平衡二叉樹(shù)57ABC若在A的左子樹(shù)的右子樹(shù)上插入結(jié)點(diǎn)，使A的平衡因子從1增加至2，需要先進(jìn)行逆時(shí)針旋轉(zhuǎn)，再順時(shí)針旋轉(zhuǎn)。3）LR平衡旋轉(zhuǎn)ABC以插入的結(jié)點(diǎn)C為旋轉(zhuǎn)軸ABC9.3.4平衡二叉樹(shù)58若在A的右子樹(shù)的左子樹(shù)上插入結(jié)點(diǎn)，使A的平衡因子從-1增加至-2，需要先進(jìn)行順時(shí)針旋轉(zhuǎn)，再逆時(shí)針旋轉(zhuǎn)。4）RL平衡旋轉(zhuǎn)ABCABCABC這種調(diào)整規(guī)則可以保證二叉排序樹(shù)的次序不變以插入的結(jié)點(diǎn)C為旋轉(zhuǎn)軸9.3.4平衡二叉樹(shù)59013037024例：請(qǐng)將下面序列構(gòu)成一棵平衡二叉排序樹(shù)013037-113024-124-213需要RR平衡旋轉(zhuǎn)(繞B逆轉(zhuǎn),B為根）090-124-137053190-237需要RL平衡旋轉(zhuǎn)(繞C先順后逆）037090053037090053

（13，24，37，90，53）建立平衡二叉樹(shù)旋轉(zhuǎn)注意要點(diǎn)1、首先確定屬于何種類型的旋轉(zhuǎn)；2、確定旋轉(zhuǎn)軸LL和RR型的旋轉(zhuǎn)軸在沿著失衡路徑上，以失去平衡點(diǎn)的直接后繼結(jié)點(diǎn)作為旋轉(zhuǎn)軸；LR和RL的旋轉(zhuǎn)軸是沿著失衡路徑上，失去平衡點(diǎn)的后兩層結(jié)點(diǎn)作為旋轉(zhuǎn)軸。60619.4哈希查找表一、哈希表的概念二、哈希函數(shù)的構(gòu)造方法三、沖突處理方法四、哈希表的查找及分析629.4.1哈希表的概念哈希表：即散列存儲(chǔ)結(jié)構(gòu)（第四種物理結(jié)構(gòu)，用于快速查找）。散列法存儲(chǔ)的基本思想：建立關(guān)鍵碼字與其存儲(chǔ)位置的對(duì)應(yīng)關(guān)系，或者說(shuō)，由關(guān)鍵碼的值決定數(shù)據(jù)的存儲(chǔ)地址。優(yōu)點(diǎn)：查找速度極快（O(1)）,查找效率與元素個(gè)數(shù)n無(wú)關(guān)！639.4.1哈希表的概念例1：若將學(xué)生信息按如下方式存入計(jì)算機(jī)，如：將2001011810201的所有信息存入V[01]單元；將2001011810202的所有信息存入V[02]單元；……將2001011810231的所有信息存入V[31]單元。欲查找學(xué)號(hào)為2001011810216的信息，便可直接訪問(wèn)V[16]！64例2：

有數(shù)據(jù)元素序列(14，23，39，9，25，11)，若規(guī)定每個(gè)元素k的存儲(chǔ)地址H（k）＝k，請(qǐng)畫(huà)出存儲(chǔ)結(jié)構(gòu)圖。解：根據(jù)散列函數(shù)H（k）＝k，可知元素14應(yīng)當(dāng)存入地址為14的單元，元素23應(yīng)當(dāng)存入地址為23的單元，……，對(duì)應(yīng)散列存儲(chǔ)表（哈希表）如下：地址…9…11…14…232425…39…內(nèi)(k)稱為散列函數(shù)9.4.1哈希表的概念65根據(jù)存儲(chǔ)時(shí)用到的散列函數(shù)H(k)表達(dá)式，迅即可查到結(jié)果！例如，查找key=9,則訪問(wèn)H(9)=9號(hào)地址，若內(nèi)容為9則成功；若查不到，應(yīng)當(dāng)設(shè)法返回一個(gè)特殊值，例如空指針或空記錄。明顯缺點(diǎn)：空間效率低如何解決？討論：如何進(jìn)行散列查找？9.4.1哈希表的概念66選取某個(gè)函數(shù)，依該函數(shù)按關(guān)鍵字計(jì)算元素的存儲(chǔ)位置并按此存放；查找時(shí)也由同一個(gè)函數(shù)對(duì)給定值k計(jì)算地址，將k與地址中內(nèi)容進(jìn)行比較，確定查找是否成功。Hash查找專業(yè)術(shù)語(yǔ)哈希方法(雜湊法)哈希方法中使用的轉(zhuǎn)換函數(shù)稱為哈希函數(shù)(雜湊函數(shù))按上述思想構(gòu)造的表稱為哈希表(雜湊表)哈希表(雜湊表)哈希函數(shù)(雜湊函數(shù))67通常關(guān)鍵碼的集合比哈希地址集合大得多，因而經(jīng)過(guò)哈希函數(shù)變換后，可能將不同的關(guān)鍵碼映射到同一個(gè)哈希地址上，這種現(xiàn)象稱為沖突。Hash查找專業(yè)術(shù)語(yǔ)沖突68有6個(gè)元素的關(guān)鍵碼分別為：（14，23，39，9，25，11）。選取關(guān)鍵碼與元素位置間的函數(shù)為H(k)=kmod7通過(guò)哈希函數(shù)對(duì)6個(gè)元素建立哈希表：253923914沖突現(xiàn)象舉例：6個(gè)元素用7個(gè)地址應(yīng)該足夠!H(14)=14%7=011H(25)=25%7=4H(11)=11%7=4有沖突！01234569.4.1哈希表的概念69所以，哈希方法必須解決以下兩個(gè)問(wèn)題：1）構(gòu)造好的哈希函數(shù)（a）所選函數(shù)盡可能簡(jiǎn)單，以便提高轉(zhuǎn)換速度；（b）所選函數(shù)對(duì)關(guān)鍵碼計(jì)算出的地址，應(yīng)在哈希地址內(nèi)集中并大致均勻分布，以減少空間浪費(fèi)。2）制定一個(gè)好的解決沖突的方案查找時(shí)，如果從哈希函數(shù)計(jì)算出的地址中查不到關(guān)鍵碼，則應(yīng)當(dāng)依據(jù)解決沖突的規(guī)則，有規(guī)律地查詢其它相關(guān)單元。在哈希查找方法中，沖突是不可能避免的，只能盡可能減少。9.4.1哈希表的概念709.4.2

哈希函數(shù)的構(gòu)造方法要求一：n個(gè)數(shù)據(jù)原僅占用n個(gè)地址，雖然散列查找是以空間換時(shí)間，但仍希望散列的地址空間盡量小。要求二：無(wú)論用什么方法存儲(chǔ)，目的都是盡量均勻地存放元素，以避免沖突。719.4.2

哈希函數(shù)的構(gòu)造方法常用的哈希函數(shù)構(gòu)造方法有：直接定址法除留余數(shù)法乘余取整法數(shù)字分析法平方取中法折疊法隨機(jī)數(shù)法72Hash(key)=a·key+b(a、b為常數(shù))優(yōu)點(diǎn)：以關(guān)鍵碼key的某個(gè)線性函數(shù)值為哈希地址，不會(huì)產(chǎn)生沖突.缺點(diǎn)：要占用連續(xù)地址空間，空間效率低。

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

哈希函數(shù)的構(gòu)造方法73Hash(key)=keymodp(p是一個(gè)整數(shù))特點(diǎn)：以關(guān)鍵碼除以p的余數(shù)作為哈希地址。關(guān)鍵：如何選取合適的p？技巧：若設(shè)計(jì)的哈希表長(zhǎng)為m，則一般取p≤m且為質(zhì)數(shù)（也可以是合數(shù)，但不能包含小于20的質(zhì)因子）。2、除留余數(shù)法（重點(diǎn))9.4.2

哈希函數(shù)的構(gòu)造方法74Hash(key)=B*(A*keymod1)

(A、B均為常數(shù)，且0<A<1，B為整數(shù))特點(diǎn)：以關(guān)鍵碼key乘以A，取其小數(shù)部分，然后再放大B倍并取整，作為哈希地址。3、乘余取整法（A*keymod1）就是取A*key的小數(shù)部分例：欲以學(xué)號(hào)最后兩位作為地址，則哈希函數(shù)應(yīng)為：

H(k)=100*(0.01*k%1)其實(shí)也可以用法2實(shí)現(xiàn)：H(k)=k%1009.4.2

哈希函數(shù)的構(gòu)造方法75特點(diǎn)：選用關(guān)鍵字的某幾位組合成哈希地址。選用原則應(yīng)當(dāng)是：各種符號(hào)在該位上出現(xiàn)的頻率大致相同。34705243491487348269634852703486305349805834796713473919例：有一組（例如80個(gè)）關(guān)鍵碼，其樣式如下：4、數(shù)字分析法討論：①第1、2位均是“3和4”，第3位也只有“7、8、9”，因此，這幾位不能用，余下四位分布較均勻，可作為哈希地址選用。位號(hào)：①②③④⑤⑥⑦②若哈希地址取兩位（因元素僅80個(gè)），則可取這四位中的任意兩位組合成哈希地址，也可以取其中兩位與其它兩位疊加求和后，取低兩位作哈希地址。9.4.2

哈希函數(shù)的構(gòu)造方法76特點(diǎn)：對(duì)關(guān)鍵碼平方后，按哈希表大小，取中間的若干位作為哈希地址。理由：因?yàn)橹虚g幾位與數(shù)據(jù)的每一位都相關(guān)。例：2589的平方值為6702921，可以取中間的029為地址。5、平方取中法9.4.2

哈希函數(shù)的構(gòu)造方法776、折疊法特點(diǎn)：將關(guān)鍵碼自左到右分成位數(shù)相等的幾部分（最后一部分位數(shù)可以短些），然后將這幾部分疊加求和，并按哈希表表長(zhǎng)，取后幾位作為地址。適用于：每一位上各符號(hào)出現(xiàn)概率大致相同的情況。法1：移位法──將各部分的最后一位對(duì)齊相加。法2：間界疊加法──從一端向另一端沿分割界來(lái)回折疊后，最后一位對(duì)齊相加。例：元素42751896,用法1：427＋518＋96=1041

用法2：42751896—>724+518+69=13119.4.2

哈希函數(shù)的構(gòu)造方法787、隨機(jī)數(shù)法Hash(key)=random(key)(random為偽隨機(jī)函數(shù))適用于：關(guān)鍵字長(zhǎng)度不等的情況。造表和查找都很方便。9.4.2

哈希函數(shù)的構(gòu)造方法79①執(zhí)行速度（即計(jì)算哈希函數(shù)所需時(shí)間）；②關(guān)鍵字的長(zhǎng)度；③哈希表的大?。虎荜P(guān)鍵字的分布情況；⑤查找頻率。小結(jié)：構(gòu)造哈希函數(shù)的原則：9.4.2

哈希函數(shù)的構(gòu)造方法809.4.3、沖突處理方法（重點(diǎn)與考點(diǎn)）常見(jiàn)的沖突處理方法有開(kāi)放定址法（開(kāi)地址法）鏈地址法（拉鏈法）再哈希法（雙哈希函數(shù)法）建立一個(gè)公共溢出區(qū)811、開(kāi)放定址法（開(kāi)地址法）設(shè)計(jì)思路：有沖突時(shí)就去尋找下一個(gè)空的哈希地址，只要哈希表足夠大，空的哈希地址總能找到，并將數(shù)據(jù)元素存入。821、開(kāi)放定址法（開(kāi)地址法）Hi=(Hash(key)+di)modm(1≤i<m)

其中：

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

m為哈希表長(zhǎng)度

di

為增量序列1，2，…m-1，且di=i

（1）線性探測(cè)法含義：一旦沖突，就找附近（下一個(gè)）空地址存入。83關(guān)鍵碼集為{47，7，29，11，16，92，22，8，3}，設(shè)：哈希表表長(zhǎng)為m=11；哈希函數(shù)為Hash(key)=keymod11；擬用線性探測(cè)法處理沖突。建哈希表如下：解釋：①47、7是由哈希函數(shù)得到的沒(méi)有沖突的哈希地址；012345678910477△▲△△例：291116922283②Hash(29)=7，哈希地址有沖突，需尋找下一個(gè)空的哈希地址：由H1=(Hash(29)+1)mod11=8，哈希地址8為空，因此將29存入。③另外，22、8、3同樣在哈希地址上有沖突，也是由H1找到空的哈希地址的。其中3還連續(xù)移動(dòng)了兩次（二次聚集）84線性探測(cè)法的優(yōu)點(diǎn)：只要哈希表未被填滿，保證能找到一個(gè)空地址單元存放有沖突的元素；線性探測(cè)法的缺點(diǎn)：可能使第i個(gè)哈希地址的同義詞存入第i+1個(gè)哈希地址，這樣本應(yīng)存入第i+1個(gè)哈希地址的元素變成了第i+2個(gè)哈希地址的同義詞，……，因此，可能出現(xiàn)很多元素在相鄰的哈希地址上“堆積”起來(lái)，大大降低了查找效率。解決方案：可采用二次探測(cè)法或偽隨機(jī)探測(cè)法，以改善“堆積”問(wèn)題。1、開(kāi)放定址法（開(kāi)地址法）

（1）線性探測(cè)法85仍舉上例，改用二次探測(cè)法處理沖突，建表如下：012345678910112234792167298△▲△△注：只有3這個(gè)關(guān)鍵碼的沖突處理與上例不同，Hash(3)=3，哈希地址上沖突，由H1=(Hash(3)+12)mod11=4，仍然沖突；H2=(Hash(3)-12)mod11=2，找到空的哈希地址，存入。（2）二次探測(cè)法Hi=(Hash(key)±di)modm其中：Hash(key)為哈希函數(shù)

m為哈希表長(zhǎng)度，m要求是某個(gè)4k+3的質(zhì)數(shù)；

di為增量序列12，-12，22，-22，…，q2

1、開(kāi)放定址法（開(kāi)地址法）862、鏈地址法(拉鏈法）基本思想：將具有相同哈希地址的記錄鏈成一個(gè)單鏈表，m個(gè)哈希地址就設(shè)m個(gè)單鏈表，然后用一個(gè)數(shù)組將m個(gè)單鏈表的表頭指針存儲(chǔ)起來(lái)，形成一個(gè)動(dòng)態(tài)的結(jié)構(gòu)。872、鏈地址法(拉鏈法）

設(shè){47,7,29,11,16,92,22,8,3,50,37,89,10}的哈希函數(shù)為：Hash(key)=keymod11，用拉鏈法處理沖突，則建表如右圖所示。例：

01234567891022118934737922971650810有沖突的元素可以插在表尾,也可以插在表頭。883、再哈希法（雙哈希函數(shù)法）Hi=RHi(key)i=1,2,…，kRHi均是不同的哈希函數(shù)，當(dāng)產(chǎn)生沖突時(shí)就計(jì)算另一個(gè)哈希函數(shù)，直到?jīng)_突不再發(fā)生。優(yōu)點(diǎn)：不易產(chǎn)生聚集；缺點(diǎn)：增加了計(jì)算時(shí)間。894.建立一個(gè)公共溢出區(qū)思路：除設(shè)立哈?；颈硗?，另設(shè)立一個(gè)溢出向量表。所有關(guān)鍵字和基本表中關(guān)鍵字為同義詞的記錄，不管它們由哈希函數(shù)得到的地址是什么，一旦發(fā)生沖突，都填入溢出表。909.4.4哈希表的查找及分析明確：散列函數(shù)沒(méi)有“萬(wàn)能”通式（雜湊法），要根據(jù)元素集合的特性而分別構(gòu)造。算法：見(jiàn)教材P2591：哈希查找的速度是否為真正的O（1）？答：不是。由于沖突的產(chǎn)生，使得哈希表的查找過(guò)程仍然要進(jìn)行比較，仍然要以平均查找長(zhǎng)度ASL來(lái)衡量。919.4.4哈希表的查找及分析2：“沖突”是不是特別討厭？答：不一定！正因?yàn)橛袥_突，使得文件加密后無(wú)法破譯?。▎蜗蛏⒘泻瘮?shù)不可逆，常用于數(shù)字簽名和間接加密）。典型應(yīng)用：md5散列算法哈希表特點(diǎn)：源文件稍稍改動(dòng)，會(huì)導(dǎo)致哈希表變動(dòng)很大。923散列存儲(chǔ)的查找效率到底是多少？答：ASL與裝填因子有關(guān)！既不是嚴(yán)格的O(1)，也不是O(n)應(yīng)盡量選擇一個(gè)合適的，以降低ASL的長(zhǎng)度9.4.4哈希表的查找及分析9.4.5哈希應(yīng)用93HASH函數(shù)，又稱雜湊函數(shù)，是在信息安全領(lǐng)域有廣泛和重要應(yīng)用的密碼算法，它有一種類似于指紋的應(yīng)用。

在網(wǎng)絡(luò)安全協(xié)議中，雜湊函數(shù)用來(lái)處理電子簽名，將冗長(zhǎng)的簽名文件壓縮為一段獨(dú)特的數(shù)字信息，像指紋鑒別身份一樣保證原來(lái)數(shù)字簽名文件的合法性和安全性。

1、數(shù)字簽名（數(shù)字手?。?.4.5哈希應(yīng)用94

SHA-1和MD5都是目前最常用的雜湊函數(shù)。經(jīng)過(guò)這些算法的處理，原始信息即使只更動(dòng)一個(gè)字母，對(duì)應(yīng)的壓縮信息也會(huì)變?yōu)榻厝徊煌摹爸讣y”，這就保證了經(jīng)過(guò)處理信息的唯一性。為電子商務(wù)等提供了數(shù)字認(rèn)證的可能性。1、數(shù)字簽名（數(shù)字手?。?5md5散列算法——信息-摘要算法（1991年）md5的典型應(yīng)用是對(duì)一段信息（message）產(chǎn)生一個(gè)128位的信息摘要（message-digest），以防止被篡改。md5以512位分組來(lái)處理輸入的信息，且每一分組又被劃分為16個(gè)32位子分組，經(jīng)過(guò)了一系列的處理后，算法的輸出由四個(gè)32位(鏈接變量參數(shù))分組組成，將這四個(gè)32位分組級(jí)聯(lián)后將生成一個(gè)128位散列值。message-digestalgorithm）——用于加解密和數(shù)字簽名9.4.5哈希應(yīng)用96例1：在unix系統(tǒng)下，有很多軟件在下載的時(shí)候都有一個(gè)文件名相同、文件擴(kuò)展名為.md5的文件，在這個(gè)文件中通常只有一行文本，大致結(jié)構(gòu)如：

md5(file)=0ca175b9c0f726a831d895e269332461這就是file文件的數(shù)字簽名。9.4.5哈希應(yīng)用97例2：md5用于BBS登錄時(shí)的身份認(rèn)證在BBS服務(wù)器上，用戶的密碼都是以md5（或其它類似的算法）經(jīng)加密后存儲(chǔ)在文件系統(tǒng)中。當(dāng)用戶登錄的時(shí)候，系統(tǒng)把用戶輸入的密碼計(jì)算成md5值，然后再去和預(yù)存在服務(wù)器中的md5值進(jìn)行比較，進(jìn)而確定輸入的密碼是否正確。優(yōu)點(diǎn)：系統(tǒng)在不知用戶密碼明碼的情況下就可以確定用戶登錄系統(tǒng)的合法性。這不但可以避免用戶的密碼被具有系統(tǒng)管理員權(quán)限的用戶知道，而且還在一定程度上增加了密碼被破解的難度。9.4.5哈希應(yīng)用98例3：?jiǎn)渭兊臄?shù)據(jù)校驗(yàn)下載光盤(pán)鏡像文件時(shí)一般會(huì)有一個(gè)MD5文件記錄校驗(yàn)和，以防止下載600MB的文件出現(xiàn)錯(cuò)誤導(dǎo)致軟件無(wú)法安裝，這在Linux/FreeBSD等通過(guò)網(wǎng)絡(luò)發(fā)布的光盤(pán)安裝系統(tǒng)中常用。9.4.5哈希應(yīng)用99現(xiàn)在使用的重要計(jì)算機(jī)安全協(xié)議，如SSL，PGP都用雜湊函數(shù)來(lái)進(jìn)行簽名。但是，如果有人一旦找到兩個(gè)文件可以產(chǎn)生相同的壓縮值，就可以偽造簽名，給網(wǎng)絡(luò)安全領(lǐng)域帶來(lái)巨大隱患。

9.4.5哈希應(yīng)用9.5B-樹(shù)和B+樹(shù)1、B-樹(shù)2B+樹(shù)9.5.1B-樹(shù)

一B-樹(shù)的定義B-樹(shù)是一種平衡的多路查找樹(shù)。一棵m階的B-樹(shù)，或?yàn)榭諛?shù)，或?yàn)闈M足下列特性的m叉樹(shù)：

1．樹(shù)中每個(gè)結(jié)點(diǎn)至多有m棵子樹(shù)，m-1個(gè)關(guān)鍵字；

2．若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少有兩棵子樹(shù)；

3．除根之外的所有非終端結(jié)點(diǎn)至少有棵子樹(shù)，至少有-1個(gè)關(guān)鍵字；4．所有的非終端結(jié)點(diǎn)中包含下列信息數(shù)據(jù)：

(n,A0,K1,A1,K2,A2,…,Kn,An)其中：Ki(i=1,…,n)為關(guān)鍵字，且Ki<Ki+1(i=1,…,n-1)；

Ai(i=1,…,n)為指向子樹(shù)根結(jié)點(diǎn)的指針，且指針Ai-1所指子樹(shù)中所有結(jié)點(diǎn)的關(guān)鍵字均小于Ki(i=1,…,n)，An所指子樹(shù)中所有結(jié)點(diǎn)的關(guān)鍵字均大于Kn，n

為關(guān)鍵字的個(gè)數(shù)（或n＋1為子樹(shù)個(gè)數(shù)）。一、B-樹(shù)的定義9.5.1B-樹(shù)

5．所有的葉子結(jié)點(diǎn)都出現(xiàn)在同一層次上，并且不帶信息（可以看作是外部結(jié)點(diǎn)或查找失敗的結(jié)點(diǎn)，實(shí)際上這些結(jié)點(diǎn)不存在，指向這些結(jié)點(diǎn)的指針為空）。一、B-樹(shù)的定義9.5.1B-樹(shù)

二、圖形表示圖1 一棵4階的B-樹(shù)tabcfegdh135111243781181271391993475364FFFFFFFFFFFF結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)為1<=n<=3

子樹(shù)數(shù)量范圍為2<=k<=49.5.1B-樹(shù)

從根結(jié)點(diǎn)出發(fā)，沿指針?biāo)阉鹘Y(jié)點(diǎn)和在結(jié)點(diǎn)內(nèi)進(jìn)行順序（或折半）查找兩個(gè)過(guò)程交叉進(jìn)行。三、查找

若查找成功，則返回指向被查關(guān)鍵字所在結(jié)點(diǎn)的指針和關(guān)鍵字在結(jié)點(diǎn)中的位置；若查找不成功，則返回插入位置。9.5.1B-樹(shù)

#define m 3 //B-樹(shù)的階，暫設(shè)為3typedefstructBTNode{ int keynum

//結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)，即結(jié)點(diǎn)的大小

structBTNode*parent;//指向雙親結(jié)點(diǎn)

KeyType key[m+1];

//關(guān)鍵字向量，0號(hào)單元未用

structBTNode*ptr[m+1]; //子樹(shù)指針向量

Record *recptr[m+1];

//記錄指針向量，0號(hào)單元未用

}BTNode,*BTree;B-樹(shù)結(jié)構(gòu)體B-樹(shù)查詢結(jié)構(gòu)體typedefstruct{ BTNode *pt; //指向找到的結(jié)點(diǎn)

int i; //1..m，在結(jié)點(diǎn)中的關(guān)鍵字序號(hào)

int tag; //1:查找成功，0:查找失敗

}Result; //B-樹(shù)的查找結(jié)果類型四、B-樹(shù)的查找1．算法思想：在B-樹(shù)上進(jìn)行查找的過(guò)程是一個(gè)順著指針查找結(jié)點(diǎn)和在結(jié)點(diǎn)的關(guān)鍵字中進(jìn)行查找交叉進(jìn)行的過(guò)程。9.5.1B-樹(shù)

四、B-樹(shù)的查找2．算法代碼9.5.1B-樹(shù)

3．查找分析從上述算法可見(jiàn)，在B-樹(shù)上進(jìn)行查找包含兩種基本操作：a.在B-樹(shù)中找結(jié)點(diǎn)（操作在磁盤(pán)上進(jìn)行）；b.在結(jié)點(diǎn)中找關(guān)鍵字（操作在內(nèi)存中進(jìn)行）。顯然，在磁盤(pán)上進(jìn)行一次查找比在內(nèi)存中進(jìn)行一次查找耗費(fèi)時(shí)間多得多，因此，在磁盤(pán)上進(jìn)行查找的次數(shù)、即待查關(guān)鍵字所在結(jié)點(diǎn)在B-樹(shù)上的層次數(shù)，是決定B-樹(shù)查找效率的首要因素。

9.5.1B-樹(shù)

四、B-樹(shù)的查找

根據(jù)B-樹(shù)的定義，第一層至少有1個(gè)結(jié)點(diǎn)；第二層至少有2個(gè)結(jié)點(diǎn)；棵子樹(shù)，則第三層至少有2()個(gè)結(jié)點(diǎn)；……；依次類推，第l＋1層至少有)l-1由于除根之外的每個(gè)非終端結(jié)點(diǎn)至少有2(個(gè)結(jié)點(diǎn)。而l＋1層的結(jié)點(diǎn)為葉子結(jié)點(diǎn)。若m階B-樹(shù)中具有N個(gè)關(guān)鍵字，則葉子結(jié)點(diǎn)即查找不成功的結(jié)點(diǎn)為N＋1，由此有：推得：3．查找分析9.5.1B-樹(shù)

四、B-樹(shù)的查找3．查找分析這就是說(shuō)，在含有N個(gè)關(guān)鍵字的B-樹(shù)上進(jìn)行查找時(shí)，從根結(jié)點(diǎn)到關(guān)鍵字所在結(jié)點(diǎn)的路徑上涉及的結(jié)點(diǎn)數(shù)不超過(guò)9.5.1B-樹(shù)

四、B-樹(shù)的查找五、B-樹(shù)的插入2．算法思想：由于B-樹(shù)結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)必須

。因此，每次插入一個(gè)關(guān)鍵字不是在樹(shù)中添加一個(gè)葉子結(jié)點(diǎn)，而是首先在最低層的某個(gè)非終端結(jié)點(diǎn)中添加一個(gè)關(guān)鍵字，若該結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)不超過(guò)m-1，則插入完成，否則要產(chǎn)生結(jié)點(diǎn)的“分裂”。9.5.1B-樹(shù)

五、B-樹(shù)的插入

一般情況下，結(jié)點(diǎn)可如下實(shí)現(xiàn)“分裂”：假設(shè)p結(jié)點(diǎn)中已有m-1個(gè)關(guān)鍵字，當(dāng)插入一個(gè)關(guān)鍵字之后，結(jié)點(diǎn)中含有信息為：m,A0,(K1,A1),…,(Km,Am)且其中Ki<Ki+1，1≤i<m，此時(shí)可將p結(jié)點(diǎn)分裂為p和p’兩個(gè)結(jié)點(diǎn)，其中p結(jié)點(diǎn)中含有信息為：

9.5.1B-樹(shù)

五、B-樹(shù)的插入p’結(jié)點(diǎn)中含有信息：而關(guān)鍵字指針p’一起插入到p的雙親結(jié)點(diǎn)中。9.5.1B-樹(shù)

3．例子例如，圖2所示為3階B-樹(shù)（圖中略去F結(jié)點(diǎn)，即葉子結(jié)點(diǎn)），假設(shè)需一次插入關(guān)鍵字30，26，85和7。(a) bta45b24c312d37f50h100g6170e5390圖2一棵2-3樹(shù)五、B-樹(shù)的插入bta45b24c312df50h100g6170e53903037(b)五、B-樹(shù)的插入bta45b24c312df50h100g6170e5390263037(c)五、B-樹(shù)的插入bta45b2430c312df50h100g6170e53903726d’(d)五、B-樹(shù)的插入bta45b2430c312df50h100g617085e53903726d’(e)五、B-樹(shù)的插入(f)bta45b2430c312df50h100g61e5370903726d’85g’五、B-樹(shù)的插入(g)bta4570b2430c312df50h100g61e533726d’85g’e’90五、B-樹(shù)的插入(h)bta4570b72430c3df50h100g61e533726d’85g’e’9012c’五、B-樹(shù)的插入bta244570b7c3df50h100g61e5326d’85g’e’9012c’30b’37(i)五、B-樹(shù)的插入(j)bta70b7c3df50h100g61e5326d’85g’e’9012c’30b’ma’452437(a)一棵2-3樹(shù)；(b)插入30之后；

(c)、(d)插入26之后；

(e)~(g) 插入85之后；(h)~(j)插入7之后；圖2 在B-樹(shù)中進(jìn)行插入（省略葉子結(jié)點(diǎn)）五、B-樹(shù)的插入

六、B-樹(shù)的刪除1．算法思想：在B-樹(shù)中刪除一個(gè)關(guān)鍵字，則首先應(yīng)找到該關(guān)鍵字所在結(jié)點(diǎn)，并從中刪除之。（1）若所刪關(guān)鍵字為非終端結(jié)點(diǎn)中的Ki，則以指針Ai所指子樹(shù)中的最小關(guān)鍵字Y替代Ki，然后在相應(yīng)的結(jié)點(diǎn)中刪去Y。（2）若所刪關(guān)鍵字在最下層非終端結(jié)點(diǎn)中。有下列3種情況：a．被刪關(guān)鍵字所在結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目不小于，則只需從該結(jié)點(diǎn)中刪去該關(guān)鍵字Ki