數(shù)據(jù)結構與算法-二叉搜索樹

第八章二叉搜索樹

理解以有序集為基礎的抽象數(shù)據(jù)類型字典。

理解用數(shù)組實現(xiàn)字典的方法。

理解二叉搜索樹的概念和實現(xiàn)方法。

掌握用二叉搜索樹實現(xiàn)字典的方法。

理解AVL樹的定義和性質(zhì)。

掌握二叉搜索樹的結點旋轉(zhuǎn)變換及實現(xiàn)方法。

掌握AVL樹的插入重新平衡運算及實現(xiàn)方法。

掌握AVL樹的刪除重新平衡運算及實現(xiàn)方法。10/11/20241福州大學數(shù)學與計算機科學學院8.1

字典的定義字典是以有序集為基礎的抽象數(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()，最小元運算：返回當前集合中依線性序最小的元素。

8二叉搜索樹10/11/20242福州大學數(shù)學與計算機科學學院8二叉搜索樹8.2

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

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

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

兩種實現(xiàn)方式均不可?。?0/11/20243福州大學數(shù)學與計算機科學學院8二叉搜索樹8.3

用二叉搜索樹實現(xiàn)字典8.3.1

基本思想：

用二叉樹來存儲有序集，每一個結點存儲一個元素。滿足：存儲于每個結點中的元素x大于其左子樹中任一結點中所存儲的元素，小于其右子樹中任一結點中所存儲的元素。10/11/20244福州大學數(shù)學與計算機科學學院運算Search(constT&x)的實現(xiàn)：template<classT>BinaryTreeNode<T>*BSTree<T>::Search(constT&x)const//找指向x所在的結點的指針{

BinaryTreeNode<T>*p=root; while(p)//*p中有元素

if(x<p->data) p=p->LeftChild; elseif(x>p->data) p=p->RightChild; else break;//找到x所在的結點*p returnp;//當x不在樹中時p為空}10/11/20245福州大學數(shù)學與計算機科學學院例

{10，18，3，8，12，2，7，4}1010181018310183810183812210183812710183812247101838122二叉搜索樹的建立過程：10/11/20246福州大學數(shù)學與計算機科學學院運算Insert(constT&x)的實現(xiàn)：template<classT>BinaryTreeNode<T>*BSTree<T>::Insert(constT&x){

BinaryTreeNode<T>*p=root,*pp=0; //從根開始檢測插入位置,*pp記錄插入結點的父結點

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

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

}10/11/20247福州大學數(shù)學與計算機科學學院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)運算結束10/11/20248福州大學數(shù)學與計算機科學學院刪除508060120110150557053刪除6080551201101505370805012060110150557053刪除43例80501206011015055705343運算Delete(constT&x)的實現(xiàn)10/11/20249福州大學數(shù)學與計算機科學學院運算Delete(constT&x)的實現(xiàn)（續(xù)）設要刪除二叉搜索樹中的結點p，分三種情況：p為葉結點

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

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

用p的右兒子代替pp左、右子樹均非空

找p的左子樹的最大元素結點（即p的前驅(qū)結點），用該結點代替結點p，然后刪除該結點。10/11/202410福州大學數(shù)學與計算機科學學院運算Delete(constT&x)的實現(xiàn)（續(xù)）template<classT>BinaryTreeNode<T>*BSTree<T>::Delete(constT&x){

BinaryTreeNode<T>*p=root,*pp=0;//從根開始搜索值為x的結點,*pp記該結點的父結點

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

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

10/11/202411福州大學數(shù)學與計算機科學學院if(p->LeftChild&&p->RightChild)//p有2個兒子結點{//找真正要刪除的結點:左子樹的最大元素結點

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和*pp分別保存真正要刪的結點和它的父親} //此時p最多只有1個兒子結點,正是要刪除的結點BinaryTreeNode<T>*c;if(p->LeftChild) c=p->LeftChild; //c保存p唯一的左兒子else c=p->RightChild; //c保存p唯一的右兒子10/11/202412福州大學數(shù)學與計算機科學學院if(p==root){ root=c; if(c)c->Parent=0;}else{ //確定p是其父結點的左兒子還是右兒子

