0-1開課

數(shù)據(jù)結(jié)構(gòu)與算法DATASTRUCTURE&ALGORITHM天津理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院第八章查找1基本概念2線性表的查找3樹表的查找4散列表的查找8.1查找的基本概念數(shù)據(jù)元素、結(jié)點(diǎn)、頂點(diǎn)關(guān)鍵碼：可以標(biāo)識一個(gè)記錄的某個(gè)數(shù)據(jù)項(xiàng)鍵值：關(guān)鍵碼的值主關(guān)鍵碼：可以唯一標(biāo)識一個(gè)記錄的關(guān)鍵碼查找的結(jié)果：若在查找集合中找到了與給定值相匹配的記錄，則稱查找成功；否則，稱查找失敗查找：在相同類型的記錄構(gòu)成的集合中找出滿足給定條件的記錄給定的查找條件可能是多種多樣的，把查找條件限制為“匹配”，即查找關(guān)鍵碼等于給定值的記錄靜態(tài)查找：不涉及插入和刪除操作的查找動(dòng)態(tài)查找要求插入、刪除、查找均有較好的效率，適用于：查找與插入和刪除操作在同一個(gè)階段進(jìn)行例如：當(dāng)查找成功時(shí)，要?jiǎng)h除查找到的記錄當(dāng)查找不成功時(shí)，要插入被查找的記錄動(dòng)態(tài)查找：涉及插入和刪除操作的查找靜態(tài)查找只注重查找效率，適用于：（1）查找集合一經(jīng)生成，便只對其進(jìn)行查找，而不進(jìn)行插入和刪除操作（2）經(jīng)過一段時(shí)間的查找之后，集中地進(jìn)行插入和刪除等修改操作靜態(tài)查找與動(dòng)態(tài)查找查找結(jié)構(gòu)查找結(jié)構(gòu)：面向查找操作的數(shù)據(jù)結(jié)構(gòu)，即查找基于的數(shù)據(jù)結(jié)構(gòu)查找結(jié)構(gòu)

查找方法

（1）幾乎所有的數(shù)據(jù)結(jié)構(gòu)都提供了查找作為基本操作，但對于數(shù)據(jù)結(jié)構(gòu)整體來說，查找并不是最重要的操作（3）數(shù)據(jù)結(jié)構(gòu)+算法=程序：不同的查找結(jié)構(gòu)，會獲得不同的查找效率（2）對于查找結(jié)構(gòu)來說，查找是最重要的基本操作，重要的是查找效率已經(jīng)有了數(shù)據(jù)結(jié)構(gòu)的概念，為什么要強(qiáng)調(diào)查找結(jié)構(gòu)？線性表：適用于靜態(tài)查找，順序查找、折半查找等技術(shù)樹表：適用于動(dòng)態(tài)查找，二叉排序樹的查找技術(shù)散列表：靜態(tài)查找和動(dòng)態(tài)查找均適用，采用散列技術(shù)集合集合理解起來，集合最常用的表示法是列舉法，習(xí)慣上，也稱為表查找結(jié)構(gòu)查找基于的數(shù)據(jù)模型是什么？都是把集合組織成XXX表，為什么？平均查找長度和關(guān)鍵碼的比較次數(shù)其中：n：問題規(guī)模，查找集合中的記錄個(gè)數(shù)

pi：查找第i個(gè)記錄的概率ci：查找第i個(gè)記錄所需的關(guān)鍵碼的比較次數(shù)ASL?==niiicp1平均查找長度：查找算法進(jìn)行的關(guān)鍵碼比較次數(shù)的數(shù)學(xué)期望值pi與算法無關(guān)，取決于具體應(yīng)用ci取決于算法如果pi是已知的，則平均查找長度只是問題規(guī)模的函數(shù)關(guān)鍵碼的比較次數(shù)與哪些因素有關(guān)呢？如何評價(jià)查找算法的效率呢？8.2線性表的查找無序表的查找——順序查找有序表的查找——折半查找分塊查找順序查找（線性查找）線性表有順序和鏈?zhǔn)絻煞N存儲結(jié)構(gòu)。靜態(tài)查找表的順序存儲結(jié)構(gòu)：

typedefstruct{KeyTypekey;OtherTypeother;}ElemType;適用的數(shù)據(jù)結(jié)構(gòu)：

順序表、線性鏈表基本思想：從線性表的一端向另一端逐個(gè)將記錄與給定值進(jìn)行比較，若相等，則查找成功，給出該記錄在表中的位置；若整個(gè)表檢測完仍未找到與給定值相等記錄，則查找失敗，給出失敗信息順序查找算法實(shí)現(xiàn)i

101524

6

12

35

40

98

550123456789例：查找35，查找25intS_search(ElemTypeST[]，KeyTypek){for(i=n;i>0&&ST[i].key!=k；i--)；/*從表尾端向前找*/returni；

/*返回k元素的下標(biāo)，否則返回0*/}順序查找的改進(jìn)：設(shè)置“哨兵”，就是待查值，放在查找方向的盡頭處，免去了每一次比較后都要判斷查找位置是否越界i25查找方向intS_search(ElemTypeST[]，KeyTypek){ST[0].key=k；/作為監(jiān)測哨兵*/for(i=n;ST[i].key!=k；i--)；/*從表尾端向前找*/returni；

/*返回k元素的下標(biāo)，否則返回0*/}順序查找的性能查找成功：查找不成功：特別是當(dāng)待查找集合中元素較多時(shí)，不推薦使用順序查找順序查找的缺點(diǎn)：查找效率較低（1）對表中記錄的存儲沒有任何要求，順序存儲和鏈接存儲均可（2）對表中記錄的有序性也沒有要求，無論記錄是否按關(guān)鍵碼有序均可順序查找的優(yōu)點(diǎn)：算法簡單而且使用面廣改進(jìn)順序查找許多情況下，查找表中數(shù)據(jù)元素的查找概率是不相等的。若事先已知各元素的查找概率，查找表可依據(jù)查找概率越高，比較次數(shù)越少；查找概率越低，比較次數(shù)就較多的原則來存儲數(shù)據(jù)元素，從而降低ASL。若事先未知各元素的查找概率，可在每次查找到一個(gè)元素時(shí)，將它與后繼(前驅(qū))元素對調(diào)位置，或直接移至表尾(表頭)。折半查找（二分查找）

[r1………rmid-1]rmid[rmid+1………rn]k（mid=(1+n)/2）如果k<rmid查找左半?yún)^(qū)如果k>rmid查找右半?yún)^(qū)適用的數(shù)據(jù)結(jié)構(gòu)：

順序存儲的有序表基本思想：在有序表（假設(shè)為遞增有序表）中，取中間記錄作為比較對象，若給定值與中間記錄相等，則查找成功；若給定值小于中間記錄，則在有序表的左半?yún)^(qū)繼續(xù)查找；若給定值大于中間記錄，則在有序表的右半?yún)^(qū)繼續(xù)查找。不斷重復(fù)上述過程，直到查找成功，或查找區(qū)域無記錄，查找失敗。折半查找算法實(shí)現(xiàn)假設(shè)靜態(tài)查找表ST遞增有序，折半查找過程為：①low=1；high=length；//設(shè)置初始區(qū)間②若low>high,返回查找失敗信息

//當(dāng)前查找區(qū)間為空，查找失敗③若low≤high，mid=

(low+high)/2

;//取中點(diǎn)

