數(shù)據(jù)結(jié)構(gòu)講義九：二叉排序樹資料課件

動態(tài)查找二叉排序樹平衡二叉樹B-樹（B+樹）鍵樹二叉排序樹二叉排序樹：或是一棵空二叉樹，或是一棵具有下列性質(zhì)的二叉樹：若左子樹非空，則左子樹上所有結(jié)點的值均小于根結(jié)點的值；若右子樹非空，則右子樹上所有結(jié)點的值均大于根結(jié)點的值；并且其左、右子樹均是二叉排序樹。類型定義為：typedef

struct

BSTNode{intkey;∥關(guān)鍵字域

…∥其它數(shù)據(jù)域

struct

BSTNode*lchild,*rchild;∥左、右孩子指針

}BSTNode,*BSTree;

二叉排序樹示例30125332394187189查找71、5

二叉排序樹的查找算法假定二叉排序樹的根結(jié)點指針為root，給定的關(guān)鍵字值為K，則查找算法可描述為：

①置初值：q＝root；

②如果K＝q－＞key，則查找成功，算法結(jié)束；

③否則，如果K＜q－＞key，而且q的左子樹非空，則將q的左子樹根送q，轉(zhuǎn)步驟②；否則，查找失敗，結(jié)束算法；

④否則，如果K＞q－＞key，而且q的右子樹非空，則將q的右子樹根送q，轉(zhuǎn)步驟②；否則，查找失敗，算法結(jié)束。

int

Bstree::Search(KeyTypeK)

{

intflag=0;

BstNode*q=root;

while((q!=NULL)&&(flag==0))

{

if(q->key==K)

{

cout<<"查找成功，找到："<<q->key<<endl;

flag=1;

}

elseif(K<q->key)q=q-lch;

elseq=q->rch;

}

if(flag==0)cout<<"查找失敗，無此結(jié)點!\n";

returnflag;

}

函數(shù)Search中，參數(shù)root為根結(jié)點指針，K為欲查找的關(guān)鍵字值，這里假定它是整數(shù)。函數(shù)執(zhí)行完后，如果查找成功，輸出所找到結(jié)點的關(guān)鍵字值，并且指針q指向所找到的結(jié)點，p指向它的父結(jié)點；如果查找失敗，q＝NULL，p為q的父結(jié)點指針。

二叉排序樹查找遞歸算法二叉排序樹查找非遞歸算法BSTreeSearchBST2(BSTreet,intk){//二叉排序樹t中非遞歸查找某關(guān)鍵字等于k的數(shù)據(jù)元素，//若查找成功，則返回指向該數(shù)據(jù)元素結(jié)點的指針，//否則返回空指針

p=t;while(p!=NULL&&p->key!=k){if(k<p->key)p=p->lchild;elsep=p->rchild;

}returnp;}//SearchBST2

二叉排序樹上結(jié)點的插入步驟：（1）若二叉排序樹是空樹，則k成為二叉排序樹的根；（2）若二叉排序樹非空，則將k與二叉排序樹的根進行比較，如果k的值等于根結(jié)點的值，則停止插入；如果k的值小于根結(jié)點的值，則將k插入左子樹；如果k的值大于根結(jié)點的值，則將k插入右子樹。

插入算法voidInsertBST(BSTree

t,intk){//若二叉排序樹t中沒有關(guān)鍵字k，則插入，否則直接返回

p=t;//p的初值指向根結(jié)點

while(p)//查找插入位置

{if(p->key==k)return;//已有k，無需插入

f=p;//f保存當(dāng)前查找的結(jié)點

p=(k<p->key)?p->lchild:p->rchild;

//若k<p->key，在左子樹上查找，否則在右子樹上查找

}

p=(BSTree)malloc(sizeof(BSTNode));p->key=k;p->lchild=p->rchild=NULL;

if(t==NULL)t=p;elseif(k<f->key)f->lchild=p;elsef->rchild=p;}//InsertBST

123532264520(g)二叉排序樹的生成

(b)32(c)3226

(d)322645(a)?32264535

(e)3226451235

