數(shù)據(jù)結(jié)構(gòu)與算法-二叉搜索樹

第八章二叉搜索樹

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

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

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

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

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

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

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

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

字典的定義字典是以有序集為基礎(chǔ)的抽象數(shù)據(jù)類型。它支持以下運(yùn)算：

(1)Member(x)，成員運(yùn)算。

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

(3)Delete(x)，刪除運(yùn)算：將元素x從當(dāng)前集合中刪去。

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

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

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

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

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

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

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

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

兩種實(shí)現(xiàn)方式均不可??！10/11/20243福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院8二叉搜索樹8.3

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

基本思想：

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

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é)點(diǎn)*p returnp;//當(dāng)x不在樹中時(shí)p為空}10/11/20245福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院例

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

BinaryTreeNode<T>*p=root,*pp=0; //從根開始檢測(cè)插入位置,*pp記錄插入結(jié)點(diǎn)的父結(jié)點(diǎn)

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

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

}10/11/20247福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院BinaryTreeNode<T>*r=newBinaryTreeNode<T>(x);if(root)//當(dāng)前樹非空{(diào) //確定x作為*pp的左兒子還是右兒子

if(x<pp->data) pp->LeftChild=r;else pp->RightChild=r;r->Parent=pp;}else root=r;returnr;}//Insert(x)運(yùn)算結(jié)束10/11/20248福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院刪除508060120110150557053刪除6080551201101505370805012060110150557053刪除43例80501206011015055705343運(yùn)算Delete(constT&x)的實(shí)現(xiàn)10/11/20249福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院運(yùn)算Delete(constT&x)的實(shí)現(xiàn)（續(xù)）設(shè)要?jiǎng)h除二叉搜索樹中的結(jié)點(diǎn)p，分三種情況：p為葉結(jié)點(diǎn)

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

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

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

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

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

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

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

10/11/202411福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院if(p->LeftChild&&p->RightChild)//p有2個(gè)兒子結(jié)點(diǎn){//找真正要?jiǎng)h除的結(jié)點(diǎn):左子樹的最大元素結(jié)點(diǎn)

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

*ps=p;

while(s->RightChild) {

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

p=s; pp=ps;//用*p和*pp分別保存真正要?jiǎng)h的結(jié)點(diǎn)和它的父親} //此時(shí)p最多只有1個(gè)兒子結(jié)點(diǎn),正是要?jiǎng)h除的結(jié)點(diǎn)BinaryTreeNode<T>*c;if(p->LeftChild) c=p->LeftChild; //c保存p唯一的左兒子else c=p->RightChild; //c保存p唯一的右兒子10/11/202412福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院if(p==root){ root=c; if(c)c->Parent=0;}else{ //確定p是其父結(jié)點(diǎn)的左兒子還是右兒子

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

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

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

p(i)+1為查找左子樹中每個(gè)結(jié)點(diǎn)的平均查找長(zhǎng)度;

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

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

平均情況下的時(shí)間復(fù)雜度為：略去-1/n項(xiàng)10/11/202416福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院運(yùn)算Predecessor(x)和Successor(x)的實(shí)現(xiàn)：

——類似于Search(x)算法運(yùn)算Range(y,z)的實(shí)現(xiàn)：可借助于Search(y)和Successor(y)運(yùn)算首先，用Search(y)檢測(cè)y是否在二叉搜索樹中，是則輸出y，否則不輸出y；然后，從y開始，不斷地用Successor找當(dāng)前元素在二叉搜索樹中的后繼元素。當(dāng)找出的后繼元素x滿足x

z時(shí)，就輸出x，并將x作為當(dāng)前元素。重復(fù)這個(gè)過(guò)程，直到找出的當(dāng)前元素的后繼元素大于z，或二叉搜索樹中已沒(méi)有后繼元素為止。時(shí)間復(fù)雜度：若二叉樹搜索樹中有r個(gè)元素x滿足y

x

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

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

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

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

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

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

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

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

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

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

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

旋轉(zhuǎn)變換

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

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

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

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

：

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

：

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

：

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

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

10/11/202438福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院8.4.4AVL樹的刪除運(yùn)算

考察v的父結(jié)點(diǎn)u。若v是u的左兒子結(jié)點(diǎn)，則bal(u)應(yīng)當(dāng)增1，否則