a.若k<ST[mid].key，high=mid-1；轉(zhuǎn)②

//查找在左半?yún)^(qū)進(jìn)行

b.若k>ST[mid].key，low=mid+1；轉(zhuǎn)②

//查找在右半?yún)^(qū)進(jìn)行

c.若k=ST[mid].key，返回元素在表中位置

//查找成功運(yùn)行實(shí)例mid=4但key=9<10,向左查找成功的情況：數(shù)組ST如下圖所示有序查找9數(shù)組ST：遞增序ST[i].Key<=ST[I+1].Key;

查找范圍：low（低下標(biāo)）=1;high（高下標(biāo)）=7（初始時(shí)為最大下標(biāo)n）;

比較對象：中點(diǎn)元素，其下標(biāo)地址為mid=(low+high)/2=4012key4891011131934567high=7low=1查找成功的情況：數(shù)組ST如下圖所示有序

查找9數(shù)組ST：遞增序ST[i].Key<=ST[I+1].Key;查找范圍：low（低下標(biāo)）=1;high（高下標(biāo)）=3;012key4891011131934567low=1high=3（mid-1）比較對象：中點(diǎn)元素，其下標(biāo)地址為mid=（low+high）/2=2mid=2;但key=9>8,向右運(yùn)行實(shí)例查找成功的情況：數(shù)組ST如下圖所示有序

查找9數(shù)組ST：遞增序ST[i].Key<=ST[I+1].Key;查找范圍：low（低下標(biāo)）=3;high（高下標(biāo)）=3;比較對象：中點(diǎn)元素，其下標(biāo)地址為mid=（low+high）/2=3012key4891011131934567high=3low=3（mid+1）mid=3;但key=9中點(diǎn)值也為9，找到運(yùn)行實(shí)例mid=4但key=5<10,向左查找不成功的情況：數(shù)組ST如下圖所示有序查找5數(shù)組ST：遞增序ST[i].Key<=ST[I+1].Key;

查找范圍：low（低下標(biāo)）=1;high（高下標(biāo)）=7（初始時(shí)為最大下標(biāo)n)

比較對象：中點(diǎn)元素，其下標(biāo)地址為mid=（low+high）/2high=7low=1012key4891011131934567運(yùn)行實(shí)例查找不成功的情況：數(shù)組ST如下圖所示有序查找5數(shù)組ST：遞增序ST[i].Key<=ST[I+1].Key;

查找范圍：low（低下標(biāo)）=1;high（高下標(biāo)）=3

;

比較對象：中點(diǎn)元素，其下標(biāo)地址為mid=（low+high）/2=2mid=2,但key=5<8,向左012key4891011131934567low=1high=3（mid-1）運(yùn)行實(shí)例查找不成功的情況：數(shù)組ST如下圖所示有序查找5數(shù)組ST：遞增序ST[i].Key<=ST[I+1].Key;

查找范圍：low（低下標(biāo)）=1;high（高下標(biāo)）=1;

比較對象：中點(diǎn)元素，其下標(biāo)地址為mid=（low+high）/2=1012key4891011131934567high=1（mid-1）mid=1;

但key=5>4,向右low=1運(yùn)行實(shí)例查找不成功的情況：數(shù)組ST如下圖所示有序查找5數(shù)組ST：遞增序ST[i].Key<=ST[I+1].Key;

查找范圍：low（低下標(biāo)）=1;high（高下標(biāo)）=1;

比較對象：中點(diǎn)元素，其下標(biāo)地址為mid=（low+high）/2=1012key4891011131934567high=1mid=1;