(f)設(shè)序列為(32,26,45,35,12,20)記錄的關(guān)鍵碼序列為：63，90，70，55，67，42，98，83，則構(gòu)造一棵二叉排序樹的過程如下：φ636390706390557063906755706390426755706390984267557063908398426755706390二叉排序樹上結(jié)點的刪除假設(shè)要刪除的結(jié)點為*p，結(jié)點*p的雙親結(jié)點為*f，并假設(shè)結(jié)點*p是結(jié)點*f的左孩子(右孩子的情況類似)。下面分三種情況討論：①若*p為葉子結(jié)點，則可直接將其刪除：f->1child＝NULL;free(p)；②若*p結(jié)點只有左子樹，或只有右子樹，則可將*p的左子樹或右子樹直接改為其雙親結(jié)點*f的左子樹，即：f->1child=p->1child(或f->1child=p->rchild);free(p)；FP*f*pP1FP1*fFP*f*pPrFPr*f③若*p既有左子樹，又有右子樹。則：令*p結(jié)點的直接前驅(qū)（或直接后繼）代替*p，然后再從二叉排序樹中刪除它的直接前驅(qū)（或直接后繼）。當(dāng)以直接前驅(qū)*s代替*p時，由于*s只有左子樹SL，則在刪去*s之后，只要令SL為*s的雙親*r的右子樹即可RQqFSFRPRpQLrRLSLSRQqFPFRPRpQLrsRLSL二叉排序樹上刪除10或40或45或555845439832405570639010voidDelete(BSTree

bst,keytypeX)//在二叉排序樹bst上，刪除其關(guān)鍵字為X的結(jié)點。

{BSTree

f,p=bst;while(p&&p->key!=X)//查找值為X的結(jié)點

if(p->key>X){f=p;p=p->lchild;}else{f=p;p=p->rchild;}if(p==null){printf(“無關(guān)鍵字為X的結(jié)點\n”);exit(0);}

if{p->lchild==null}//被刪結(jié)點無左子樹

if(f->lchild==p)f->lchild=p->rchild;//將被刪結(jié)點的右子樹接到其雙親上

elsef->rchild=p->rchild;

else//被刪結(jié)點有左子樹

{q=p;s=p->lchild;//s指向被刪結(jié)點左子樹的根

while(s->rchild!=null)//查左子樹中最右下的結(jié)點（中序最后結(jié)點）

{q=s;s=s->rchild;}p->key=s->key;//結(jié)點值用其左子樹最右下的結(jié)點的值代替

if(q==p)p->lchild=s->lchild;//被刪結(jié)點左子樹的根結(jié)點無右子女

elseq->rchild=s->lchild;//s是被刪結(jié)點左子樹中序最后一個結(jié)點

free(s);}}//算法結(jié)束

最佳二叉排序樹定義：平均查找長度最小的二叉排序樹。

舉例：形如滿二叉樹或完全二叉樹的二叉排序樹。非常難于構(gòu)造。折中：平衡二叉樹。平衡二叉樹定義：它或者是一棵空二叉樹，或者是二叉樹中任一結(jié)點的左、右子樹高度之差的絕對值不大于1，則稱這棵二叉樹為平衡二叉樹

平衡因子(bf)：結(jié)點的左、右子樹高度差為該結(jié)點的平衡因子

平衡的二叉樹示例01-1001-110100不平衡的二叉樹示例210-1001-201000平衡二叉樹的類型定義typedef

struct

AVLNode{intkey;

intbf;//結(jié)點的平衡因子

struct

AVLNode*lchild,*rchild;

//左、右孩子指針

}AVLNode,*AVLTree;

構(gòu)造平衡二叉樹方法：每當(dāng)插入一個結(jié)點時，首先檢查是否破壞了樹的平衡性，如果因插入結(jié)點而破壞了二叉排序樹的平衡，則找出其中最小不平衡子樹。所謂最小不平衡子樹是指離插入結(jié)點最近，且平衡因子的絕對值大于1的結(jié)點，因為此結(jié)點失去平衡，使得該結(jié)點的祖先結(jié)點也可能隨之失去平衡。所以，失衡后應(yīng)該調(diào)整以該結(jié)點為根的子樹。失去平衡的四種情況321223131132LL型RR型失去平衡的四種情況312233121132LR型RL型二叉平衡樹插入結(jié)點(結(jié)點旁的數(shù)字為其平衡因子)

示例15152127152121271521154327關(guān)鍵字的插入順序為(15，21，27，43，36，8，11)

RR示例關(guān)鍵字的插入順序為(15，21，27，43，36，8，11)

2127154336212715368432127154336示例關(guān)鍵字的插入順序為(15，21，27，43，36，8，11)

15211136827431521364327118(i)(j)LL型調(diào)整操作示意圖BABRBLAR0BAARBLSBR21

(b)調(diào)整后恢復(fù)平衡(a)插入結(jié)點S后失去平衡LL型調(diào)整的兩個例子01613125031251251631002(a)

BL、BR、AR

都是空樹(b)BL、BR、AR

都是非空樹9281631254728925163147281631254701010000010000210RR型調(diào)整操作示意圖BBRAALBL

