二叉搜索樹(BinarySearchTree)課件

二叉搜索樹(BinarySearchTree)定義

二叉搜索樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：每個(gè)結(jié)點(diǎn)都有一個(gè)作為搜索依據(jù)的關(guān)鍵碼(key)，所有結(jié)點(diǎn)的關(guān)鍵碼互不相同。左子樹（如果非空）上所有結(jié)點(diǎn)的關(guān)鍵碼都小于根結(jié)點(diǎn)的關(guān)鍵碼。右子樹（如果非空）上所有結(jié)點(diǎn)的關(guān)鍵碼都大于根結(jié)點(diǎn)的關(guān)鍵碼。左子樹和右子樹也是二叉搜索樹。1351545504025102030二叉搜索樹例結(jié)點(diǎn)左子樹上所有關(guān)鍵碼小于結(jié)點(diǎn)關(guān)鍵碼；右子樹上所有關(guān)鍵碼大于結(jié)點(diǎn)關(guān)鍵碼；注意：若從根結(jié)點(diǎn)到某個(gè)葉結(jié)點(diǎn)有一條路徑，路徑左邊的結(jié)點(diǎn)的關(guān)鍵碼不一定小于路徑上的結(jié)點(diǎn)的關(guān)鍵碼。如箭頭所示路徑。2性質(zhì)：如果對(duì)一棵二叉搜索樹進(jìn)行中序遍歷，可以按從小到大的順序，將各結(jié)點(diǎn)關(guān)鍵碼排列起來，所以也稱二叉搜索樹為二叉排序樹(BST)。二叉搜索樹的類定義——略二叉搜索樹的類定義用二叉鏈表作為它的存儲(chǔ)表示，許多操作的實(shí)現(xiàn)與二叉樹類似。3二叉搜索樹的搜索算法在二叉搜索樹上進(jìn)行搜索，是一個(gè)從根結(jié)點(diǎn)開始，沿某一個(gè)分支逐層向下進(jìn)行比較判等的過程。它可以是一個(gè)遞歸的過程。假設(shè)想要在二叉搜索樹中搜索關(guān)鍵碼為x

的元素，搜索過程從根結(jié)點(diǎn)開始。如果根指針為NULL，則搜索不成功；否則用給定值

x

與根結(jié)點(diǎn)的關(guān)鍵碼進(jìn)行比較：若給定值等于根結(jié)點(diǎn)關(guān)鍵碼，則搜索成功，返回搜索成功信息并報(bào)告搜索到結(jié)點(diǎn)地址。4若給定值小于根結(jié)點(diǎn)的關(guān)鍵碼，則繼續(xù)遞歸搜索根結(jié)點(diǎn)的左子樹；否則。遞歸搜索根結(jié)點(diǎn)的右子樹。搜索45搜索成功搜索28搜索失敗3515455040251020305BSTNode*Search(Tx,

BSTNode*subtree){//遞歸算法：在以

subtree

為根的二叉搜索樹中//

搜索含x的結(jié)點(diǎn)。若找到，則函數(shù)返回該結(jié)點(diǎn)//的地址，否則函數(shù)返回NULL值。 if(subtree==NULL)returnNULL;

elseif(x<subtree->data) returnSearch(x,subtree->left); elseif(x>subtree->data) returnSearch(x,

subtree->right); elsereturnsubtree; //搜索成功}6BSTNode*Search(Tx,

BSTNode*subtree){//迭代算法：在當(dāng)前以subtree

為根的二叉搜索//樹中搜索含x的結(jié)點(diǎn)。若找到，則函數(shù)返回該//結(jié)點(diǎn)的地址，否則函數(shù)返回NULL值。while(subtree!=NULL){

if(x==subtree->data)returnsubtree; if(x<subtree->data)

subtree=subtree->left; elsesubtree=subtree->right;}returnNULL;}7搜索過程是從根結(jié)點(diǎn)開始，沿某條路徑自上而下逐層比較判等的過程。搜索成功，搜索指針將停留在樹上某個(gè)結(jié)點(diǎn)；搜索不成功，搜索指針將走到樹上某個(gè)結(jié)點(diǎn)的空子樹。設(shè)樹的高度為h，最多比較次數(shù)不超過h。8二叉搜索樹的插入算法為了向二叉搜索樹中插入一個(gè)新元素，必須先檢查這個(gè)元素是否在樹中已經(jīng)存在。在插入之前，先使用搜索算法在樹中檢查要插入的元素在不在樹中。如果搜索成功，說明樹中已經(jīng)有這個(gè)元素，不再插入；如果搜索不成功，說明樹中原來沒有關(guān)鍵碼等于給定值的結(jié)點(diǎn)，把新元素加到搜索操作停止的地方。9插入新結(jié)點(diǎn)

28二叉搜索樹的插入每次結(jié)點(diǎn)的插入，都要從根結(jié)點(diǎn)出發(fā)搜索插入位置，然后把新結(jié)點(diǎn)作為葉結(jié)點(diǎn)插入。3515455040251020302810二叉搜索樹的插入算法bool