但key=5>4,向右low=2(mid+1）失敗條件：low>high;處于間隙中的鍵值導(dǎo)致這種情況！運(yùn)行實(shí)例非遞歸算法intBinSearch1(intr[],intn,intk)

/*查找集合存儲在r[1]~r[n]*/{}

return0;

/*查找失敗，返回0*/intmid,low=1,high=n;

/*初始查找區(qū)間是[1,n]*/while(low<=high)

/*當(dāng)區(qū)間存在時(shí)*/{}mid=(low+high)/2;if(k<r[mid])high=mid-1;elseif(k>r[mid])low=mid+1;elsereturnmid;

/*查找成功，返回元素序號*/遞歸算法

714182123293135380123456789lowhigh例：查找18查找區(qū)間[1,9]midhigh查找區(qū)間[1,4]intBinSearch2(intr[],intlow,inthigh,intk){}else{

mid=(low+high)/2;

if(k<r[mid])returnBinSearch2(r,low,mid-1,k);elseif(k>r[mid])returnBinSearch2(r,mid+1,high,k);

elsereturnmid;

/*查找成功，返回序號*/}intmid;if(low>high)return0;

/*遞歸的邊界條件*/判定樹判定樹（折半查找判定樹）：描述折半查找判定過程的二叉樹（1）當(dāng)low＞high時(shí)，判定樹為空；（2）當(dāng)low≤high時(shí)，判定樹的根結(jié)點(diǎn)是有序表中序號為mid=(low+high)/2的記錄，根結(jié)點(diǎn)的左子樹是與有序表r[low]~r[mid-1]相對應(yīng)的判定樹，根結(jié)點(diǎn)的右子樹是與有序表r[mid+1]~r[high]相對應(yīng)的判定樹。設(shè)查找區(qū)間是[low,high]，判定樹的構(gòu)造方法：例如，結(jié)點(diǎn)個(gè)數(shù)（查找集合的記錄個(gè)數(shù)）為11的判定樹3構(gòu)造6的左子樹，區(qū)間[1,5]查找區(qū)間[1,11]，中間記錄的序號是6645構(gòu)造3的左子樹，區(qū)間[1,2]12構(gòu)造3的右子樹區(qū)間[4,5]判定樹例如，結(jié)點(diǎn)個(gè)數(shù)（查找集合的記錄個(gè)數(shù)）為11的判定樹3611845129構(gòu)造6的右子樹，區(qū)間[7,11]7構(gòu)造9的左子樹區(qū)間[7,8]10構(gòu)造9的右子樹區(qū)間[10,11]判定樹折半查找性能分析例如，結(jié)點(diǎn)個(gè)數(shù)（查找集合的記錄個(gè)數(shù)）為11的判定樹3691011784512折半查找任一記錄的過程，即是判定樹中從根結(jié)點(diǎn)到該記錄結(jié)點(diǎn)的路徑，和給定值的比較次數(shù)等于該記錄結(jié)點(diǎn)在樹中的層數(shù)查找第4個(gè)元素比較多少次？判定樹深度為

時(shí)間復(fù)雜度為O(log2n)比較次數(shù)至多為33~4~11~22~34~510~1111~9~108~97~85~66~7691011784512查找不成功的過程是從根結(jié)點(diǎn)到外部結(jié)點(diǎn)的路徑，和給定值進(jìn)行的比較次數(shù)等于該路徑上內(nèi)部結(jié)點(diǎn)的個(gè)數(shù)。折半查找性能分析查找成功情況下，與判定樹的深度有關(guān)，判定樹的深度是多少？如何確定查找失敗呢？例如查找的元素比第3個(gè)元素大比第4個(gè)元素小？33~4~11~22~34~510~1111~9~108~97~85~66~7691011784512折半查找性能分析查找成功的平均查找長度=(1×1+2×2+3×4+4×4)/11=3查找不成功的平均查找長度

=(3×4+4×8)/12=11/3折半查找性能分析在等概率假設(shè)下，二分查找的平均查找長度為二分查找的算法復(fù)雜度為：O(log2n)優(yōu)點(diǎn)：查找效率較高缺點(diǎn)：要求被查找序列事先按關(guān)鍵字排好序，而排序本身是一種很費(fèi)時(shí)的運(yùn)算；另外，二分查找只適用于順序存儲結(jié)構(gòu)，因此，二分查找特別適用于那種一經(jīng)建立就很少改動(dòng)、而又需要經(jīng)常查找的線性表。分塊查找數(shù)據(jù)結(jié)構(gòu)的設(shè)置：1）將長度為n的查找表R[n]均分成b塊(子表),要求:每一塊中的關(guān)鍵字不一定有序，但前一塊中的最大關(guān)鍵字必須小于后一塊中的最小關(guān)鍵字，即要“分塊有序”。2）建立索引表ID[b]，其中ID[i]存放第i塊中的最大關(guān)鍵字及該塊在查找表中的起始位置。由于表R[n]分塊有序，所以索引表ID[b]遞增有序。13392033424438608074498653221217132248862448123456789101112131415161718基本思想：首先查找索引表ID[]，以確定待查結(jié)點(diǎn)在哪一分塊(由于索引項(xiàng)按關(guān)鍵碼字有序，可用順序或折半查找)。然后，在已確定的那一塊中進(jìn)行順序查找。數(shù)據(jù)結(jié)構(gòu)定義：

長度為n的查找表采用順序表：ElemTypeR[]索引表的結(jié)構(gòu)typedefstruct/*索引表結(jié)點(diǎn)結(jié)構(gòu)*/{keytypekey;intaddr;}IDtable;IDtabelID[b];/*索引表*/分塊查找運(yùn)行實(shí)例12345678910111213141516171822121389203342443824486058745786532248861713索引表查38算法實(shí)現(xiàn)intBlkSearch(ElemTypeR[],IDtableID[],keytypeK){inti,low1,low2,mid,high1,high2;low1＝0;high1＝b-1;/*置查找區(qū)間上下界的初值*/while(low1<=high1){mid＝(low1+high1)/2;if(k<=ID[mid].key)high1＝mid-1;elselow1＝mid+1;}/*查找完畢，low1為找到的塊號*/if(low1<b)/*否則，K大于所有關(guān)鍵字*/{low2＝ID[low1].addr;/*塊起始地址*/if(low1==b-1)high2＝n-1;elsehigh2＝ID[low1+1].addr-1;for(i=low2;i<=high2;i++)/*在塊內(nèi)順序查找*/if(R[i].key==K)returni;/*查找成功*/}return(-1);/*查找失敗*/}分塊查找性能分析分塊查找由索引表查找和子表查找兩步完成，故整個(gè)算法的平均查找長度是兩次查找的平均查找長度之和。

ASL=ASL索引表+ASL子表

設(shè)查找表長為n,分為b個(gè)子表,每塊中均有s=n/b個(gè)元素若用二分查找來確定塊，則分塊查找的平均查找長度約為：若用順序查找來確定塊，則分塊查找的平均查找長度約為：

對于后一種情況，當(dāng)時(shí)，平均查找長度為極小值。在實(shí)用中，可根據(jù)表的具體情況進(jìn)行分塊。分塊查找性能分析分塊查找的性能介于順序查找和二分查找之間，例如對長度為10000的線性表,它們的平均查找長度分別是:

順序查找：ASL=(n+1)/2=5000

分塊查找：ASL=log2(b+1)-1+(S+1)/2<57

或ASL=(b+1)/2+(S+1)/2=101

二分查找：ASL=log2(n+1)-1<14優(yōu)點(diǎn)：把線性表分成若干邏輯子表，提高了查找效率缺點(diǎn)：增加了一索引存儲空間，和將初始表進(jìn)行分塊的運(yùn)算8.3樹表的查找（動(dòng)態(tài)查找）二叉搜索樹AVL樹——平衡的二叉搜索樹B-樹、B+樹樹表的提出順序查找：不要求元素的有序性，插入、刪除的性能是O(1)

查找性能是O(n)折半查找：查找性能是O(log2n)

為保證元素的有序性，插入、刪除要移動(dòng)元素，性能是O(n)樹表：將查找集合組織成樹的結(jié)構(gòu)二叉排序樹如何在一個(gè)大型的數(shù)據(jù)集合上進(jìn)行動(dòng)態(tài)查找？有沒有一種查找結(jié)構(gòu)，使得插入、刪除、查找均具有較好效率？二叉排序樹的定義二叉搜索樹（二叉排序樹）：或者是一棵空的二叉樹，或者是具有下列性質(zhì)的二叉樹：（1）若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值（2）若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值（3）它的左右子樹也都是二叉排序樹6360554258254565857063905542582545658570二叉排序樹的定義二叉排序樹是記錄之間滿足某種大小關(guān)系的二叉樹25424555586365708590升序序列二叉排序樹63905542582545658570寫出二叉排序樹的中序序列？二叉排序樹的存儲二叉鏈表45635590425870256585∧∧∧∧∧∧∧∧∧∧∧63905542582545658570如何存儲二叉排序樹？二叉排序樹的查找在二叉排序樹中查找給定值k

的過程是（1）若root是空樹，則查找失敗；（2）若k＝root->data，則查找成功；（3）若k＜root->data，則在root的左子樹上查找；（4）若k>

root->data，在root的右子樹上查找。二叉排序樹的查找效率在于只需查找二個(gè)子樹之一6355426585452590705855424563554265854525907058554245BiNode*SearchBST(BiNode*root,intk){if(root==NULL)returnNULL;if(root->data==k)returnroot;

elseif(root->data>k)returnSearchBST(root->lchild,k);elsereturnSearchBST(root->rchild,k);}在二叉搜索樹上進(jìn)行搜索，是一個(gè)從根結(jié)點(diǎn)開始，沿某一個(gè)分支逐層向下進(jìn)行比較判的過程。它可以是一個(gè)遞歸的過程。二叉排序樹的查找二叉排序樹的插入6355905870∧∧∧6390557058∧∧∧9898∧∧若二叉排序樹為空樹，則新插入的結(jié)點(diǎn)為新的根結(jié)點(diǎn)；否則，新插入的結(jié)點(diǎn)必為一個(gè)新的葉子結(jié)點(diǎn)，其插入位置由查找過程得到。如何在二叉排序樹中插入一個(gè)元素？例如，插入98voidInsertBST(BiNode*root,intx){

if(root==NULL){BiNode*s=(BiNode*)malloc(sizeof(BiNode));s->data=x;s->lchild=s->rchild=NULL;root=s;

}

elseif(root->data>x)InsertBST(root->lchild,x);

elseInsertBST(root->rchild,x);}63root∧∧55∧∧90∧∧先序遍歷的思想，任何結(jié)點(diǎn)插入到二叉排序樹時(shí)，都是以葉結(jié)點(diǎn)插入的。二叉排序樹的插入二叉排序樹的構(gòu)造voidCreatBST(BiNode*root,intr[],intn){

for(inti=0;i<n;i++)InsertBST(root,r[i]);}63554265854525907058例如，給定查找集合{63,55,42,45,58,90,70,25,85,65}，構(gòu)造二叉排序樹（1）每次插入的新結(jié)點(diǎn)都是二叉排序樹上新的葉子結(jié)點(diǎn);（2）找到插入位置后，不必移動(dòng)其它結(jié)點(diǎn)，僅需修改某個(gè)結(jié)點(diǎn)的指針；（3）在左子樹/右子樹的查找過程與在整棵樹上查找過程相同；（4）新插入的結(jié)點(diǎn)沒有破壞原有結(jié)點(diǎn)之間的關(guān)系。二叉排序樹的刪除（1）從二叉排序樹中刪除一個(gè)結(jié)點(diǎn)之后，要仍然保持二叉排序樹的特性；63554265854525907058（2）當(dāng)刪除分支結(jié)點(diǎn)時(shí)破壞了二叉排序樹中原有結(jié)點(diǎn)之間的鏈接關(guān)系，需要重新修改指針，使得刪除結(jié)點(diǎn)后仍為一棵二叉排序樹。如何在二叉排序樹中刪除一個(gè)元素？63554265854525907058情況1——被刪除的結(jié)點(diǎn)是葉子結(jié)點(diǎn)不失一般性，設(shè)待刪除結(jié)點(diǎn)為p，其雙親結(jié)點(diǎn)為f，且p是f的左孩子，pf操作：將雙親結(jié)點(diǎn)中相應(yīng)指針域的值改為空。f->lchild=NULL;6355428545259070f58二叉排序樹的刪除635542854525907058情況2——被刪除的結(jié)點(diǎn)只有左子樹或者只有右子樹不失一般性，設(shè)待刪除結(jié)點(diǎn)為p，其雙親結(jié)點(diǎn)為f，且p是f的左孩子，pf操作：將雙親結(jié)點(diǎn)中相應(yīng)指針域指向被刪除結(jié)點(diǎn)的左子樹（或右子樹）f->lchild=p->rchild;63554245259085pf二叉排序樹的刪除情況3——被刪除的結(jié)點(diǎn)既有左子樹也有右子樹不失一般性，設(shè)待刪除結(jié)點(diǎn)為p，其雙親結(jié)點(diǎn)為f，且p是f的左孩子，操作：找結(jié)點(diǎn)替換之，然后再刪除該結(jié)點(diǎn)中序遍歷：CLCPRFFCCLPRQQLS中序遍歷：CLCPPRFFPCPRCLQQLS二叉排序樹的刪除情況3——被刪除的結(jié)點(diǎn)既有左子樹也有右子樹不失一般性，設(shè)待刪除結(jié)點(diǎn)為p，其雙親結(jié)點(diǎn)為f，且p是f的左孩子，操作：以其中序前驅(qū)/后繼結(jié)點(diǎn)替換之，然后再刪除該結(jié)點(diǎn)中序遍歷：CLC……QLQSLSPPRFFPCPRCLQQLSSLFSCPRCLQQLSL中序遍歷：CLC……QLQSLSPRF二叉排序樹的刪除635542854525907058情況3——被刪除的結(jié)點(diǎn)既有左子樹也有右子樹不失一般性，設(shè)待刪除結(jié)點(diǎn)為p，其雙親結(jié)點(diǎn)為f，且p是f的左孩子，p操作：以其左子樹中的最大值結(jié)點(diǎn)替換之，然后再刪除該結(jié)點(diǎn)sparBiNode*par=p,*s=p->lchild;while(s->rchild!=NULL){par=s;s=s->rchild;}585542854525907056pspar56p->data=s->data;par->rchild=s->lchild;二叉排序樹的刪除6355428545259070情況3——被刪除的結(jié)點(diǎn)既有左子樹也有右子樹不失一般性，設(shè)待刪除結(jié)點(diǎn)為p，其雙親結(jié)點(diǎn)為f，且p是f的左孩子，p操作：以其左子樹中的最大值結(jié)點(diǎn)替換之，然后再刪除該結(jié)點(diǎn)spar特殊情況：左子樹中的最大值結(jié)點(diǎn)是被刪結(jié)點(diǎn)的孩子55428545259070psif(p==par)

par->lchild=s->lchild;二叉排序樹的刪除voidDeleteBST(BiNode*p,BiNode*f){

if(p->rchild==NULL){

/*p只有左子樹*/f->lchild=p->lchild;free(p);return;}if(p->lchild==NULL){

/*p只有右子樹*/f->lchild=p->rchild;free(p);return;}

if((p->lchild==NULL)&&(p->rchild==NULL)){

/*p為葉子*/f->lchild=NULL;free(p);return;}二叉排序樹的刪除BiNode*par=p,*s=p->lchild;

/*p的左右子樹均不空*/while(s->rchild!=NULL)

/*查找左子樹的最右下結(jié)點(diǎn)*/

{par=s;s=s->rchild;}p->data=s->data;if(par==p)par->rchild=s->lchild;/*特殊情況，p的左孩子無右子樹*/elsepar->lchild=s->lchild;free(s);

/*查找右子樹的最左下結(jié)點(diǎn)*/BiNode*par=p,*s=p->rchild;while(s->lchild!=NULL)

{par=s;s=s->lchild;}p->data=s->data;if(par==p)par->lchild=s->rchild;

elsepar->rchild=s->rchild;二叉排序樹的刪除舉例：805012060110150557053刪除508060120110150557053刪除60805512011015053701032581354832551348325413刪除10刪除5二叉排序樹的刪除二叉排序樹的性能分析在二叉排序樹中執(zhí)行插入和刪除操作查找插入和刪除的位置修改相應(yīng)指針插入、刪除、查找的時(shí)間復(fù)雜度相同63554265854525907058554245比較次數(shù)不超過樹的深度二叉排序樹的查找性能取決于什么？例如，給定查找集合{40,35,30,25,20,15}，構(gòu)造的二叉排序樹深度為n403530152520平均比較次數(shù)=(1+2+3+4+5+6)/6=21/6例如，給定查找集合{15,20,25,30,35,40}，構(gòu)造的二叉排序樹深度為403530152520平均比較次數(shù)=(1×1+2×2+3×3)/6=14/6最壞情況：退化為線性查找最好情況：相當(dāng)于折半查找平均情況：O(n)~O(log2n)查找集合的初始排列二叉排序樹的性能分析二叉排序樹的查找性能取決于什么？

容易看出，中序遍歷二叉排序樹可以得到按關(guān)鍵字遞增的有序序列。這就是說，一個(gè)原本無序的集合可通過構(gòu)造一棵二叉排序樹而變成有序集合，構(gòu)造樹的過程即為對無序集合進(jìn)行排序的過程。不僅如此，每次插入的新結(jié)點(diǎn)都是葉結(jié)點(diǎn)，即在插入過程中，不必移動(dòng)其他結(jié)點(diǎn)。這就相當(dāng)于在一個(gè)有序集合上插入一個(gè)元素而不需移動(dòng)其他元素。

因此，二叉排序樹既擁有類似折半查找的性能，又采用了鏈?zhǔn)酱鎯Y(jié)構(gòu)(而折半查找只適用于順序存儲結(jié)構(gòu))，因此是一種優(yōu)越的動(dòng)態(tài)集合63554265854525907058二叉排序樹的性能分析平衡二叉樹的提出二叉排序樹的深度取決于給定查找集合的排列，即結(jié)點(diǎn)的插入順序完全二叉樹的深度：1234568910712345689107左右子樹的深度相同具有n

個(gè)結(jié)點(diǎn)的二叉排序樹，最小深度是多少？有什么特征？二叉排序樹的深度取決于給定查找集合的排列，即結(jié)點(diǎn)的插入順序左右子樹的深度相同維護(hù)最小深度的二叉排序樹的代價(jià)太大左右子樹的深度相差1完全二叉樹的深度：平衡二叉樹的深度：平衡二叉樹的提出具有n

個(gè)結(jié)點(diǎn)的二叉排序樹，最小深度是多少？有什么特征？對于查找集合的任意排列，如何得到一棵深度盡可能小的二叉排序樹？平衡二叉樹的定義平衡因子：該結(jié)點(diǎn)的左子樹的深度減去右子樹的深度5482548210110-12200在平衡二叉樹中，結(jié)點(diǎn)的平衡因子是1、0或-1平衡二叉樹非平衡二叉樹平衡二叉樹：或者是一棵空的二叉排序樹，或者是具有下列性質(zhì)的二叉排序樹：（1）根結(jié)點(diǎn)的左子樹和右子樹的深度最多相差1;（2）根結(jié)點(diǎn)的左子樹和右子樹也都是平衡二叉樹最小不平衡子樹最小不平衡子樹：以距離插入結(jié)點(diǎn)最近的、且平衡因子的絕對值大于1的結(jié)點(diǎn)為根的子樹3-1210548269010000且入且判斷，一旦失衡立即調(diào)整只調(diào)整最小不平衡子樹，并且不影響其他結(jié)點(diǎn)4插入一個(gè)結(jié)點(diǎn)會影響哪些結(jié)點(diǎn)的平衡因子？如何調(diào)整最小不平衡子樹呢？平衡調(diào)整算法算法：平衡調(diào)整輸入：平衡二叉樹，新插入結(jié)點(diǎn)A輸出：新的平衡二叉樹1.找到最小不平衡子樹的根結(jié)點(diǎn)D2.根據(jù)結(jié)點(diǎn)A和結(jié)點(diǎn)D之間的關(guān)系，判斷調(diào)整類型3.根據(jù)類型、遵循扁擔(dān)原理和旋轉(zhuǎn)優(yōu)先原則進(jìn)行相應(yīng)調(diào)整

（1）LL型、RR型：調(diào)整一次

（2）LR型、RL型：調(diào)整兩次LL型的平衡調(diào)整403520012例1：設(shè)序列{40,35,20}，構(gòu)造平衡二叉樹40352040hBLhBRhARABX插入結(jié)點(diǎn)X失去平衡調(diào)整后重新平衡h+1BLhARBRhBAX新插入結(jié)點(diǎn)20和最小不平衡子樹根結(jié)點(diǎn)40之間的關(guān)系——LL型扁擔(dān)原理：將根結(jié)點(diǎn)看成是扁擔(dān)中肩膀的位置LL型的平衡調(diào)整例2：設(shè)序列{40,35,20,15,25,10}，構(gòu)造平衡二叉樹40352001240352040152510101235402015103525新插入結(jié)點(diǎn)10和最小不平衡子樹根結(jié)點(diǎn)35之間的關(guān)系——LL型扁擔(dān)原理：將根結(jié)點(diǎn)看成是扁擔(dān)中肩膀的位置旋轉(zhuǎn)優(yōu)先：旋轉(zhuǎn)下來的結(jié)點(diǎn)作為新根結(jié)點(diǎn)的孩子RR型的平衡調(diào)整2035400-1-2例3：設(shè)序列{20,35,40}，構(gòu)造平衡二叉樹20203540新插入結(jié)點(diǎn)40和最小不平衡子樹根結(jié)點(diǎn)20之間的關(guān)系——RR型扁擔(dān)原理：將根結(jié)點(diǎn)看成是扁擔(dān)中肩膀的位置RR型的平衡調(diào)整例4：設(shè)序列{20,35,40,38,45,50}，構(gòu)造平衡二叉樹2035400-1-22035204038455035204045503538新插入結(jié)點(diǎn)50和最小不平衡子樹根結(jié)點(diǎn)35之間的關(guān)系——RR型扁擔(dān)原理：將根結(jié)點(diǎn)看成是扁擔(dān)中肩膀的位置旋轉(zhuǎn)優(yōu)先：旋轉(zhuǎn)下來的結(jié)點(diǎn)作為新根結(jié)點(diǎn)的孩子平衡調(diào)整算法算法：平衡調(diào)整輸入：平衡二叉樹，新插入結(jié)點(diǎn)A輸出：新的平衡二叉樹1.找到最小不平衡子樹的根結(jié)點(diǎn)D2.根據(jù)結(jié)點(diǎn)A和結(jié)點(diǎn)D之間的關(guān)系，判斷調(diào)整類型3.根據(jù)類型、遵循扁擔(dān)原理和旋轉(zhuǎn)優(yōu)先原則進(jìn)行相應(yīng)調(diào)整

（1）LL型、RR型：調(diào)整一次

（2）LR型、RL型：調(diào)整兩次LR型的平衡調(diào)整A2-1hhh+1B初始平衡二叉樹h+2AB10hhhLR型h+2插入結(jié)點(diǎn)失去平衡細(xì)化B的右子樹2-1hhBCh-1hA-1C繞B左單旋h+2h+2C繞A右單旋恢復(fù)平衡A21hhBCh-1h100hhBCh-1h1ALR型的平衡調(diào)整例1：設(shè)序列{35,40,20,15,30,25}，構(gòu)造平衡二叉樹3520401530253520152530354035第1次調(diào)整新插入結(jié)點(diǎn)25和最小不平衡子樹根結(jié)點(diǎn)35之間的關(guān)系——LR型扁擔(dān)原理：將根結(jié)點(diǎn)看成是扁擔(dān)中肩膀的位置旋轉(zhuǎn)優(yōu)先：旋轉(zhuǎn)下來的結(jié)點(diǎn)作為新根結(jié)點(diǎn)的孩子LR型的平衡調(diào)整例1：設(shè)序列{35,40,20,15,30,25}，構(gòu)造平衡二叉樹3520401530253535252015304035第1次調(diào)整第2次調(diào)整252015304035新插入結(jié)點(diǎn)25和最小不平衡子樹根結(jié)點(diǎn)35之間的關(guān)系——LR型扁擔(dān)原理：將根結(jié)點(diǎn)看成是扁擔(dān)中肩膀的位置旋轉(zhuǎn)優(yōu)先：旋轉(zhuǎn)下來的結(jié)點(diǎn)作為新根結(jié)點(diǎn)的孩子LR型的平衡調(diào)整例2：設(shè)序列{35,20,30}，構(gòu)造平衡二叉樹35203035203035第1次調(diào)整第2次調(diào)整203035新插入結(jié)點(diǎn)30和最小不平衡子樹根結(jié)點(diǎn)35之間的關(guān)系——LR型扁擔(dān)原理：將根結(jié)點(diǎn)看成是扁擔(dān)中肩膀的位置RL型的平衡調(diào)整初始平衡二叉樹h+2AB-10hhhh+2插入結(jié)點(diǎn)失去平衡細(xì)化B的左子樹A-21hhh+1BRL型-21hhBCh-1hA1C繞B右單旋h+2h+2C繞A左單旋恢復(fù)平衡A-2-1hhBCh-1h-100hhBCh-1h-1ARL型的平衡調(diào)整例3：設(shè)序列{35,45,20,50,40,38}，構(gòu)造平衡二叉樹3520454050383538402035第1次調(diào)整4550新插入結(jié)點(diǎn)38和最小不平衡子樹根結(jié)點(diǎn)35之間的關(guān)系——RL型扁擔(dān)原理：將根結(jié)點(diǎn)看成是扁擔(dān)中肩膀的位置RL型的平衡調(diào)整例3：設(shè)序列{35,45,20,50,40,38}，構(gòu)造平衡二叉樹3520454050383538402035第1次調(diào)整4550第2次調(diào)整404550203538新插入結(jié)點(diǎn)38和最小不平衡子樹根結(jié)點(diǎn)35之間的關(guān)系——RL型扁擔(dān)原理：將根結(jié)點(diǎn)看成是扁擔(dān)中肩膀的位置旋轉(zhuǎn)優(yōu)先：旋轉(zhuǎn)下來的結(jié)點(diǎn)作為新根結(jié)點(diǎn)的孩子構(gòu)造平衡二叉排序樹且入且判斷，一旦失衡立即調(diào)整只調(diào)整最小不平衡子樹，并且不影響其他結(jié)點(diǎn)在構(gòu)造二叉排序樹的過程中，每當(dāng)插入一個(gè)新結(jié)點(diǎn)時(shí)，首先檢查是否因插入而破壞了樹的平衡性。若是,則找出其中最小不平衡子樹，在保持二叉排序樹特性的前提下,調(diào)整最小不平衡子樹中各結(jié)點(diǎn)之間的連接關(guān)系,以達(dá)到新的平衡。舉例：例：設(shè)序列{16,3,7,11,9,26,18,14,15}，構(gòu)造平衡二叉樹例：設(shè)序列{16,3,7,11,9,26,18,14,15}，構(gòu)造平衡二叉樹舉例：AVL樹的性能分析AVL的查找性能優(yōu)于一般的二叉排序樹，不像二叉排序樹，會出現(xiàn)最壞的時(shí)間復(fù)雜度O(n)，它的時(shí)間復(fù)雜度與二叉排序樹的最佳時(shí)間復(fù)雜相同，為O(log2n)實(shí)驗(yàn)表明78%的刪除完全不需要平衡化，只有53%的插入不需要平衡化可以將AVL樹的高度差放大，當(dāng)然此時(shí)AVL樹的高度也會相應(yīng)增加，從而使查找效率降低。例如

1.81log2n–0.71||≤2 h= 2.15log2n–1.13||≤3這時(shí)，訪問結(jié)點(diǎn)的ASL比純AVL樹(||≤1)多將近一倍，但插入或刪除時(shí)的重新平衡化操作卻能以10倍遞減AVL樹的性能分析小結(jié)

平衡二叉樹是組織紀(jì)錄的常用方法。查找的時(shí)間代價(jià)與O(log2n)等數(shù)量級，適合于組織在內(nèi)存中的規(guī)模較小的集合。對于存儲在外存(如磁盤)上的大型文件系統(tǒng)和數(shù)據(jù)庫管理系統(tǒng)，由于其中存放的是海量數(shù)據(jù)，所以log2n仍然很大，對外存進(jìn)行l(wèi)og2n次訪問還是很耗時(shí)，因此在外存中存儲大量紀(jì)錄時(shí)，我們通常采用索引(index)結(jié)構(gòu)。B樹的定義B_樹：一棵

m階的B樹是一棵平衡的m叉搜索樹，它或者為空樹，或者為滿足下列特性的m叉樹：（1）每個(gè)結(jié)點(diǎn)至多有

m棵子樹；1181112

213013924753199342

58701351654階B樹（2）根結(jié)點(diǎn)至少有兩棵子樹；（3）除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)外，所有結(jié)點(diǎn)至少有