(a)插入結(jié)點*s后失去平衡(b)調(diào)整后恢復(fù)平衡AAL-2BBRBL-1SRR型調(diào)整的兩個例子(a)AL、BL、BR

都是空樹69-1314703147-1473169000-20025470-1-2-100473169254700-100000-1031766940402576316940(b)AL、BL、BR

都是非空樹LR型調(diào)整操作示意圖(b)調(diào)整后恢復(fù)平衡

CACRAR0BBLCL00BAARCLCR2-1BLCS

(a)插入結(jié)點*s后失去平衡LR型調(diào)整的三個例子281312503125-128253100020261628253147312547-10226281610031254700128160000000-10

(b)LR(L)型調(diào)整(a)LR(0)型調(diào)整LR型調(diào)整的三個例子312547-102302816-1003125470012816000301628253147001000(c)LR(R)型調(diào)整RL型調(diào)整操作示意圖

(b)調(diào)整后恢復(fù)平衡CBCRBRAALCLBAALBRCLSCCR

(a)插入結(jié)點*s后失去平衡RL型調(diào)整的三個例子(a)RL(0)型調(diào)整40-13147031471403147000-20(b)

RL(L)型調(diào)整31254701-236406910031254700-169400003625403147690000-10RL型調(diào)整的三個例子

(c)RL(R)型調(diào)整31254701-24369400-1031254700-16940000432540314769001000AVL樹上結(jié)點的插入

結(jié)點插入后，若平衡二叉樹失去了平衡，則要找到最小不平衡子樹當(dāng)插入樹中后，修改有關(guān)結(jié)點的平衡因子如何判斷根的子樹是否失去平衡，若失去平衡則要作相應(yīng)的處理AVL樹查找分析

深度為h的平衡二叉樹所具有的最少結(jié)點數(shù)。設(shè)以Nh表示深度為h的平衡二叉樹中含有的最少結(jié)點數(shù)。N0＝0，N1=1，N2=2，并且Nh＝Nh-1+Nh-2+1。利用歸納法可證明：當(dāng)h≥0時，Nh=Fh+2-1。含有n個結(jié)點的平衡二叉樹的最大深度，即在AVL上進行查找的時間復(fù)雜度為O(logn)。B-樹1970年Bayer提出B-樹多路平衡外查找樹。前面討論的查找方法適用于組織規(guī)模較小、內(nèi)存中能容納的數(shù)據(jù)，是內(nèi)查找方法

B-樹是一種平衡、有序、多路、動態(tài)的查找樹，它是磁盤文件系統(tǒng)中索引技術(shù)常用的一種數(shù)據(jù)結(jié)構(gòu)形式，如磁盤管理系統(tǒng)中的目錄管理以及數(shù)據(jù)文件中的索引機構(gòu)大多采用B-樹B-樹B-樹的定義一棵m階的B-樹，或為空樹，或為滿足下列特性的m叉樹：(1)樹中每個結(jié)點至多有m棵子樹；(2)若根結(jié)點不是葉子結(jié)點，則至少有兩棵子樹；(3)除根結(jié)點之外的所有非終端結(jié)點至少有棵子樹；(4)所有的非終端結(jié)點中包含下列信息數(shù)據(jù)（n,P0,K1,P1,K2,P2,…,Kn,Pn），其中：Ki(i=1,…,n)為關(guān)鍵字，且Ki<Ki+1(i=1,…,n-1)，Pi(i=0,…,n)為指向子樹根結(jié)點的指針，且指針Pi-1所指子樹中所有結(jié)點的關(guān)鍵字均小于Ki(i=1,…,n)，Pn所指子樹中所有結(jié)點的關(guān)鍵字均大于Kn，n（m/2-1≤n≤m-1）為關(guān)鍵字的個數(shù)。(5)所有葉子結(jié)點都出現(xiàn)在同一層次上，并且不帶信息（可以看作是外部結(jié)點或查找失敗的結(jié)點，實際上這些結(jié)點不存在，指向這些結(jié)點的指針為空）。B-樹示例256154071502386345301058024016121109223177162294281273336320317375363487456419890782613568abcdefghijk一棵5階B-樹B-樹的查找查找過程包括兩種基本操作

(1)順指針查找結(jié)點；(2)在結(jié)點中順序查找關(guān)鍵字；

