5.1線性查找5.2折半查找5.3分快查找5.4二叉查找樹(shù)5.5平衡二叉樹(shù)5.6B-樹(shù)5.7散列法第5章查找查找分類傳統(tǒng)的查找方法較先進(jìn)的查找方法（散列法,哈希表）線性查找折半查找分快查找二叉查找樹(shù)幾個(gè)概念：查找表：由同一類型的數(shù)據(jù)元素（或紀(jì)錄）構(gòu)成的集合。關(guān)鍵字：數(shù)據(jù)元素中某一數(shù)據(jù)項(xiàng)的值，用以表示一個(gè)數(shù)據(jù)元素。靜態(tài)查找：查找+提取數(shù)據(jù)元素屬性信息動(dòng)態(tài)查找：查找+（插入或刪除元素）查找：根據(jù)給定的值，在查找表中確定一個(gè)其關(guān)鍵字等于給定值的紀(jì)錄或數(shù)據(jù)元素。IntSearch(k,last,F)Keytyoek,intlast;LISTF;/*在F中查找關(guān)鍵字為k的紀(jì)錄，若找到，則返回該紀(jì)錄所在的下標(biāo)，否則返回0*/{inti;F[0].key=k;i=last;while(F[i].key!=k)i=i–1;returni;}/*Search*/Structrecords{keytypekey;fieldsother;}TypedefrecordsLIST[maxsize];LISTF;5.1線性查找算法一：順序表LISTSearch(k,F)Keytypek;LISTF;{LISTp;p=F;while(p!=NULL)if(p->data.key==k)returnp;elsep=p->next;returnp;}Structcelltype{recordsdata;celltype*next;}Typedefcelltype*LIST;算法二：鏈表性能分析[定義]

為確定紀(jì)錄在查找表中的位置，需和給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)的期望值稱為查找算法在查找成功時(shí)的

平均查找長(zhǎng)度(AverageSearchLength)。設(shè)Pi為查找表中第i個(gè)記錄的概率?！芇i=1

Ci為比較次數(shù)ASL=∑Pi·Cini=1在等概率情況下Pi=1/n，且一般情況下Ci=n－i+1ASL=nP1+(n-1)P2+…+2Pn-1+Pn=1/n·∑(n－i+1)ni=1=(n+1)/25.2折半查找查找表=[05,13,19,21,37,56,64,75,80,88,92]Key=210513192137566475808892Low=1mid=6Up=11Up=5mid=3Low=4,mid=40513192137566475808892Low=1mid=6Up=11Key=85low=5mid=9Low=10,mid=10Low=10Up=9Intbinary-search(keytypek,LISTF){intlow,up,mid;low=1;up=last;while(low<=up){mid=(low+up)/2;if(F[mid].key==k)returnmid;elseif(F[mid].key>k)up=mid–1;elselow=mid+1;}return–1}折半查找算法算法分析6391471025811hn=2h-1(h=log2(n+1))ASLbs=∑Pi·CiPi=1/nni=1=1/n·∑j·2j-1hj=1=(n+1)/n·log2(n+1)-1平均查找長(zhǎng)度ASLbs=log2(n+1)-1O(log2n)intBsearch(F,i,j,k)//折半查找的遞歸算法{intm;if(i>j)return(-1);else{m=(i+j)/2;if(F[m].key==k)returnm;if(F[m].key<k)return(Bsearch(F,i,m-1,k));elsereturn(Bsearch(F,m+1,j,k));}}調(diào)用：Bsearch(F,1,n,k)5.3分塊查找(線性查找+折半查找)224474012IX221213983342443824486058744701234567891011121314F索引表Intindex_search(k,last,blocks,ix,F,L)Keytypek;intlast,blocks;indexixLISTF;intL;{inti,j;i=0;while((k>ix[i])&&(i<blocks))i++;if(i<blocks){j=i*L;while((k!=F[j].key)&&(j<=(i+1)*L-1)&&(j<last))j=j+1;if(k==F[j].key)returnj;}return–1;}Typedefkeytypeindex[maxblock]5.4二叉查找樹(shù)(二叉排序樹(shù))1031415121671518Structcelltype{recordsdata;celltype*lchild,*rchild;}Typedefcelltype*BST;BSTsearch(keytypek,BSTF);{p=F;if(p==NULL)returnNull;elseif(k==p->data.key)returnp;elseif(K<p->data.key)return(search(k,p->lchild));elseif(K>p->data.key)return(search(k,p->rchild));}Voidinsert(recordsR,BST&F){if(F==NULL){F=newcelltype;F->data=R;F->lchild=NULL;F->rchild=NULL;}elseif(R.key<F->data.key)insert(R,F->lchild)elseif(R.key>F->data.key)insert(R,F->rchild)}在二叉查找樹(shù)中插入新結(jié)點(diǎn)在二叉查找樹(shù)中刪除結(jié)點(diǎn)1051437121811516刪除之前10514371215116刪除18之后10515371218116刪除14之后刪除三類結(jié)點(diǎn)：1、被刪除的結(jié)點(diǎn)是葉子結(jié)點(diǎn)2、被刪除的結(jié)點(diǎn)只有一顆非空的左子樹(shù)或右子樹(shù)3、被刪除的結(jié)點(diǎn)有兩棵非空的子樹(shù)Voiddelete(keytypek,BST&F){if(F!=NULL)if(k<F->data.key)

delete(k,f->lchild);elseif(k>F->data.key)