if(p==pp->LeftChild) pp->LeftChild=c; else pp->RightChild=c;if(c) c->Parent=p->Parent;}deletep;returnc;}//Delete(x)運算結束10/11/202413福州大學數(shù)學與計算機科學學院用二叉搜索樹實現(xiàn)字典時間復雜性分析最壞情況分析—member,insert,delete都需要O(n)平均情況分析 引入記號:

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

若設某二叉搜索樹的左子樹有i個結點，則：

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

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

由此構造而得的二叉搜索樹在n個結點的查找概率相等的情況下，其平均查找長度為：10/11/202414福州大學數(shù)學與計算機科學學院對n用數(shù)學歸納法可以證明:又假設當前的二叉搜索樹有n個結點，而它是從空樹開始反復調(diào)用n次的Insert運算得到的，且被插入的n個元素的所有可能的順序是等概率的。則：當n=1時顯然成立。若設i<n時有，則10/11/202415福州大學數(shù)學與計算機科學學院

平均情況下的時間復雜度為：略去-1/n項10/11/202416福州大學數(shù)學與計算機科學學院運算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滿足x

z時，就輸出x，并將x作為當前元素。重復這個過程，直到找出的當前元素的后繼元素大于z，或二叉搜索樹中已沒有后繼元素為止。時間復雜度：若二叉樹搜索樹中有r個元素x滿足y

x

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

10/11/202417福州大學數(shù)學與計算機科學學院運算Range(y,z)的改進：考慮半無限查詢區(qū)域, ——即找出二叉搜索樹中滿足y

x的所有元素x。當y不在二叉搜索樹中時，產(chǎn)生一條從根到葉的路徑。如下圖(a)當y在二叉搜索樹中時，產(chǎn)生一條從根到存儲元素y的結點的路徑。如下圖(b)10/11/202418福州大學數(shù)學與計算機科學學院在找到的搜索路徑上的所有結點可分為以下3種情況，如下圖：10/11/202419福州大學數(shù)學與計算機科學學院運算Range(y,z)的實現(xiàn)：

——可用類似于Range(y,∞)算法從二叉搜索樹的根結點開始，同時與y和z比較,此時,結點分類的情況可能有（見下圖）：10/11/202420福州大學數(shù)學與計算機科學學院運算Range(y,z)的搜索路徑如下圖：

10/11/202421福州大學數(shù)學與計算機科學學院8.4AVL樹8.4.0

引言—AVL樹產(chǎn)生的背景問題的提出:用二叉搜索樹實現(xiàn)有序字典在最壞情況下—member,insert,delete都需要O(n);平均情況下需要O(logn)。

問在最壞情況下能降到O(logn)嗎？10/11/202422福州大學數(shù)學與計算機科學學院8.4AVL樹8.4.0

引言—AVL樹產(chǎn)生的背景(續(xù))解決問題的設想:

n個結點的二叉樹最矮是近似滿二叉樹,其高為[logn]。若放寬此限制為每一個結點的左子樹與右子樹高度差的絕對值不超過1，則二叉樹當然就達不到最矮,卻可望接近最矮,而不超過O(logn),目的就達到了。這正是AVL樹。剩下的問題是設法找一種在insert和delete后只需O(logn)時間的維護算法。設想的證實:(1)n個結點的AVL樹的高度為O(logn);(2)insert和delete后的維護算法在最壞的情況下只需O(logn)的時間。10/11/202423福州大學數(shù)學與計算機科學學院8.4AVL樹8.4.1

AVL樹的定義和性質(zhì)遞歸定義:空的和單結點的二叉搜索樹都是AVL樹;結點數(shù)大于1的二叉搜索樹,若滿足左子樹和右子樹都是AVL樹且左、右子樹高度之差的絕對值不超過1,那么,它是AVL樹。性質(zhì):(1)AVL樹T的結點數(shù)n與高度h的關系。設高度h的AVL樹的最少結點數(shù)N(h)。N(h)一定出現(xiàn)在樹的左、右子樹中一棵高為h-1,而另一棵高為h-2時。則N(h)滿足如下遞歸方程：

