第八章 二叉搜索樹

第八章二叉搜索樹

理解以有序集為基礎(chǔ)的抽象數(shù)據(jù)類型字典。理解用數(shù)組實現(xiàn)字典的方法。理解二叉搜索樹的概念和實現(xiàn)方法。掌握用二叉搜索樹實現(xiàn)字典的方法。理解AVL樹的定義和性質(zhì)。掌握二叉搜索樹的結(jié)點旋轉(zhuǎn)變換及實現(xiàn)方法。掌握AVL樹的插入重新平衡運算及實現(xiàn)方法。掌握AVL樹的刪除重新平衡運算及實現(xiàn)方法。8.1字典的定義字典是以有序集為基礎(chǔ)的抽象數(shù)據(jù)類型。它支持以下運算：

(1)Member(x)，成員運算。

(2)Insert(x)，插入運算：將元素x插入集合。

(3)Delete(x)，刪除運算：將元素x從當前集合中刪去。

(4)Predecessor(x)，前驅(qū)運算：返回集合中小于x的最大元素。

(5)Successor(x)，后繼運算：返回集合中大于x的最小元素。

(6)Range(x，y)，區(qū)間查詢運算：返回集合中界于x和y之間，即x≤z≤y的所有元素z組成的集合。

(7)Min()，最小元運算：返回當前集合中依線性序最小的元素。

2第八章二叉搜索樹

8.2用數(shù)組實現(xiàn)字典

用數(shù)組實現(xiàn)字典與用數(shù)組實現(xiàn)字典的不同之處： 可以利用線性序?qū)⒆值渲械脑貜男〉酱笠佬虼鎯υ跀?shù)組中，通過數(shù)組下標來反映字典元素之間的序關(guān)系。優(yōu)點：可用二分法高效地實現(xiàn)與線性序有關(guān)的一些運算。如：Member(x)，Predecessor(x)和

Successor(x)可在時間O(logn)內(nèi)實現(xiàn)。缺點：插入和刪除運算的效率較低。每執(zhí)行一次Insert或Delete運算，需要移動部分數(shù)組元素，從而導(dǎo)致它們在最壞情況下的計算時間為O(n)?？紤]：能否用鏈表來實現(xiàn)字典？？？Member運算需要O(n)時間，一旦找到元素在鏈表中插入或刪除的位置后，只要用O(1)時間就可完成插入或刪除操作。

兩種實現(xiàn)方式均不可??！第八章二叉搜索樹

8.3用二叉搜索樹實現(xiàn)字典8.3.1基本思想：

用二叉樹來存儲有序集，每一個結(jié)點存儲一個元素。滿足：存儲于每個結(jié)點中的元素x大于其左子樹中任一結(jié)點中所存儲的元素，小于其右子樹中任一結(jié)點中所存儲的元素。4第八章二叉搜索樹

例

{10，18，3，8，12，2，7，4}1010181018310183810183812210183812710183812247101838122二叉搜索樹的建立過程：運算Insert(constT&x)的實現(xiàn)：template<classT>BinaryTreeNode<T>*BSTree<T>::Insert(constT&x){ BinaryTreeNode<T>*p=root,*pp=0; //從根開始檢測插入位置,*pp記錄插入結(jié)點的父結(jié)點

while(p)//p非空，選擇其左或右子樹進行插入

{ pp=p; if(x<p->data) p=p->LeftChild; elseif(x>p->data) p=p->RightChild; else return0;//表明x在樹中，無需插入

}BinaryTreeNode<T>*r=newBinaryTreeNode<T>(x);if(root)//當前樹非空{(diào) //確定x作為*pp的左兒子還是右兒子

if(x<pp->data) pp->LeftChild=r;else pp->RightChild=r;r->Parent=pp;}else root=r;returnr;}//Insert(x)運算結(jié)束運算Insert(constT&x)的實現(xiàn)：運算Search(constT&x)的實現(xiàn)template<classT>BinaryTreeNode<T>*BSTree<T>::Search(constT&x)const//找指向x所在的結(jié)點的指針{ BinaryTreeNode<T>*p=root; while(p)//*p中有元素

if(x<p->data) p=p->LeftChild; elseif(x>p->data) p=p->RightChild; else break;//找到x所在的結(jié)點*p returnp;//當x不在樹中時p為空}刪除508060120110150557053刪除6080551201101505370805012060110150557053刪除43例80501206011015055705343運算Delete(constT&x)的實現(xiàn)運算Delete(constT&x)的實現(xiàn)（續(xù)）設(shè)要刪除二叉搜索樹中的結(jié)點p，分三種情況：p為葉結(jié)點

直接刪除節(jié)點pp只有左子樹或右子樹p只有左子樹

用p的左兒子代替pp只有右子樹