delete(k,f->rchild);elseif(F->rchild==NULL)F=F->lchild;elseif(F->lchild==NULL)F=F->rchild;elseF->data=deletemin(F->rchild)}在二叉查找樹(shù)中刪除結(jié)點(diǎn)Recordsdeletemin(F){recordstmp;BSTp;if(F->lchild==NULL){p=F;tmp=F->data;F=F->rchild;deletep;returntmp;}elsereturn(deletemin(F->lchild);}用右子樹(shù)中最左邊的結(jié)點(diǎn)作為繼承結(jié)點(diǎn)在F所指的非空二叉樹(shù)中刪除關(guān)鍵字最小的結(jié)點(diǎn)，返回該結(jié)點(diǎn)中的數(shù)據(jù)。例：二叉樹(shù)用二叉鏈表表示，且每個(gè)結(jié)點(diǎn)的鍵值互不相同，編寫(xiě)算法判別該二叉樹(shù)是否為二叉排序樹(shù)。intjudge(BTree*bt){BTree*s[100],*p=bt;inttop=0,preval=min;do{while(p){s[top++]=p;p=p->lchild;}if(top>0){p=s[--top];

if(p->data<preval)return0;//不是二叉排序樹(shù)

preval=p->data;p=p->rchild;}}while(p||top>0);return(1)；//是二叉排序樹(shù)

}5.5AVL樹(shù)，又稱平衡二叉樹(shù)(BalancedBinaryTree)結(jié)點(diǎn)的平衡因子BF(BanlancedFactor)定義為：

結(jié)點(diǎn)左子樹(shù)與右子樹(shù)的高度之差。AVL中的任意結(jié)點(diǎn)的BF只可能是-1，0，+1[定義]

AVL樹(shù)或者是一顆空二叉樹(shù)，或者具有如下性質(zhì)的二叉查找樹(shù)：其左子樹(shù)和右子樹(shù)都是高度平衡的二叉樹(shù)，且左子樹(shù)和右子樹(shù)高度之差的絕對(duì)值不超過(guò)1。G.M.Adelson-Velsky和E.M.Landis,首次出現(xiàn)在1962年論文：《Analgorithmfortheorganizationofinformation》格奧爾吉·阿杰爾松-韋利斯基,前蘇聯(lián)數(shù)學(xué)家，計(jì)算機(jī)科學(xué)家。1922年出生于俄羅斯薩馬拉。1962年與葉夫吉尼·蘭迪斯發(fā)明了AVL樹(shù)。后移居以色列，現(xiàn)居住于阿什杜德。251200-1-125-23002527270003025270+1+13025270025003000+2+2302527+11112110+10301227025+1110+2-130122701818011-1002712250(a)插入25(b)插入27(c)插入30(d)插入12

RR旋轉(zhuǎn)(e)插入11(f)插入18

LL旋轉(zhuǎn)

LR旋轉(zhuǎn)輸入={25,27,30,12,11,18,14,20,15,22}0030018+111-1+1-1271225014200110150300011-1+1-127122501418200-1300+111-1+2-22712250141820003000-1+10271425+1151812(g)插入14(h)插入20(i)插入15

RL旋轉(zhuǎn)110-10300-1-1+2-1271425+115181222020110-10-1000+1251418+12215123002027

LR旋轉(zhuǎn)(i)插入22LL：新結(jié)點(diǎn)Y被插入到A的左子樹(shù)的左子樹(shù)上；LR：新結(jié)點(diǎn)Y被插入到A的左子樹(shù)的右子樹(shù)上；RR：新結(jié)點(diǎn)Y被插入到A的右子樹(shù)的右子樹(shù)上；RL：新結(jié)點(diǎn)Y被插入到A的右子樹(shù)的左子樹(shù)上；對(duì)稱設(shè)：Y表示新插入的結(jié)點(diǎn)，

A表示離新插入結(jié)點(diǎn)Y最近的且平衡因子變?yōu)椤?的祖先結(jié)點(diǎn)BLARBLBRhhABARh21BRhhBh00ABRBLhhAh-2-1BBRBLhhBAALh00ALLL型(a)LL型的旋轉(zhuǎn)RR型(b)RR型的旋轉(zhuǎn)h-1CLCLh-1hABBL2-1h-10-1AChARARhBLhCB10LR型(c)LR型的旋轉(zhuǎn)CRCRh-1h-1CLh-1hA-21h-10-1BCCLhALBRhALhCA10RL型(d)RL型的旋轉(zhuǎn)BBRh-1CRCRintunbalanced=FALSE;structNode{ElementTypedata;intbf;structNode*lchild,*rchild;}TypedefNode*AVLT;AVL樹(shù)的結(jié)構(gòu)類型voidAVLInsert(AVLT&T,ElementTypeR,int&unbalanced)

{if(!T)//向空二叉樹(shù)中插入元素

{unbalanced=TRUE;T=newNode;T->data=R;T->lchild=T->rchild=NULL;T->bf=0;}elseif(R.key<T->data.key)//在左子樹(shù)上插入

{AVLInser(T->lchild,R,unbalanced);if(unbalanced)switch(T->bf){case-1:T->bf=0;unbalanced=FALSE;break;case0:T->bf=1;break;case1:LeftRotation(T,unbalanced);}}unbalanced=TRUE；elseif(R.key>T->data.key)//在右子樹(shù)上插入

{AVLInsert(T->rchild,R,unbalanced);if(unbalanced)switch(T->bf){case1:T->bf=0;unbalanced=FALSE;break;case0:T->bf=-1;break;case-1:RightRotation(T,unbalanced);

}}elseunbalanced=FALSE;}//AVLInsertvoidLeftRotation(AVL&T,int&unbalanced){AVLTgc,lc;

lc=T->lchild;if(lc->bf==1)//LL旋轉(zhuǎn)

{T->lchild=lc->rchild;lc->rchild=T;T->bf=0;T=lc}else//LR旋轉(zhuǎn)

{gc=lc->rchild;lc->rchild=gc->lchild;gc->lchild=lc;T->lchild=gc->rchild;gc->rchild=T;

switch(gc->bf){case1:T->bf=-1;lc->bf=0;break;case0:T->bf=lc->bf=0;break;case-1:T->bf=0;lc->bf=1;}

T=gc;}T->bf=0;unbalanced=FALSE;}BLBRhhABARh21(a)LL型的旋轉(zhuǎn)TlcBLBRhhABARh21TlcBLARBRhhBh00Alc=T->lchild;if(lc->bf==1)//LL旋轉(zhuǎn)

{T->lchild=lc->rchild;

lc->rchild=T;T->bf=0;T=lc}…Th-1CLh-1hABBL2-1ChAR1(c)LR型的旋轉(zhuǎn)CRlcTgch-1CLh-10-1AARhBLhCB0CRlc=T->lchild;……else//LR旋轉(zhuǎn){gc=lc->rchild;

lc->rchild=gc->lchild;

gc->lchild=lc;

T->lchild=gc->rchild;