m/2

棵子樹；子樹個(gè)數(shù)2~4B_樹：一棵m階的B_樹是一棵平衡的m叉搜索樹，它或者為空樹，或者為滿足下列特性的m叉樹：（4）所有結(jié)點(diǎn)都包含以下數(shù)據(jù)：（n，A0，K1，A1，K2，…，Kn，An），其中，n（

m/2

1≤n≤m

1）為關(guān)鍵碼的個(gè)數(shù)，Ki（1≤i≤n）為關(guān)鍵碼，且Ki＜Ki+1（1≤i≤n-1），Ai（0≤i≤n）為指向子樹根結(jié)點(diǎn)的指針，且指針Ai所指子樹中所有結(jié)點(diǎn)的關(guān)鍵碼均小于Ki+1大于Ki。1181112

21301392

4753199342

58

701351

65B樹的定義在B樹中，結(jié)點(diǎn)的值有什么特征？B_樹：一棵m階的B_樹或者為空樹，或者為滿足下列特性的m叉樹：（5）葉子結(jié)點(diǎn)都在同一層；葉子結(jié)點(diǎn)都在同一層樹高平衡具有較高的查找效率失敗結(jié)點(diǎn)葉子結(jié)點(diǎn)1181112

21301392

4753199342

58701351

65FFFFFFFFFFFFFFB樹的定義5階B_樹示意圖60102040708081899573776266455055582530121618681322由定義可知，B_樹的每個(gè)結(jié)點(diǎn)其實(shí)就是一個(gè)索引表，稱為索引結(jié)點(diǎn)。其關(guān)鍵字域按升序排列，Ai指針域指向包含該關(guān)鍵字的紀(jì)錄在外存中的地址。每個(gè)索引結(jié)點(diǎn)對應(yīng)于磁盤中的一個(gè)塊，因此也叫索引塊。對索引結(jié)點(diǎn)的訪問等價(jià)于從磁盤讀取相應(yīng)的索引塊B樹的定義B樹的查找B_樹的查找過程：（1）順指針查找結(jié)點(diǎn)：按照指針到相應(yīng)的子樹中查找；（2）在結(jié)點(diǎn)中查找關(guān)鍵碼：若在結(jié)點(diǎn)內(nèi)找到，則查找成功；（3）重復(fù)上述兩步，到達(dá)外部結(jié)點(diǎn)時(shí)，查找失敗。1181111271393