Insert(Te,BSTNode&subtree){//遞歸算法：在以subtree

為根的二叉搜索樹中插入//值為e的結(jié)點(diǎn)。若樹中已有結(jié)點(diǎn)e，則不插入

if(subtree==NULL){//新結(jié)點(diǎn)作為葉結(jié)點(diǎn)插入

subtree=newBSTNode(e);//創(chuàng)建新結(jié)點(diǎn) returntrue;}elseif(e<subtree->data)Insert(e,subtree->left); elseif(e>subtree->data)Insert(e,subtree->right);};11注意參數(shù)表中引用型指針參數(shù)subtree的使用。利用二叉搜索樹的插入算法，可以很方便地建立二叉搜索樹。

12輸入數(shù)據(jù)

{53,78,65,17,87,09,81,15}53537853786553786517537865871753786509178753786581178709537865151787098113voidcreateBST(TEndValue){//從鍵盤上輸入元素序列,建立一棵二叉搜索樹，//參數(shù)

EndValue

表示序列的結(jié)束符

root=NULL;//root為樹根，初始化為空樹

cin>>x; //輸入數(shù)據(jù)

while(x.key!=EndValue){ //RefValue是一個(gè)輸入結(jié)束標(biāo)志

Insert(x,root);cin>>x; //插入，再輸入數(shù)據(jù)

}}14二叉搜索樹的刪除算法在二叉搜索樹中刪除一個(gè)結(jié)點(diǎn)時(shí)，必須將因刪除結(jié)點(diǎn)而斷開的二叉鏈表重新鏈接起來，同時(shí)確保二叉搜索樹的性質(zhì)不會(huì)失去。為保證在刪除后樹的搜索性能不至于降低，還需要防止重新鏈接后樹的高度增加。刪除葉結(jié)點(diǎn)，只需將其雙親結(jié)點(diǎn)指向它的指針清零，再釋放它即可。被刪結(jié)點(diǎn)右子樹為空，可以拿它的左子女結(jié)點(diǎn)頂替它的位置，再釋放它。15被刪結(jié)點(diǎn)左子樹為空，可以拿它的右子女結(jié)點(diǎn)頂替它的位置，再釋放它。被刪結(jié)點(diǎn)左、右子樹都不為空，可以在它的右子樹中尋找中序下的第一個(gè)結(jié)點(diǎn)(關(guān)鍵碼最小),用它的值填補(bǔ)到被刪結(jié)點(diǎn)中，再來處理這個(gè)結(jié)點(diǎn)的刪除問題。5378651787092345刪除45右子樹空,用左子女頂替53786517870923168853788817940923刪除78左子樹空,用右子女頂替53948817092353788117940945刪除78在右子樹上找中序下第一個(gè)結(jié)點(diǎn)填補(bǔ)236553818817940945236517二叉搜索樹的刪除算法bool

Remove(x,BSTNode&subtree){//遞歸算法：在以subtree

為根的二叉搜索樹中//

刪除含x的結(jié)點(diǎn)

if(subtree==NULL)return

false;

if(x<subtree->data)//在左子樹中執(zhí)行刪除 returnRemove(x,subtree->left);

elseif(x>subtree->data)//在右子樹中執(zhí)行刪除

return

Remove(x,subtree->right);

else{//

找到了被刪結(jié)點(diǎn)18

//1.左、右子女均不空 if(subtree->left!=NULL&&

subtree->right!=NULL){ //subtree指示關(guān)鍵碼為x的結(jié)點(diǎn)，它有兩個(gè)子女 temp=subtree->right;

//到右子樹搜尋中序下第一個(gè)結(jié)點(diǎn)

while(temp->left!=NULL)temp=temp->left;

subtree->data=temp->data;

//用該結(jié)點(diǎn)數(shù)據(jù)代替根結(jié)點(diǎn)數(shù)據(jù) Remove(temp->data,subtree->right); }19 else{//subtree指示的結(jié)點(diǎn)最多有一個(gè)子女 temp=subtree;

if(subtree->left==NULL)subtree=

subtree->right; elsesubtree=subtree->left;deletetemp; returntrue; } }}注意在刪除算法參數(shù)表引用型指針參數(shù)的使用。20

二叉搜索樹性能分析對(duì)于有n個(gè)關(guān)鍵碼的集合，其關(guān)鍵碼有n!種不同排列，可構(gòu)成不同二叉搜索樹有

(棵)

{2,1,3}{1,2,3}{1,3,2}{2,3,1}{3,1,2}{3,2,1}

12311113222332321同樣3個(gè)數(shù)據(jù){1,2,3}，輸入順序不同，建立起來的二叉搜索樹的形態(tài)也不同。這直接影響到二叉搜索樹的搜索性能。如果輸入序列選得不好，會(huì)建立起一棵單支樹，使得二叉搜索樹的高度達(dá)到最大。用樹的搜索效率來評(píng)價(jià)這些二叉搜索樹。為此，在二叉搜索樹中加入外結(jié)點(diǎn)，形成判定樹。外結(jié)點(diǎn)表示失敗結(jié)點(diǎn)，內(nèi)結(jié)點(diǎn)表示搜索樹中已有的數(shù)據(jù)。這樣的判定樹即為擴(kuò)充的二叉搜索樹。22舉例說明。已知關(guān)鍵碼集合

{a1,a2,a3}=

{do,if,to}，對(duì)應(yīng)搜索概率p1,p2,p3,在各搜索不成功間隔內(nèi)搜索概率分別為q0,q1,q2,q3?？赡艿亩嫠阉鳂淙缦滤?。doiftodoiftoq0q1p1q2p2q3p3q0q1q2q3p1p2p3(a)(b)23判定樹doiftoq0q1p1q2p2q3p3doiftoq0q1p1q2p2q3p3(d)(c)doiftoq0q1p1q2p2q3p3(e)24在判定樹中

○表示內(nèi)部結(jié)點(diǎn)，包含了關(guān)鍵碼集合中的某一個(gè)關(guān)鍵碼；□表示外部結(jié)點(diǎn)，代表各關(guān)鍵碼間隔中的不在關(guān)鍵碼集合中的關(guān)鍵碼。在每?jī)蓚€(gè)外部結(jié)點(diǎn)間必存在一個(gè)內(nèi)部結(jié)點(diǎn)。一棵判定樹上