gc->rchild=T;……T=gc;TvoidRightRotation(AVLT*&T){AVLT*gc,*rc;rc=T->rchild;

if(rc->bf==-1)//RR旋轉(zhuǎn){T->rchild=rc->lchild;rc->lchild=T;T->bf=0;T=rc;}else//RL旋轉(zhuǎn){gc=rc->lchild;rc->lchild=gc->rchild;gc->rchild=rc;T->rchild=gc->lchild;gc->lchild=T;switch(gc->bf){//調(diào)整平衡因子

case-1:T->bf=-1;rc->bf=0;break;case0:T->bf=rc->bf=0;break;case1:T->bf=0;rc->bf=-1;}T=gc;}T->bf=0;unbalanced=FALSE;}分析：高度為h的AVL樹(shù)最多具有Nhmax=2h-1個(gè)結(jié)點(diǎn)(二叉樹(shù)性質(zhì)一)高度為h的AVL樹(shù)最少具有多少個(gè)結(jié)點(diǎn)？

N0=1

N1=1

N2=2……

Nh=Nh-1+Nh-2+1Fi=Fi-1+Fi-2(Fibonaccipolynomial)T(n)=O(logn)Nhmin=?例1：下述二叉樹(shù)中,哪一種滿足性質(zhì):從任一結(jié)點(diǎn)出發(fā)到根的路徑上所經(jīng)過(guò)的結(jié)點(diǎn)序列按其關(guān)鍵字有序

(A)二叉排序樹(shù)

(B)赫夫曼樹(shù)

(C)AVL樹(shù)

(D)堆【分析】

對(duì)于選項(xiàng)A，根據(jù)二叉排序樹(shù)的結(jié)構(gòu)特點(diǎn)我們可以知道，二叉排序樹(shù)的中序遍歷結(jié)果是一個(gè)有序序列，而在中序遍歷中，父結(jié)點(diǎn)并不總是出現(xiàn)在孩子結(jié)點(diǎn)的前面（或后面），故該選項(xiàng)不正確。對(duì)于選項(xiàng)B，根據(jù)赫夫曼樹(shù)的結(jié)構(gòu)特點(diǎn)我們可以知道，在赫夫曼樹(shù)中所有的關(guān)鍵字只出現(xiàn)在葉結(jié)點(diǎn)上，其非葉結(jié)點(diǎn)上并沒(méi)有關(guān)鍵字值，顯然不正確。對(duì)于選項(xiàng)C，AVL樹(shù)其本質(zhì)上也是一種二叉排序樹(shù)，只不過(guò)是平衡化之后的二叉排序樹(shù)，故該選項(xiàng)也是不正確的。對(duì)于選項(xiàng)D，堆的概念我們會(huì)在堆排序中給大家介紹，根據(jù)建堆的過(guò)程，不斷地把大者“上浮”，將小者“篩選”下去，最終得到的正是一個(gè)從任一結(jié)點(diǎn)出發(fā)到根的路徑上所經(jīng)過(guò)的結(jié)點(diǎn)序列按其關(guān)鍵字有序的樹(shù)狀結(jié)構(gòu)。D是正確答案例2：輸入關(guān)鍵碼序列為(16,3,7,11,9,26,18,14,15)，據(jù)此建立平衡二叉樹(shù)，給出插入和調(diào)整的具體過(guò)程。例3：有一棵平衡二叉樹(shù)的初始狀態(tài)如圖所示，請(qǐng)給出刪除圖中結(jié)點(diǎn)p后經(jīng)調(diào)整得到的新的平衡二叉樹(shù)。由于結(jié)點(diǎn)p既有左孩子，又有右孩子，故在刪除結(jié)點(diǎn)p的時(shí)候應(yīng)該先找到中序遍歷中結(jié)點(diǎn)p的直接前驅(qū)結(jié)點(diǎn)，即結(jié)點(diǎn)o，然后用o取代p，刪除o，此時(shí)結(jié)點(diǎn)o的平衡度變?yōu)?，發(fā)生不平衡，故應(yīng)對(duì)子樹(shù)o,r,t進(jìn)行RR型調(diào)整結(jié)點(diǎn)m的平衡度變?yōu)?2，發(fā)生不平衡，故應(yīng)對(duì)子樹(shù)m,e,j進(jìn)行LR調(diào)整例4：判斷任意二叉樹(shù)是否是平衡二叉樹(shù)intIsAVL(AVLT*T)//判斷平衡二叉樹(shù){inthl,hr;if(T==NULL) return(1);else{hl=Depth(T->lchild);hr=Depth(T->rchild);if(abs(hl-hr)<=1){if(IsAVL(T->lchild))return(IsAVL(T->rchild));}elsereturn(0);}}intDepth(AVLT*bt)//求二叉樹(shù)的深度{intldepth,rdepth;if(bt==NULL)return(0);else{ldepth=Depth(bt->lchild);rdepth=Depth(bt->rchild);if(ldepth>rdepth)return(ldepth+1);else return(rdepth+1);}}[m-路查找樹(shù)定義1]

一顆m-路查找樹(shù)或者為空，或者滿足以下性質(zhì)：1、根結(jié)點(diǎn)至多包含m棵子樹(shù)，且具有以下結(jié)構(gòu)

n,A0,(K1,A1),(K2,A2),……,(Kn,An)

其中，Ai是指向子樹(shù)的指針，0≤i≤n＜m；Ki是關(guān)鍵字值，0≤i≤n＜m2、Ki<Ki+1，1≤

i＜

n3、子樹(shù)Ai中的所有關(guān)鍵字值都小于Ki+1，而大于Ki,1<i<n4、子樹(shù)An中的所有關(guān)鍵字值都大于Kn，子樹(shù)A0中的所有關(guān)鍵字值都小于K15、每棵子樹(shù)Ai都是m-路查找樹(shù)，0≤

i≤

n由于每個(gè)結(jié)點(diǎn)最多包含m-1個(gè)關(guān)鍵字，因此在一棵高度為h的m-路查找樹(shù)中，最多可容納mh-1個(gè)關(guān)鍵字。例如：h=3的二叉樹(shù)，最多容納7個(gè)關(guān)鍵字；而對(duì)于h=3的200-路查找樹(shù)，最多有mh-1=8*106-1個(gè)關(guān)鍵字。設(shè)m-路查找樹(shù)高度為h，其結(jié)點(diǎn)數(shù)量的最大值是∑mi=h-1i=0mh-1m-1[m-路查找樹(shù)定義2]