用p的右兒子代替pp左、右子樹均非空找p的左子樹的最大元素結(jié)點（即p的前驅(qū)結(jié)點），用該結(jié)點代替結(jié)點p，然后刪除該結(jié)點。運算Delete(constT&x)的實現(xiàn)（續(xù)）template<classT>BinaryTreeNode<T>*BSTree<T>::Delete(constT&x){ BinaryTreeNode<T>*p=root,*pp=0;//從根開始搜索值為x的結(jié)點,*pp記該結(jié)點的父結(jié)點

while(p&&p->data!=x) {

pp=p; if(x<p->data) p=p->LeftChild; else p=p->RightChild; } if(!p) return0;//x不在樹中,無需刪除

if(p->LeftChild&&p->RightChild)//p有2個兒子結(jié)點{//找真正要刪除的結(jié)點:左子樹的最大元素結(jié)點

BinaryTreeNode<T>*s=p->LeftChild,

*ps=p; while(s->RightChild) { ps=s; s=s->RightChild; } p->data=s->data;//實現(xiàn)x的刪除（替代）

p=s; pp=ps} //此時p最多只有1個兒子結(jié)點,正是要刪除的結(jié)點BinaryTreeNode<T>*c;if(p->LeftChild) c=p->LeftChild;//c保存p唯一的左兒子else c=p->RightChild; //c保存p唯一的右兒子if(p==root){ root=c; if(c)c->Parent=0;}else{ //確定p是其父結(jié)點的左兒子還是右兒子

if(p==pp->LeftChild) pp->LeftChild=c; else pp->RightChild=c;if(c) c->Parent=p->Parent;}deletep;returnc;}//Delete(x)運算結(jié)束用二叉搜索樹實現(xiàn)字典時間復(fù)雜性分析最壞情況分析—member,insert,delete都需要O(n)平均情況分析 引入記號:

記：p(n)為含有n個結(jié)點的二叉搜索樹的平均查找長度。 顯然p(0)=0,p(1)=1;

若設(shè)某二叉搜索樹的左子樹有i個結(jié)點，則：

p(i)+1為查找左子樹中每個結(jié)點的平均查找長度;

p(n-i-1)+1為查找右子樹中每個結(jié)點的平均查找長度；

由此構(gòu)造而得的二叉搜索樹在n個結(jié)點的查找概率相等的情況下，其平均查找長度為：對n用數(shù)學歸納法可以證明:又假設(shè)當前的二叉搜索樹有n個結(jié)點，而它是從空樹開始反復(fù)調(diào)用n次的Insert運算得到的，且被插入的n個元素的所有可能的順序是等概率的。則：當n=1時顯然成立。若設(shè)i<n時有，則平均情況下的時間復(fù)雜度為：略去-1/n項運算Predecessor(x)和Successor(x)的實現(xiàn)：

——類似于Search(x)算法運算Range(y,z)的實現(xiàn)：可借助于Search(y)和Successor(y)運算首先，用Search(y)檢測y是否在二叉搜索樹中，是則輸出y，否則不輸出y；然后，從y開始，不斷地用Successor找當前元素在二叉搜索樹中的后繼元素。當找出的后繼元素x滿足xz時，就輸出x，并將x作為當前元素。重復(fù)這個過程，直到找出的當前元素的后繼元素大于z，或二叉搜索樹中已沒有后繼元素為止。時間復(fù)雜度：若二叉樹搜索樹中有r個元素x滿足

yxz，則在最壞情況下用時間，在平均情況下用時間可實現(xiàn)Range運算。

運算Range(y,z)的改進：考慮半無限查詢區(qū)域, ——即找出二叉搜索樹中滿足yx的所有元素x。當y不在二叉搜索樹中時，產(chǎn)生一條從根到葉的路徑。如下圖(a)當y在二叉搜索樹中時，產(chǎn)生一條從根到存儲元素y的結(jié)點的路徑。如下圖(b)在找到的搜索路徑上的所有結(jié)點可分為以下3種情況，如下圖：運算Range(y,z)的實現(xiàn)：

——可用類似于Range(y,∞)算法從二叉搜索樹的根結(jié)點開始，同時與y和z比較,此時,結(jié)點分類的情況可能有（見下圖）：運算Range(y,z)的搜索路徑如下圖：

8.4AVL樹8.4.0引言—AVL樹產(chǎn)生的背景問題的提出:用二叉搜索樹實現(xiàn)有序字典在最壞情況下—member,insert,delete都需要O(n);平均情況下需要O(logn)。問在最壞情況下能降到O(logn)嗎？8.4AVL樹8.4.0引言—AVL樹產(chǎn)生的背景(續(xù))解決問題的設(shè)想:

n個結(jié)點的二叉樹最矮是近似滿二叉樹,其高為[logn]。若放寬此限制為每一個結(jié)點的左子樹與右子樹高度差的絕對值不超過1，則二叉樹當然就達不到最矮,卻可望接近最矮,而不超過O(logn),目的就達到了。這正是AVL樹。剩下的問題是設(shè)法找一種在insert和delete后只需O(logn)時間的維護算法。設(shè)想的證實:(1)n個結(jié)點的AVL樹的高度為O(logn);(2)insert和delete后的維護算法在最壞的情況下只需O(logn)的時間。8.4AVL樹8.4.1AVL樹的定義和性質(zhì)遞歸定義:空的和單結(jié)點的二叉搜索樹都是AVL樹;結(jié)點數(shù)大于1的二叉搜索樹,若滿足左子樹和右子樹都是AVL樹且左、右子樹高度之差的絕對值不超過1,那么,它是AVL樹。性質(zhì):(1)AVL樹T的結(jié)點數(shù)n與高度h的關(guān)系。設(shè)高度h的AVL樹的最少結(jié)點數(shù)N(h)。N(h)一定出現(xiàn)在樹的左、右子樹中一棵高為h-1,而另一棵高為h-2時。則N(h)滿足如下遞歸方程：