47536419924378135118111127139347536419924378135B樹的查找B樹通常存儲在磁盤上，則順指針查找結(jié)點(diǎn)是在磁盤上進(jìn)行，結(jié)點(diǎn)內(nèi)查找操作是在內(nèi)存中進(jìn)行，即在磁盤上找到某結(jié)點(diǎn)后，先將結(jié)點(diǎn)的信息讀入內(nèi)存，然后再查找等于

k

的關(guān)鍵碼。顯然，在磁盤上進(jìn)行一次查找比在內(nèi)存中進(jìn)行一次查找耗費(fèi)的時(shí)間多得多，因此，在磁盤上進(jìn)行查找的次數(shù)，是決定B樹查找效率的首要因素。B樹的深度第一層至少有1個(gè)結(jié)點(diǎn)第三層至少有2個(gè)結(jié)點(diǎn)第二層至少有2個(gè)結(jié)點(diǎn)根結(jié)點(diǎn)非終端結(jié)點(diǎn)至少有棵子樹若m階B樹有n個(gè)關(guān)鍵碼，則第k+1層有n+1個(gè)結(jié)點(diǎn)（失敗結(jié)點(diǎn)）根結(jié)點(diǎn)至少有兩棵子樹)k-1個(gè)結(jié)點(diǎn)以此類推，第k+1層至少有2(第k+1層為查找不成功的結(jié)點(diǎn)含有

n個(gè)關(guān)鍵碼的

m階B樹，最壞情況下的深度是多少？因此，含有

n個(gè)關(guān)鍵碼的m階B樹的最大深度是B樹的深度含有

n個(gè)關(guān)鍵碼的

m階B樹，最壞情況下的深度是多少？含有

n個(gè)關(guān)鍵碼的

m階B樹，最好情況下的深度是多少？B樹的插入假定在

m階B樹中插入關(guān)鍵碼key，插入過程如下：（1）定位：確定關(guān)鍵碼key應(yīng)該插入哪個(gè)葉子結(jié)點(diǎn)并返回該結(jié)點(diǎn)的指針p。

若

p中的關(guān)鍵碼個(gè)數(shù)不超過m-1個(gè)，則直接插入關(guān)鍵碼key；

否則，結(jié)點(diǎn)

p的關(guān)鍵碼個(gè)數(shù)溢出，執(zhí)行“分裂——提升”過程。B樹是多少階？m=3656020408010222850759096新關(guān)鍵碼將插入到相應(yīng)的葉子結(jié)點(diǎn)中假定在

m階B樹中插入關(guān)鍵碼key，插入過程如下：（1）定位：確定關(guān)鍵碼key應(yīng)該插入哪個(gè)終端結(jié)點(diǎn)并返回該結(jié)點(diǎn)的指針p。

若

p中的關(guān)鍵碼個(gè)數(shù)不超過m-1個(gè)，則直接插入關(guān)鍵碼key；

否則，結(jié)點(diǎn)

p的關(guān)鍵碼個(gè)數(shù)溢出，執(zhí)行“分裂——提升”過程。B樹是多少階？m

=3602040801022285090966575B樹的插入假定在

m階B樹中插入關(guān)鍵碼key，插入過程如下：（1）定位：確定關(guān)鍵碼key應(yīng)該插入哪個(gè)終端結(jié)點(diǎn)并返回該結(jié)點(diǎn)的指針p。

若

p中的關(guān)鍵碼個(gè)數(shù)不超過m-1個(gè)，則直接插入關(guān)鍵碼key；

否則，結(jié)點(diǎn)

p的關(guān)鍵碼個(gè)數(shù)溢出，執(zhí)行“分裂——提升”過程。B樹是多少階？m

=360204080102228509096657570發(fā)生溢出B樹的插入假定在

m階B樹中插入關(guān)鍵碼key，插入過程如下：B樹是多少階？m

=36020401022285090966575分裂—提升（2）分裂——提升：將結(jié)點(diǎn)

p“分裂”成兩個(gè)結(jié)點(diǎn)，分別是p1和p2，把中間的關(guān)鍵碼k“提升”到父結(jié)點(diǎn)，并且k的左指針指向p1，右指針指向p2。7080B樹的插入假定在

m階B樹中插入關(guān)鍵碼key，插入過程如下：B樹是多少階？m

=360204010222850909665757080（2）分裂——提升：如果父結(jié)點(diǎn)的關(guān)鍵碼個(gè)數(shù)也溢出，則繼續(xù)執(zhí)行“分裂——提升”過程。顯然，這種分裂可能一直上傳，如果根結(jié)點(diǎn)也分裂了，則樹的高度增加了一層。30發(fā)生溢出B樹的插入假定在

m階B樹中插入關(guān)鍵碼key，插入過程如下：B樹是多少階？m

=3602028401050909665757080（2）分裂——提升：如果父結(jié)點(diǎn)的關(guān)鍵碼個(gè)數(shù)也溢出，則繼續(xù)執(zhí)行“分裂——提升”過程。顯然，這種分裂可能一直上傳，如果根結(jié)點(diǎn)也分裂了，則樹的高度增加了一層。分裂——提升再次溢出2230B樹的插入假定在

m階B樹中插入關(guān)鍵碼key，插入過程如下：B樹是多少階？m

=31050909665757080（2）分裂——提升：如果父結(jié)點(diǎn)的關(guān)鍵碼個(gè)數(shù)也溢出，則繼續(xù)執(zhí)行“分裂——提升”過程。顯然，這種分裂可能一直上傳，如果根結(jié)點(diǎn)也分裂了，則樹的高度增加了一層。再次分裂——提升223028602040B樹的插入（1）定位：確定關(guān)鍵碼key應(yīng)該插入哪個(gè)葉子結(jié)點(diǎn)并返回該結(jié)點(diǎn)的指針p（2）若

p中的關(guān)鍵碼個(gè)數(shù)小于m-1，則直接插入關(guān)鍵碼key（3）若

p中的關(guān)鍵碼個(gè)數(shù)等于m-1，則執(zhí)行“分裂——提升”（4）如果提升到父結(jié)點(diǎn)的關(guān)鍵碼個(gè)數(shù)等于m-1

，則繼續(xù)執(zhí)行“分裂——提升”如果在B樹中插入一個(gè)元素時(shí)導(dǎo)致根結(jié)點(diǎn)發(fā)生溢出，則B樹產(chǎn)生一個(gè)新的根結(jié)點(diǎn)并且樹高增加了一層，此時(shí)，新根只有一個(gè)關(guān)鍵碼和兩棵子樹。假定在

m階B樹中插入關(guān)鍵碼key，插入過程如下：B樹的插入為什么B樹的根結(jié)點(diǎn)最少有兩棵子樹？105090966575708022302860204095105065752230204090967095288060B樹的插入如果在B樹中插入一個(gè)元素時(shí)導(dǎo)致根結(jié)點(diǎn)發(fā)生溢出，則B樹產(chǎn)生一個(gè)新的根結(jié)點(diǎn)并且樹高增加了一層，此時(shí)，新根只有一個(gè)關(guān)鍵碼和兩棵子樹。為什么B樹的根結(jié)點(diǎn)最少有兩棵子樹？99例：從空樹開始逐個(gè)加入關(guān)鍵碼建立3階B_樹(又叫2-3樹)的插入過程插入5353插入755375插入139537553751395375139插入49，14549751395314536插入3649751395314536491397514553101插入101364913975145531454975101361395313914549751013653B樹的插入在

m階B樹中刪除關(guān)鍵碼key的過程：確定關(guān)鍵碼key在哪個(gè)結(jié)點(diǎn)并返回該結(jié)點(diǎn)的指針q，從中刪去這個(gè)關(guān)鍵碼。刪除分兩種情況：情況1——?jiǎng)h除葉子結(jié)點(diǎn)中關(guān)鍵碼情況2——?jiǎng)h除非葉子結(jié)點(diǎn)中關(guān)鍵碼B樹的刪除情況1——?jiǎng)h除葉子結(jié)點(diǎn)中關(guān)鍵碼有3種情況（1）如果葉子結(jié)點(diǎn)中關(guān)鍵碼的個(gè)數(shù)大于