m

分支查找樹(shù)T,是指其所有結(jié)點(diǎn)的度都不大于m的查找樹(shù)。

空樹(shù)T

是一株m

分支查找樹(shù)。當(dāng)T

非空時(shí)，它有下述性質(zhì)：（1）T

是形式如下的一個(gè)結(jié)點(diǎn)：

n,A0,(K1,A1),(K2,A2),……,(Kn,An)

其中，Ai(0≤i≤n＜m)是指向T

之子樹(shù)的指針，而Ki(0≤i≤n)是元素，并且0≤i≤n＜m;

（2）Ki<Ki+1,(1≤i<n)

；（3）子樹(shù)Ai中的所有元素值小于Ki+1(0≤i<n);

（4）子樹(shù)An中的所有元素值大于Kn;

（5）子樹(shù)Ai（0≤i≤n）也是m分支查找樹(shù)。nA0K1A1K2A2……KiAiKi+！Ai+1……Kn-1An-1KnAnniAi0Ki1Ai1……KijAij……KniAniKi＜

(Ki1，Ki2，……Kij，Kni)＜Ki+1K＞AnK＜A0…………5.6B-樹(shù)B-TreeBalanced-Tree

B-樹(shù)：B-樹(shù)是一種非二叉的查找樹(shù)除了要滿足查找樹(shù)的特性，還要滿足以下結(jié)構(gòu)特性：

一棵m階的B-樹(shù)：（1）樹(shù)的根或者是一片葉子(一個(gè)節(jié)點(diǎn)的樹(shù)),或者其兒子數(shù)在2和

m

之間。（2）除根外，所有的非葉子結(jié)點(diǎn)的孩子數(shù)在m/2

和m

之間。（3）所有的葉子結(jié)點(diǎn)都在相同的深度。B-樹(shù)的平均深度為logm/2N。執(zhí)行查找的平均時(shí)間為O(logm)；B-樹(shù)應(yīng)用在數(shù)據(jù)庫(kù)系統(tǒng)中的索引，它加快了訪問(wèn)數(shù)據(jù)的速度；[B-樹(shù)定義]一顆m階B-樹(shù)是一顆m-路查找樹(shù)，它或?yàn)榭?，或滿足以下性質(zhì)：1、根結(jié)點(diǎn)至少包含2個(gè)兒子2、除根結(jié)點(diǎn)和失敗結(jié)點(diǎn)以外，所有結(jié)點(diǎn)都至少具有m/2個(gè)兒子3、所有失敗結(jié)點(diǎn)都在同一層1、B-樹(shù)中的關(guān)鍵字值個(gè)數(shù)所有2階B-樹(shù)都是滿二叉樹(shù)，只有當(dāng)關(guān)鍵字個(gè)數(shù)等于2k-1時(shí)，才存在2階B-樹(shù)對(duì)于任意給定的關(guān)鍵字和任意的m(>2),一定存在一棵包含上述所有關(guān)鍵字的

m階B-樹(shù)。所有失敗結(jié)點(diǎn)都在l+1層的m階B-樹(shù)至多包含ml-1個(gè)關(guān)鍵字。B-樹(shù)的第1層至少包含2個(gè)兒子B-樹(shù)的第2層至少包含2個(gè)結(jié)點(diǎn)B-樹(shù)的第3層至少包含2*(m/2)個(gè)結(jié)點(diǎn)B-樹(shù)的第4層至少包含2*(m/2)2個(gè)結(jié)點(diǎn)…B-樹(shù)的第l(>1)層至少包含2*(m/2)l-2

個(gè)結(jié)點(diǎn)每個(gè)結(jié)點(diǎn)又至少包含m/2個(gè)兒子注：上述所有結(jié)點(diǎn)都不是失敗結(jié)點(diǎn)若B-樹(shù)中的關(guān)鍵字分別為K1,K2,…,Kn，且有Ki<Ki+1，(1≤

i＜

N)則失敗結(jié)點(diǎn)的個(gè)數(shù)為N+1

。因?yàn)楫?dāng)x滿足Ki<x<Ki+1,就會(huì)查找失敗，其中：K0=-∞，KN+1=+∞使得查找不在B-樹(shù)中的關(guān)鍵字x時(shí)，就可能到達(dá)N+1個(gè)不同的失敗結(jié)點(diǎn)。因此：

N+1=失敗結(jié)點(diǎn)個(gè)數(shù)=第l+1層的結(jié)點(diǎn)個(gè)數(shù)≥2*(m/2)l-1故有N≥2*(m/2)l-1，l≥1反之，如果一棵m階B-樹(shù)包含N個(gè)關(guān)鍵字，則所有非失敗結(jié)點(diǎn)所在的層號(hào)都小于或等于l，l≤logm/2|(N+1)/2|+1即每次查找所需進(jìn)行至多l(xiāng)+1次的結(jié)點(diǎn)訪問(wèn)。例：m=200的B-樹(shù)，當(dāng)N≤2×106-2時(shí)，有l(wèi)≤log100|(N+1)/2|+1由于l為整數(shù)，所以l≤3。而當(dāng)N≤2×108-2時(shí)，有l(wèi)≤4。因此，采用高階的B-樹(shù)可以用很少的磁盤(pán)訪問(wèn)次數(shù)來(lái)查找大規(guī)模的索引。2、B-樹(shù)階的選擇高階B-樹(shù)會(huì)降低在查找索引時(shí)所需的磁盤(pán)訪問(wèn)次數(shù)

——人們期望使用高階B-樹(shù)如果索引中包含N各元素，則m=N+1階B-樹(shù)就只有一層

——但m的選擇受到內(nèi)存可用空間的限制

選取較大的結(jié)點(diǎn)度數(shù)可降低樹(shù)的高度，以及減少查找任意關(guān)鍵字所需的磁盤(pán)訪問(wèn)次數(shù)。如果m的值很大，使得索引不能一次性地全部讀入內(nèi)存，就會(huì)增加讀盤(pán)次數(shù)，也會(huì)增加結(jié)點(diǎn)內(nèi)的查找時(shí)間，m的選擇不合理合理地選擇m的目標(biāo)可使得在B-樹(shù)中查找關(guān)鍵字x所需的總時(shí)間最?。?/p>