10/11/202424福州大學數(shù)學與計算機科學學院8.4AVL樹解上面的遞歸方程得：由于因此10/11/202425福州大學數(shù)學與計算機科學學院8.4AVL樹8.4.2

旋轉(zhuǎn)變換

旋轉(zhuǎn)變換的目的：是調(diào)整結點的子樹高度，并維持二叉搜索樹性質(zhì)，即結點中元素的中序性質(zhì)。旋轉(zhuǎn)變換分為單旋轉(zhuǎn)變換和雙旋轉(zhuǎn)變換2種類型。單旋轉(zhuǎn)變換又分為右單旋轉(zhuǎn)變換和左單旋轉(zhuǎn)變換。雙旋轉(zhuǎn)變換又分為先左后右雙旋轉(zhuǎn)變換和先右后左雙旋轉(zhuǎn)變換。10/11/202426福州大學數(shù)學與計算機科學學院1、左單旋的情況原來的AVL樹插入一結點，A點不平衡左單旋的結果10/11/202427福州大學數(shù)學與計算機科學學院2.右單旋的情況原來的AVL樹插入一結點，A點不平衡右單旋的結果10/11/202428福州大學數(shù)學與計算機科學學院原來的AVL樹插入一結點，A點不平衡先左旋再右旋3.先左后右雙旋的情況10/11/202429福州大學數(shù)學與計算機科學學院4.先右后左雙旋的情況原來的AVL樹插入一結點，A點不平衡先右旋再左旋10/11/202430福州大學數(shù)學與計算機科學學院8.4AVL樹8.4.3AVL樹的插入運算

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

10/11/202431福州大學數(shù)學與計算機科學學院8.4AVL樹8.4.3AVL樹的插入運算新結點v的平衡因子為0?，F(xiàn)考察v的父結點u。若v是u的左兒子結點，則bal(u)應當減1，否則bal(u)應當增1。根據(jù)修正后的bal(u)的值分以下3種情形討論。情形1：bal(u)=0。此時以結點u為根的子樹平衡，且其高度不變。因此從根結點到結點u的路徑上各結點子樹高度不變，從而各結點的平衡因子不變。此時可結束重新平衡過程。情形2：|bal(u)|=1。此時以結點u為根的子樹滿足平衡條件，但其高度增1。此時將當前結點向根結點方向上移，繼續(xù)考察結點u的父結點的平衡狀態(tài)。10/11/202432福州大學數(shù)學與計算機科學學院情形3：|bal(u)|=2。先討論bal(u)=-2的情形。易知，此時結點v是結點u的左兒子結點，且bal(v)

0。又可分為2種情形。情形3.1：bal(v)=-1。此時作1次右單旋轉(zhuǎn)變換后，結束重新平衡過程。情形3.2：bal(v)=1。此時結點v的右兒子結點x非空。根據(jù)bal(x)的值，又分為bal(x)=0、bal(x)=-1和bal(x)=1的3種情形。在這3種情形下，分別作1次雙旋轉(zhuǎn)變換后，結束重新平衡過程。8.4AVL樹10/11/202433福州大學數(shù)學與計算機科學學院情形3.1：10/11/202434福州大學數(shù)學與計算機科學學院情形3.2

：

bal(x)=010/11/202435福州大學數(shù)學與計算機科學學院情形3.2

：

bal(x)=-110/11/202436福州大學數(shù)學與計算機科學學院情形3.2

：

bal(x)=110/11/202437福州大學數(shù)學與計算機科學學院8.4AVL樹8.4.4AVL樹的刪除運算

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

10/11/202438福州大學數(shù)學與計算機科學學院8.4.4AVL樹的刪除運算

考察v的父結點u。若v是u的左兒子結點，則bal(u)應當增1，否則