m/2

-1，直接刪去。6321427812233051869665

746321427812518696233074B樹的刪除（2）如果葉子結(jié)點(diǎn)中關(guān)鍵碼的個(gè)數(shù)等于

m/2

-1，而其相鄰的左/右兄弟結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)大于

m/2-1，則向兄弟結(jié)點(diǎn)借一個(gè)關(guān)鍵碼。632142781251869623307463213078124286967423B樹的刪除情況1——?jiǎng)h除葉子結(jié)點(diǎn)中關(guān)鍵碼有3種情況（3）如果兄弟結(jié)點(diǎn)的關(guān)鍵碼個(gè)數(shù)也不大于

m/2

-1，則執(zhí)行“合并”兄弟操作。63213078124286967423637812869674233021B樹的刪除情況1——?jiǎng)h除葉子結(jié)點(diǎn)中關(guān)鍵碼有3種情況（3）如果兄弟結(jié)點(diǎn)的關(guān)鍵碼個(gè)數(shù)也不大于

m/2

-1，則執(zhí)行“合并”兄弟操作。如果雙親結(jié)點(diǎn)的關(guān)鍵碼個(gè)數(shù)發(fā)生下溢，則雙親結(jié)點(diǎn)也要進(jìn)行借關(guān)鍵碼或合并操作。637812869674212312216378869674如果根結(jié)點(diǎn)的兩個(gè)孩子結(jié)點(diǎn)進(jìn)行合并，則B樹就會減少一層級聯(lián)合并B樹的刪除情況1——?jiǎng)h除葉子結(jié)點(diǎn)中關(guān)鍵碼有3種情況情況2——?jiǎng)h除非葉子結(jié)點(diǎn)中關(guān)鍵碼