從磁盤(pán)上讀入結(jié)點(diǎn)的時(shí)間B-樹(shù)上查找x的時(shí)間在結(jié)點(diǎn)中查找x所需要的時(shí)間

在大多數(shù)系統(tǒng)中，B-樹(shù)上的算法執(zhí)行時(shí)間主要由讀、寫(xiě)磁盤(pán)的次數(shù)來(lái)決定，每次讀寫(xiě)盡可能多的信息可提高算法得執(zhí)行速度。

B-樹(shù)中的結(jié)點(diǎn)的規(guī)模一般是一個(gè)磁盤(pán)頁(yè)，而結(jié)點(diǎn)中所包含的關(guān)鍵字及其孩子的數(shù)目取決于磁盤(pán)頁(yè)的大小。25,3020,4010,1545,5035abcde結(jié)點(diǎn)n,A0,(K1,A1),(K2,A2)a2b(20,C)(40,d)b2^(10,^)(15,^)c2^(25,^)(30,e)d2^(45,^)(50,^)e1^(35,^)【例1】3分支查找樹(shù)，元素為（10，15，20，25，30，35，40，45，50）[重申]m階的B-樹(shù)T是這樣一棵m分支查找樹(shù)：T或者為空；或者其高度不小于1且滿足下述性質(zhì)：（1）根結(jié)點(diǎn)至少有兩個(gè)兒子；（2）除根和葉子結(jié)點(diǎn)外的所有結(jié)點(diǎn)，至少有m/2個(gè)兒子；（3）所有的葉子結(jié)點(diǎn)都在同一層上。非B-樹(shù)【例2】一棵高度為3的1001階B-樹(shù)。說(shuō)明：

①每個(gè)結(jié)點(diǎn)包含1000個(gè)關(guān)鍵字，故在第三層上有100多萬(wàn)個(gè)葉結(jié)點(diǎn)，這些葉節(jié)點(diǎn)可容納10億多個(gè)關(guān)鍵字。

②圖中各結(jié)點(diǎn)內(nèi)的數(shù)字表示關(guān)鍵字的數(shù)目。

③通常根結(jié)點(diǎn)可始終置于主存中，因此在這棵B-樹(shù)中查找任一關(guān)鍵字至多只需二次訪問(wèn)外存。#defineMaxl000

//結(jié)點(diǎn)中關(guān)鍵字的最大數(shù)目：Max=m-1，m是B-樹(shù)的階

#defineMin500

//非根結(jié)點(diǎn)中關(guān)鍵字的最小數(shù)目：Min=┌m/2┐-1

typedefintKeyType；//KeyType應(yīng)由用戶定義

typedefstructnode//結(jié)點(diǎn)定義中省略了指向關(guān)鍵字代表的記錄的指針{intkeynum//結(jié)點(diǎn)中當(dāng)前擁有的關(guān)鍵字的個(gè)數(shù)，keynum<Max

KeyTypekey[Max+1]//關(guān)鍵字向量為key[1..keynum]，key[0]不用

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

structnode*son[Max+1]；//孩子指針向量為son[0..keynum]

}BTreeNode；

typedefBTreeNode*BTree；1、B-樹(shù)的存儲(chǔ)結(jié)構(gòu)（1）B-樹(shù)的查找方法

在B-樹(shù)中查找給定關(guān)鍵字的方法類似于二叉排序樹(shù)上的查找。不同的是在每個(gè)結(jié)點(diǎn)上確定向下查找的路徑不一定是二路而是keynum+1路的。對(duì)結(jié)點(diǎn)內(nèi)的存放有序關(guān)鍵字序列的向量key[l..keynum]用順序查找或折半查找方法查找。若在某結(jié)點(diǎn)內(nèi)找到待查的關(guān)鍵字K，則返回該結(jié)點(diǎn)的地址及K在

key[1..keynum]中的位置；否則，確定K在某個(gè)key[i]和key[i+1]之間結(jié)點(diǎn)后，從磁盤(pán)中讀son[i]所指的結(jié)點(diǎn)繼續(xù)查找……。2、B-樹(shù)的查找【例3】下圖中左邊的虛線表示查找關(guān)鍵字1的過(guò)程，它失敗于葉結(jié)點(diǎn)的H和K

之間空指針上；右邊的虛線表示查找關(guān)鍵字S的過(guò)程，并成功地返回S

所在結(jié)點(diǎn)的地址和S在key[1..keynum]中的位置2。【例4】BTreeNode*SearchBTree(BTreeT，KeyTypeK，int*pos)

{//在B-樹(shù)T中查找關(guān)鍵字K，成功時(shí)返回找到的結(jié)點(diǎn)的地址及K在其中的位置*pos

//失敗則返回NULL

inti；

T->key[0]=k;//設(shè)哨兵．下面用順序查找key[1..keynum]

for(i=T->keynum；K<t->key[i];i--)；//從后向前找第1個(gè)小于等于K的關(guān)鍵字

if(i>0&&T->key[i]==1){//查找成功，返回T及i

*pos=i；

returnT；

}//結(jié)點(diǎn)內(nèi)查找失敗，但T->key[i]<K<T->key[i+1]，下一個(gè)查找的結(jié)點(diǎn)應(yīng)為son[i]

if(!T->son[i])//*T為葉子，在葉子中仍未找到K，則整個(gè)查找過(guò)程失敗

returnNULL；

//查找插入關(guān)鍵字的位置，則應(yīng)令*pos=i，并返回T，見(jiàn)后面的插入操作

DiskRead(T->son[i])；//在磁盤(pán)上讀人下一查找的樹(shù)結(jié)點(diǎn)到內(nèi)存中

returnSearchBTree(T->Son[i]，k，pos)；//遞歸地繼續(xù)查找于樹(shù)T->son[i]

}（2）B-樹(shù)的查找算法B-樹(shù)上的查找有兩個(gè)基本步驟：

①在B-樹(shù)中查找結(jié)點(diǎn)，該查找涉及讀盤(pán)操作，屬外部查找；

②在結(jié)點(diǎn)內(nèi)查找，該查找屬內(nèi)查找。

查找操作的時(shí)間為：

①外查找的讀盤(pán)次數(shù)不超過(guò)樹(shù)高h(yuǎn)，故其時(shí)間是O(h)；