8.4AVL樹

解上面的遞歸方程得：由于因此8.4AVL樹8.4.2旋轉(zhuǎn)變換

旋轉(zhuǎn)變換的目的：是調(diào)整結(jié)點的子樹高度，并維持二叉搜索樹性質(zhì)，即結(jié)點中元素的中序性質(zhì)。旋轉(zhuǎn)變換分為單旋轉(zhuǎn)變換和雙旋轉(zhuǎn)變換2種類型。單旋轉(zhuǎn)變換又分為右單旋轉(zhuǎn)變換和左單旋轉(zhuǎn)變換。雙旋轉(zhuǎn)變換又分為先左后右雙旋轉(zhuǎn)變換和先右后左雙旋轉(zhuǎn)變換。1、左單旋的情況原來的AVL樹插入一結(jié)點，A點不平衡左單旋的結(jié)果2.右單旋的情況原來的AVL樹插入一結(jié)點，A點不平衡右單旋的結(jié)果原來的AVL樹插入一結(jié)點，A點不平衡先左旋再右旋3.先左后右雙旋的情況4.先右后左雙旋的情況原來的AVL樹插入一結(jié)點，A點不平衡先右旋再左旋8.4AVL樹8.4.3AVL樹的插入運算AVL樹與二叉搜索樹的插入運算是類似的。惟一的不同之處是，在AVL樹中執(zhí)行1次二叉搜索樹的插入運算，可能會破壞AVL樹的高度平衡性質(zhì)，因此需要重新平衡。設(shè)新插入的結(jié)點為v。從根結(jié)點到結(jié)點v的路徑上，每個結(jié)點處插入運算所進入的子樹高度可能增1。因此在執(zhí)行1次二叉搜索樹的插入運算后，需從新插入的結(jié)點v開始，沿此插入路徑向根結(jié)點回溯，修正平衡因子，調(diào)整子樹高度，恢復(fù)被破壞的平衡性質(zhì)。8.4AVL樹8.4.3AVL樹的插入運算新結(jié)點v的平衡因子為0?，F(xiàn)考察v的父結(jié)點u。若v是u的左兒子結(jié)點，則bal(u)應(yīng)當減1，否則bal(u)應(yīng)當增1。根據(jù)修正后的bal(u)的值分以下3種情形討論。情形1：bal(u)=0。此時以結(jié)點u為根的子樹平衡，且其高度不變。因此從根結(jié)點到結(jié)點u的路徑上各結(jié)點子樹高度不變，從而各結(jié)點的平衡因子不變。此時可結(jié)束重新平衡過程。情形2：|bal(u)|=1。此時以結(jié)點u為根的子樹滿足平衡條件，但其高度增1。此時將當前結(jié)點向根結(jié)點方向上移，繼續(xù)考察結(jié)點u的父結(jié)點的平衡狀態(tài)。8.4AVL樹情形3：|bal(u)|=2。先討論bal(u)=-2的情形。易知，此時結(jié)點v是結(jié)點u的左兒子結(jié)點，且bal(v)0。又可分為2種情形。情形3.1：bal(v)=-1。此時作1次右單旋轉(zhuǎn)變換后，結(jié)束重新平衡過程。情形3.2：bal(v)=1。此時結(jié)點v的右兒子結(jié)點x非空。根據(jù)bal(x)的值，又分為bal(x)=0、bal(x)=-1和bal(x)=1的3種情形。在這3種情形下，分別作1次雙旋轉(zhuǎn)變換后，結(jié)束重新平衡過程。情形3.1：情形3.2

：

bal(x)=0情形3.2

：

bal(x)=-1情形3.2

：

bal(x)=18.4AVL樹8.4.4AVL樹的刪除運算

AVL樹與二叉搜索樹的刪除運算是類似的。惟一的不同之處是，在AVL樹中執(zhí)行1次二叉搜索樹的刪除運算，可能會破壞AVL樹的高度平衡性質(zhì)，因此需要重新平衡。設(shè)被刪除結(jié)點為p，其惟一的兒子結(jié)點為v。結(jié)點p被刪除后，結(jié)點v取代了它的位置。從根結(jié)點到結(jié)點v的路徑上，每個結(jié)點處刪除運算所進入的子樹高度可能減1。因此在執(zhí)行1次二叉搜索樹的刪除運算后，需從結(jié)點v開始，沿此刪除路徑向根結(jié)點回溯，修正平衡因子，調(diào)整子樹高度，恢復(fù)