如果刪除非底層結(jié)點(diǎn)中關(guān)鍵碼Ki，則可用指針Ai所指子樹中的最小關(guān)鍵碼x

替代Ki，然后在相應(yīng)結(jié)點(diǎn)中刪除x，即轉(zhuǎn)為情況1的刪除。65214278125186962330746321427812233051869665

74刪除操作歸結(jié)為在葉子結(jié)點(diǎn)中刪除關(guān)鍵碼B樹的刪除假定在

m階B_樹中刪除關(guān)鍵碼key，刪除過程如下：（1）定位：確定關(guān)鍵碼key在哪個(gè)結(jié)點(diǎn)并返回該結(jié)點(diǎn)的指針q。

假定key是結(jié)點(diǎn)

q中的第

i個(gè)關(guān)鍵碼Ki，有以下兩種情況：

1.1若結(jié)點(diǎn)

q

是葉子結(jié)點(diǎn)，則刪除key；

1.2否則用

Ai所指子樹中的最小值

x

替換Ki；刪除x；

（2）判斷是否下溢2.1如果葉子結(jié)點(diǎn)中關(guān)鍵碼的個(gè)數(shù)大于

-1，則直接刪除；

2.2否則，刪除操作涉及到兄弟結(jié)點(diǎn)

2.2.1兄弟結(jié)點(diǎn)的關(guān)鍵碼個(gè)數(shù)大于，則向兄弟結(jié)點(diǎn)借一個(gè)關(guān)鍵碼，