②內(nèi)查找中，每個(gè)結(jié)點(diǎn)內(nèi)的關(guān)鍵字?jǐn)?shù)目keynum<m(m是B-樹(shù)的階數(shù))，故其時(shí)間為O(nh)。

注意：

①實(shí)際上外部查找時(shí)間可能遠(yuǎn)遠(yuǎn)大于內(nèi)部查找時(shí)間。

②B-樹(shù)作為數(shù)據(jù)庫(kù)文件時(shí)，打開(kāi)文件之后就必須將根結(jié)點(diǎn)讀人內(nèi)存，而直至文件關(guān)閉之前，此根一直駐留在內(nèi)存中，故查找時(shí)可以不計(jì)讀入根結(jié)點(diǎn)的時(shí)間。（3）查找操作的時(shí)間開(kāi)銷5階B-樹(shù)示例

【例5】下圖給出了一棵包含24個(gè)英文字母的5階B-樹(shù)的存儲(chǔ)結(jié)構(gòu)圖。按照定義，在5階B-樹(shù)里，根中的關(guān)鍵字?jǐn)?shù)目可以是1～4，子樹(shù)數(shù)可以是2～5；其它的結(jié)點(diǎn)中關(guān)鍵字?jǐn)?shù)目可以是2～4，若該結(jié)點(diǎn)不是葉子，則它可以有3～5棵子樹(shù)。3、B-樹(shù)的插入操作210301102203011511012021525130未分裂分裂1次分裂2次【例1】110130115【例2】【例3】以關(guān)鍵字序列

(a，g，f，b，k，d，h，m，i，e，s，i，r，x，c，l，n，t，u，p)

建立一棵5階B-樹(shù)的生長(zhǎng)過(guò)程注意：

①當(dāng)一結(jié)點(diǎn)分裂時(shí)所產(chǎn)生的兩個(gè)結(jié)點(diǎn)大約是半滿的，這就為后續(xù)的插入騰出了較多的空間,尤其是當(dāng)m較大時(shí)，往這些半滿的空間中插入新的關(guān)鍵字不會(huì)很快引起新的分裂。

②向上插人的關(guān)鍵字總是分裂結(jié)點(diǎn)的中間位置上的關(guān)鍵字，它未必是正待插入該分裂結(jié)點(diǎn)的關(guān)鍵字。因此，無(wú)論按何次序插入關(guān)鍵字序列，樹(shù)都是平衡的。aagafgabfgabfgkfabgkfabdgkfabdghkfabdghkmfabdghjkmfjabdghkm上述關(guān)鍵字序列(a,g,f,b,k,d,h,m,j,e,s,i,r,x,c,l,n,t,u,p)(1)(2)(3)(4)(5)(6)(7)(8)(9)fjabdeghkmfjabdeghkmsfjabdeghikmsfjabdeghikmrsfjabdeghikmrsxfjrabdeghikmsx(10)(11)(12)(13)(14)fjrabcdeghikmsxcfjrdeghikmsxabcfjrdeghiklmsxabcfjrdeghiklmnsxabcfjrdeghiklmnstxabcfjrdeghiklmnstuxab(15)(16)(17)(18)(19)cfjrdeghiklmnpstuxabcfjmrdeghiklstuxabnpcfdeghiklstuxabnpjmr(20)重申：

①當(dāng)一結(jié)點(diǎn)分裂時(shí)所產(chǎn)生的兩個(gè)結(jié)點(diǎn)大約是半滿的，這就為后續(xù)的插入騰出了較多的空間，尤其是當(dāng)m較大時(shí),往這些半滿的空間中插入新的關(guān)鍵字不會(huì)很快引起新的分裂。

②向上插人的關(guān)鍵字總是分裂結(jié)點(diǎn)的中間位置上的關(guān)鍵字，它未必是正待插入該分裂結(jié)點(diǎn)的關(guān)鍵字。因此，無(wú)論按何次序插入關(guān)鍵字序列，樹(shù)都是平衡的。首先執(zhí)行插入操作以確定可以插入新關(guān)鍵字的葉結(jié)點(diǎn)p。如果在結(jié)點(diǎn)p上插入新關(guān)鍵字是結(jié)點(diǎn)p的關(guān)鍵字達(dá)到m，則需要分裂結(jié)點(diǎn)p。否則，只需將新結(jié)點(diǎn)p寫(xiě)入磁盤(pán)上，完成插入操作。分裂節(jié)點(diǎn)：假定插入新關(guān)鍵字后，結(jié)點(diǎn)p具有如下結(jié)構(gòu)：m,A0,(K1,A1),(K2,A2),……,(Km,Am),

且Ki<Ki+1,0≤i＜m分裂后，形成具有如下格式的兩個(gè)結(jié)點(diǎn)p和q:結(jié)點(diǎn)p：m/2,A0,(K1,A1),……,(Km/2-1,Am-1)結(jié)點(diǎn)q：m-m/2,Am/2,(Km/2,Am/2+1),……,(Km,Am)剩下的關(guān)鍵字Km/2和指向新結(jié)點(diǎn)q的指針形成一個(gè)二元組(Km/2,q)。該二元組將被插入到p的父結(jié)點(diǎn)中。插入前，將結(jié)點(diǎn)p和q寫(xiě)盤(pán)。插入父結(jié)點(diǎn)有可能會(huì)導(dǎo)致這個(gè)父結(jié)點(diǎn)的分裂，而且此分裂過(guò)程可能會(huì)一直向上傳播，直到根結(jié)點(diǎn)為止。根結(jié)點(diǎn)分裂時(shí)，創(chuàng)建一個(gè)只包含一個(gè)關(guān)鍵字的新根結(jié)點(diǎn)，B-樹(shù)的高度增1。插入結(jié)點(diǎn)小結(jié)4、B-樹(shù)的刪除操作首先找到要?jiǎng)h除的關(guān)鍵字x所在的結(jié)點(diǎn)z。若z不是葉結(jié)點(diǎn)，則用該B-樹(shù)中某個(gè)葉結(jié)點(diǎn)中的關(guān)鍵字來(lái)代替結(jié)點(diǎn)z中的x。假定x是z中的第i個(gè)關(guān)鍵字（x=Ki），就可以用子樹(shù)Ai中的最小關(guān)鍵字或者子樹(shù)Ai-1中的最大關(guān)鍵字來(lái)替換x，而這兩個(gè)關(guān)鍵字均在葉結(jié)點(diǎn)中。