查找算法TreeSearchBTree(BTree

t,int

k,int*pos){//在B-樹查找關(guān)鍵字k，成功時返回結(jié)點的地址及k在其中的位置*pos，失敗返回NULLt->key[0]=k;//設(shè)置哨兵，下面用順序查找key[1..keynum]

for(i=t->keynum;k<t->key[i];i--);

//從后向前找第1個小于等于k的關(guān)鍵字

if(i>0&&t->key[i]==k)//查找成功，返回t及i{*pos=i;returnt;}//結(jié)點內(nèi)查找失敗，但t->key[i]<k<t->key[i+1]下一個查找結(jié)點應(yīng)為son[i]

if(!t->son[i])//*t為葉子，在葉子中仍未找到k，則查找過程失敗

returnNULL;

DiskRead[t->son[i]];//從磁盤上讀入下一個查找的樹結(jié)點到內(nèi)存中

returnSearchBTree(t->son[i],k,pos);//遞歸的繼續(xù)查找子樹t->son[i]}//

SearchBTree

B-樹查找分析在含有N個關(guān)鍵字的B-樹上進行查找時，從根結(jié)點到關(guān)鍵字所在結(jié)點的路徑上涉及的結(jié)點數(shù)不超過

若N=1,999,999,m=199，則查找次數(shù)至多為4。B-樹查找長度分析第一層至少有1個結(jié)點；第二層至少有2個結(jié)點；第三層至少有2*m/2個結(jié)點，…，依次類推;第L+1層至少有2*(m/2)L-1個結(jié)點；而L+1層的結(jié)點為葉子結(jié)點,數(shù)量為N+1;N+1>=2*(m/2)L-1;即L<=logm/2((N+1)/2)+1

。附：S=N+1的推導(dǎo)設(shè)B-樹某結(jié)點的子樹數(shù)為Ci，則該結(jié)點的關(guān)鍵字?jǐn)?shù)Ni=Ci-1。對于有k個結(jié)點的B-樹，有∑Ni=∑(Ci-1)=∑Ci-k（1≤i≤k）

（1）因為B樹上的關(guān)鍵字?jǐn)?shù)，即∑Ni=N（1≤i≤k）（2）而B-樹上的子樹數(shù)可這樣計算：每個結(jié)點（除根結(jié)點）都是一棵子樹，設(shè)葉子（子樹）數(shù)為S；則∑Ci=(k-1)+S（1≤i≤k）（3）綜合（1）（2）（3）式，有s=n+1。證畢。B-樹的插入插入操作先要通過查找確定插入的位置，然后可按以下三種情形分別進行處理：情形2：插入關(guān)鍵字的結(jié)點在插入后，關(guān)鍵字的個數(shù)超過m-1，則進行分裂處理。假設(shè)當(dāng)前處理的結(jié)點由q指向，以為界，將結(jié)點*q分裂成兩個結(jié)點，前面-1個關(guān)鍵字組成一部分仍由q指向，其余后面的一部分由q1指向，而中間的一個關(guān)鍵字帶著指針ql被“上擠”到雙親結(jié)點中。

情形3：在執(zhí)行情形2的“上擠”處理后，雙親結(jié)點中的關(guān)鍵字個數(shù)也超過了m-1個，則必須以該雙親結(jié)點為當(dāng)前結(jié)點，進行相同的處理，也就是說要繼續(xù)“上擠”直至根結(jié)點。一旦根結(jié)點中的關(guān)鍵字個數(shù)超過了m-1個，對根結(jié)點進行分裂處理后，整個B-樹的層數(shù)即增加一層

情形1：插入關(guān)鍵字的結(jié)點在插入后，關(guān)鍵字的個數(shù)不超過m-1，則將給定的關(guān)鍵字插入到該結(jié)點的相應(yīng)位置，插入過程即完成。插入結(jié)點后的分裂插入后：m,P0,(K1,P1,),…,(Km,Pm);

Ki<Ki+1(1<=i<m)

分成*p’和*q’兩個結(jié)點:p’:m/2-1,P0,(K1,P1),…,(Km/2-1,Pm/2-1)q’:m-m/2,Pm/2,(Km/2+1,Pm/2+1),…,(Km,Pm)Km/2和p’一起插入到P結(jié)點中。B-樹上插入結(jié)點3階B-樹上插入結(jié)點561824q2031q1(c)561881(e)18

5681bt(d)5618202431q(b)24

315618(a)插入結(jié)點示例56183572(a)5618357283(b)567283182135(c)215618728335(d)插入結(jié)點示例21561835697283(e)

56217218356983(g)(f)

21567218356983B-樹的刪除

在B-樹上刪除一個關(guān)鍵字，則首先要找到該關(guān)鍵字所在的結(jié)點，并從中刪除之。若該結(jié)點為最下層的非終端結(jié)點，且其中的關(guān)鍵字個數(shù)不少于