并且借來的關(guān)鍵碼“上移”到雙親結(jié)點(diǎn)，雙親結(jié)點(diǎn)相應(yīng)關(guān)鍵碼“下移”；

2.2.2否則執(zhí)行“合并”兄弟操作；刪除空結(jié)點(diǎn)，并將雙親結(jié)點(diǎn)中的相應(yīng)關(guān)鍵碼“下移”到合并結(jié)點(diǎn)中；B樹的刪除B_樹的分析根據(jù)B_樹的定義，每個(gè)索引塊必須保證至少半滿，因此整個(gè)索引樹可能會有50%的空間被浪費(fèi)。實(shí)驗(yàn)表明，B_樹的平均利用率是69%(即31%的磁盤空間被浪費(fèi)了)Knuth等人在B_樹的基礎(chǔ)上又提出了B*樹。在B*樹中，除根以外的所有結(jié)點(diǎn)都至少2/3滿而不是半滿。更準(zhǔn)確說，對m叉B*樹索引結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)n，有

≤n≤m-1。當(dāng)結(jié)點(diǎn)分裂時(shí)，兩個(gè)結(jié)點(diǎn)分裂成三個(gè)，而不是一分為二，即當(dāng)兩個(gè)互為兄弟的結(jié)點(diǎn)都滿時(shí)，分裂成三個(gè)結(jié)點(diǎn)，原來兩個(gè)結(jié)點(diǎn)中的所有關(guān)鍵字在三個(gè)結(jié)點(diǎn)中平均分配，使每個(gè)結(jié)點(diǎn)至少2/3滿。實(shí)驗(yàn)表明，B*樹的平均利用率是81%，比B_樹要好。而且通過延遲結(jié)點(diǎn)的分裂降低了結(jié)點(diǎn)分裂發(fā)生的頻率，提高了操作效率.B+樹的定義B+樹：B+樹可以看作是B樹的一種變形，在實(shí)現(xiàn)文件索引結(jié)構(gòu)方面比B_樹使用得更普遍。一棵m階的B+樹和m階的B樹的差異在于：（1）有m棵子樹的結(jié)點(diǎn)中含有m個(gè)關(guān)鍵碼；（2）所有的葉子結(jié)點(diǎn)中包含了全部關(guān)鍵碼的信息，及指向含有這些關(guān)鍵碼記錄的指針,且葉子結(jié)點(diǎn)本身依關(guān)鍵碼的大小自小而大的順序鏈接。（3）所有的非終端結(jié)點(diǎn)可以看成是索引部分,結(jié)點(diǎn)中僅含有其子樹根結(jié)點(diǎn)中最大(或最小)關(guān)鍵碼。一棵4階的B+樹示例B+樹的定義B+樹的搜索在B+樹上進(jìn)行隨機(jī)搜索、插入和刪除的過程基本上與B_樹類似。只是在搜索過程中，若非終端結(jié)點(diǎn)上的關(guān)鍵碼等于給定值，搜索并不停止，而是繼續(xù)沿右指針向下，一直查到葉結(jié)點(diǎn)上的這個(gè)關(guān)鍵碼。因此，在B+樹，不管查找成功與否，每次查找都是走了一條從根到葉子結(jié)點(diǎn)的路徑。路徑長度即為讀磁盤的次數(shù)3152152231475210121518192022233031334547485052張三索引部分root通過該指針可以實(shí)現(xiàn)隨機(jī)查找sqt通過該指針可以實(shí)現(xiàn)順序查找B+樹的插入B+樹的插入僅在葉結(jié)點(diǎn)上進(jìn)行。每插入一個(gè)關(guān)鍵碼后都要判斷結(jié)點(diǎn)中的子樹棵數(shù)是否超出范圍。（1）當(dāng)結(jié)點(diǎn)中的關(guān)鍵碼個(gè)數(shù)大于m時(shí)要分裂成兩個(gè)結(jié)點(diǎn)，它們的關(guān)鍵碼分別為

(m+1)/2

和

(m+1)/2

。并且它們雙親結(jié)點(diǎn)中應(yīng)包含這兩個(gè)結(jié)點(diǎn)的最大關(guān)鍵碼和結(jié)點(diǎn)地址。此后，問題歸于在非終端結(jié)點(diǎn)中的插入了。（2）在非終端結(jié)點(diǎn)中關(guān)鍵碼的插入與葉結(jié)點(diǎn)的插入類似，非終端結(jié)點(diǎn)中的子樹棵數(shù)的上限為m，超出這個(gè)范圍就需要進(jìn)行結(jié)點(diǎn)分裂。（3）在做根結(jié)點(diǎn)分裂時(shí)，因?yàn)闆]有雙親結(jié)點(diǎn)，就必須創(chuàng)建新的雙親結(jié)點(diǎn)，作為樹的新根。這樣樹的高度就增加一層了。B+樹的刪除僅在葉結(jié)點(diǎn)上進(jìn)行。當(dāng)在葉結(jié)點(diǎn)上刪除