=〉把從非葉結(jié)點(diǎn)中刪除x的操作轉(zhuǎn)化成從葉結(jié)點(diǎn)中刪除x的操作?！纠?】刪除5階B-樹(shù)的h、r、p、d等關(guān)鍵字的過(guò)程例1的過(guò)程分析：第2個(gè)刪去的r不在葉子中，故用中序后繼s取代r，即把s復(fù)制到r的位置上，然后從葉子中刪去s。第3個(gè)刪去的p所在的葉子中的關(guān)鍵字?jǐn)?shù)目是最小值Min，但其右兄弟的關(guān)鍵字個(gè)數(shù)>m/2-1,故可以通過(guò)左移，將雙親中的s移到p所在的結(jié)點(diǎn)，而將右兄弟中‘最小(即最左邊)的關(guān)鍵字t上移至雙親取代s。當(dāng)刪去d時(shí)，d所在的結(jié)點(diǎn)及其左右兄弟均無(wú)多余的關(guān)鍵字，故需將刪去d后的結(jié)點(diǎn)與這兩個(gè)兄弟中的一個(gè)(圖中是選擇左兄弟(ab))及其雙親中分隔這兩個(gè)被合并結(jié)點(diǎn)的關(guān)鍵字c合并在一起形成一個(gè)新結(jié)點(diǎn)(abce)。但因?yàn)殡p親中失去c后關(guān)鍵字個(gè)數(shù)<m/2-1，故必須對(duì)該結(jié)點(diǎn)做調(diào)整操作，此時(shí)它只有一個(gè)右兄弟，且右兄弟無(wú)多余的關(guān)鍵字，不可能通過(guò)移動(dòng)關(guān)鍵字來(lái)解決。因此引起再次合并，因根只有一個(gè)關(guān)鍵字，故合并后樹(shù)高度減少一層，從而得到上圖的最后一個(gè)圖。第1個(gè)被刪的關(guān)鍵字h是在葉子中，且該葉子的關(guān)鍵字個(gè)數(shù)>m/2-1(5階B-樹(shù)的Min=2)，故直接刪去即可。從葉結(jié)點(diǎn)p刪除關(guān)鍵字后，分為4種不同情況分別進(jìn)行處理：1、p同時(shí)也是根結(jié)點(diǎn)，若刪除x后還至少剩一個(gè)關(guān)鍵字，寫(xiě)盤(pán)，結(jié)束；否則，B-樹(shù)變成空樹(shù)；2、刪除x后結(jié)點(diǎn)p至少還有m/2-1個(gè)關(guān)鍵字，寫(xiě)盤(pán)，結(jié)束；3、刪除x后結(jié)點(diǎn)p有m/2-2個(gè)關(guān)鍵字，其鄰近的右兄弟（左兄弟）結(jié)點(diǎn)q至少還有m/2個(gè)關(guān)鍵字。假定r是p和q的父結(jié)點(diǎn)，設(shè)Ki是r中大于（或小于）x的最小（或最大）關(guān)鍵字，將Ki下移至p，把q的最?。ɑ蜃畲螅╆P(guān)鍵字上移到r的Ki處，把q的最左（或最右）子樹(shù)指針平移到p中最后（或最前）子樹(shù)的指針處，在q中，將被移走的關(guān)鍵字和指位置有剩余的關(guān)鍵字和指針補(bǔ)齊，再將其中的關(guān)鍵字個(gè)數(shù)減1。將p、q、r寫(xiě)盤(pán)，結(jié)束；刪除小結(jié)4、刪除x后結(jié)點(diǎn)p有m/2-2個(gè)關(guān)鍵字，其鄰近的右兄弟（左兄弟）結(jié)點(diǎn)q至少還有m/2-1個(gè)關(guān)鍵字。將p、q和關(guān)鍵字Ki合并，形成一個(gè)結(jié)點(diǎn)，有少于m-1個(gè)關(guān)鍵字。合并操作使父結(jié)點(diǎn)r的關(guān)鍵字個(gè)數(shù)減1。若r中關(guān)鍵字個(gè)數(shù)仍滿足要求（根至少1個(gè)關(guān)鍵字，非根結(jié)點(diǎn)至少m/2-1個(gè)關(guān)鍵字），寫(xiě)盤(pán)，結(jié)束。否則，父結(jié)點(diǎn)r的關(guān)鍵字不足，若是根，其中無(wú)關(guān)鍵字，刪除；若r不是根結(jié)點(diǎn)，其關(guān)鍵字個(gè)數(shù)應(yīng)為m/2-2。要與其兄弟結(jié)點(diǎn)合并，并沿

B-樹(shù)向上進(jìn)行，直到根結(jié)點(diǎn)的兒子被合并為止。B-樹(shù)的高度及性能分析B-樹(shù)上操作的時(shí)間由存取磁盤(pán)的時(shí)間和CPU計(jì)算時(shí)間構(gòu)成。B-樹(shù)上大部分基本操作所需訪問(wèn)盤(pán)的次數(shù)均取決于樹(shù)高h(yuǎn)。關(guān)鍵字總數(shù)相同的情況下B-樹(shù)的高度越小，磁盤(pán)I/O所花的時(shí)間越少。與高速的CPU計(jì)算相比，磁盤(pán)I/O要慢得多，所以可忽略

CPU的計(jì)算時(shí)間，只分析算法所需的磁盤(pán)訪問(wèn)次數(shù)：（磁盤(pán)訪問(wèn)次數(shù)）×（讀寫(xiě)盤(pán)的平均時(shí)間）1、B-樹(shù)的高度

若n≥1，m≥3，則對(duì)任意一棵具有n個(gè)關(guān)鍵字的m階B-樹(shù)，其樹(shù)高h(yuǎn)至多為：logt((n+1)/2)+1。

t

是每個(gè)(除根外)內(nèi)部結(jié)點(diǎn)的最小度數(shù)，即[m/2]B-樹(shù)的高度為O(logtn)。在B-樹(shù)上查找、插入和刪除的讀寫(xiě)盤(pán)的次數(shù)為O(logtn)，CPU計(jì)算時(shí)間為O(mlogtn)。2、性能分析

①n個(gè)結(jié)點(diǎn)的平衡的二叉排序的高度H（即lgn）比B-樹(shù)的高度h約大lgt倍。

【例】若m=1024，則lgt=lg512=9。此時(shí)若B-樹(shù)高度為4，則平衡的二叉排序樹(shù)的高度約為36。顯然，若m越大，則B-樹(shù)高度越小。②若要作為內(nèi)存中的查找表，B-樹(shù)卻不一定比平衡的二叉排序樹(shù)好，尤其當(dāng)m較大時(shí)更是如此。因?yàn)椴檎业炔僮鞯腃PU計(jì)算時(shí)間在B-樹(shù)上是:

O(mlogtn)=0(lgn·(m/lgt))

而m/logt>1，所以m較大時(shí)O(mlogtn)比平衡的二叉排序樹(shù)上相應(yīng)操作的時(shí)間

O(lgn)大得多。因此，僅在內(nèi)存中使用的B-樹(shù)必須取較小的m。③通常取最小值m=3，此時(shí)B-樹(shù)中每個(gè)內(nèi)部結(jié)點(diǎn)可以有2或3個(gè)孩子，這種3階的B-樹(shù)稱為2-3樹(shù)。B+樹(shù)是B-樹(shù)的一種變形，二者區(qū)別在于：

1、有k個(gè)子結(jié)點(diǎn)的結(jié)點(diǎn)必然有k個(gè)關(guān)鍵碼

2、非葉子結(jié)點(diǎn)僅具有索引作用，與記錄有關(guān)的信息均放在葉結(jié)點(diǎn)中查找：

B+樹(shù)查找過(guò)程中，即使找到關(guān)鍵碼，也必須向下找到葉子結(jié)點(diǎn)插入：插入在葉子上，分裂，改變上層兩個(gè)最大關(guān)鍵碼刪除：刪除在葉結(jié)點(diǎn)，上層關(guān)鍵馬可以保留，刪除后若關(guān)鍵字少于m/2，則與B-同樣處理B-樹(shù)適合只隨機(jī)檢索，但B+樹(shù)同時(shí)支持隨機(jī)檢索和順序檢索B+樹(shù)5.7散列法——哈希（Hash）查找散列法——地址散列法被查找元素的存儲(chǔ)地址=Hash(Key)KeyBEIJING（北京)TIANJIN(天津)HEBEI(河北)SHANXI(山西)SHANGHAI(上海)SHANGDONG(山東)HENAN(河南)SICHUAN(四川)f1(key)0220081919190819f2(key)0904172828262203f3(key)0426021323171616例：全國(guó)30個(gè)地區(qū)的人口統(tǒng)計(jì)，每個(gè)地區(qū)為一個(gè)記錄，內(nèi)容如下：編號(hào)地區(qū)名總?cè)丝跐h族回族…f1(key):取關(guān)鍵字第一個(gè)字母在字母表中的序號(hào)f2(key):求第一和最后字母在字母表中序號(hào)之和，然后取30的余數(shù)f3(key):將第一個(gè)字母的八進(jìn)制看成十進(jìn)制，再取30的余數(shù)Hash查找的關(guān)鍵問(wèn)題①構(gòu)造Hash函數(shù)②制訂解決沖突的方法散列（Hash）函數(shù)（表）分類內(nèi)散列表（數(shù)組）外散列表（鏈表）構(gòu)造散列函數(shù)（Hash）的幾種方法：

直接定址法：Hash(key)=key;或Hash(key)=a·key+b;

質(zhì)數(shù)除余法平方取中法折疊法數(shù)字分析法隨機(jī)數(shù)法解決沖突的方法：開(kāi)放定址法再散列法鏈地址法建立一個(gè)公共溢出區(qū)地址0102030405…252627…100年齡12345…252627…100人數(shù)300020005000…6000……：地址0102030405…252627…100年份194919501951…1973…人數(shù)300020005000…6000……：直接定址法：Hash(key)=key;或Hash(key)=a·key+b;例一：Hash(key)=key例二：Hash(key)=key+（-1949）+1質(zhì)數(shù)除余法設(shè)桶數(shù)B，取質(zhì)數(shù)m≤BHash(key)=key%m平方取中法取key

2

的中間的幾位數(shù)作為散列地址記錄keykey2HashA01000010000010I11001210000210J12001440000440I011601370400370P120614310541310P220624314704314Q121614734741734Q221624741304741Q321634745651745平方取中法折疊法圖書(shū)編號(hào):0-442-20586-458644220+041008858640224+046092左：移位疊加

Hash(key)=0088右：間界疊加

Hash(key)=6092數(shù)字分析法813465328137224281387422813013678132281781338967813541578136853781419355①②③④⑤⑥⑦⑧如右圖所示假設(shè)散列表長(zhǎng)為10010可取中間4位中的兩位為散例地址隨機(jī)數(shù)法構(gòu)造Hash函數(shù)應(yīng)注意以下幾個(gè)問(wèn)題：計(jì)算Hash函數(shù)所需時(shí)間關(guān)鍵字的長(zhǎng)度散列表的大小關(guān)鍵字的分布情況記錄的查找頻率解決沖突的幾種方法：開(kāi)放定址法Hi=(H(key)+di

)MODm

i=1,2,…,k

(k≤m-2)H(key)為哈希函數(shù)，m為表長(zhǎng)，di為增量序列：(1)di=1,2,3,…,m-1(2)di=12,-12,22,-22,…,±k2(k≤m/2)(3)di

為偽隨機(jī)序列，稱為偽隨機(jī)探測(cè)再散列再散列法Hi=Rhi(key)i=1,2,…,k鏈地址法例：(19,14,23,01,68,20,84,27,55,11,10,79)

H(key)=keyMOD1301142779?5568?1968?20?1023?11?0123456789101112???????建立一個(gè)公共溢出區(qū)鏈地址法處理沖突方法查找成功查找失?。ú迦胗涗洠┚€性探測(cè)法二次探測(cè)法再散列法鏈地址法幾種處理沖突方法的平均查找長(zhǎng)度裝填因子：α=表中裝入的記錄數(shù)哈希表的長(zhǎng)度裝填因子α標(biāo)志著哈希表的裝滿程度，α越小，發(fā)生沖突的可能性越小，反之，發(fā)生沖突的可能性越大。成功查找平均查找長(zhǎng)度：ASLs