課件54二叉搜索樹

5二叉樹2/985.1二叉樹的概念5.2二叉樹的周游5.3二叉樹的存儲結(jié)構(gòu)5.4二叉搜索樹5.5堆與優(yōu)先隊列5.6Huffman樹及其應(yīng)用5.7二叉樹知識點總結(jié)主要內(nèi)容3/98二叉搜索樹二叉搜索樹二叉搜索樹的查找二叉搜索樹的插入操作二叉搜索樹的刪除操作4/98二叉搜索樹一棵非空的二叉搜索樹滿足以下特征：每個結(jié)點都有一個作為搜索依據(jù)的關(guān)鍵碼，所有結(jié)點的關(guān)鍵碼互不相同。左子樹（如果存在）上的所有結(jié)點的關(guān)鍵碼均小于根結(jié)點的關(guān)鍵碼。右子樹（如果存在）上的所有結(jié)點的關(guān)鍵碼均大于根結(jié)點的關(guān)鍵碼。根結(jié)點的左右子樹也都是二叉搜索樹。二叉搜索樹又稱為“二叉排序樹”、“二叉查找樹”、“二叉檢索樹”5/98二叉搜索樹舉例LNPEMCY12225030011020099105230216607080505540是二叉搜索樹是二叉搜索樹不是二叉搜索樹6/98二叉搜索樹的基本操作查找插入刪除7/98二叉搜索樹查找操作分割式查找法：若根結(jié)點的關(guān)鍵碼等于查找的關(guān)鍵碼，成功。否則，若小于根結(jié)點的關(guān)鍵碼，查其左子樹。大于根結(jié)點的關(guān)鍵碼，查其右子樹。二叉搜索樹的高效率在于繼續(xù)檢索時只需要查找兩棵子樹之一8/9813

85231837如何查找元素5?555查找成功！二叉搜索樹查找操作9/98二叉搜索樹查找分析——平均情況分析

156070302050156070302050ASL=(1+2+2+3+3+3)/6=14/6ASL=(1+2+3+4+5+6)/6=21/610/98二叉搜索樹插入操作首先執(zhí)行查找算法，找出被插結(jié)點的父親結(jié)點。判斷被插結(jié)點是其父親結(jié)點的左、右兒子。將被插結(jié)點作為葉子結(jié)點插入。若二叉樹為空。則首先單獨生成根結(jié)點。注意：新插入的結(jié)點總是葉子結(jié)點。11/98【算法5.9】二叉搜索樹的結(jié)點插入算法template<classT>voidBinarySearchTree<T>::InsertNode(BinaryTreeNode<T>*root,BinaryTreeNode<T>*newpointer){BinaryTreeNode<T>*pointer=NULL; if(root==NULL){ //如果是空樹

Initialize(newpointer); //則用指針newpointer作為樹根

return; } elsepointer=root; while(pointer!=NULL){ if(newpointer->value()==pointer->value())//如果存在相等的元素則不用插入

return; elseif(newpointer->value()<pointer->value()){//如果待插入結(jié)點小于pointer的關(guān)鍵碼值if(pointer->leftchild()==NULL){//如果pointer沒有左孩子

12/98

pointer->left=newpointer; //newpointer作為pointer的左子樹

return;

}

elsepointer=pointer->leftchild();//向左下降

} else{//若待插入結(jié)點大于pointer的關(guān)鍵碼值

if(pointer->rightchild()==NULL){//如果pointer沒有右孩子

pointer->right=newpointer; //newpointer作為pointer的右子樹

return; } else pointer=pointer->rightchild();//向右下降

} }}13/98利用插入操作可以構(gòu)造一棵二叉搜索樹首先給出結(jié)點序列:13、8、23、5、18、37Φ

13537

18

8238235518183737二叉搜索樹插入操作14/98二叉搜索樹插入操作(另一個例子)對于關(guān)鍵碼集合K={50，19，35，55，20，5，100，52，88，53，92}二叉搜索樹的生成過程如圖所示：

505195535522010053928815/98對二叉搜索樹的檢索，每一次只需與結(jié)點的一棵子樹相比較在執(zhí)行插入操作時，也不必像在有序線性表中插入元素那樣要移動大量的數(shù)據(jù)，而只需改動某個結(jié)點的空指針插入一個葉結(jié)點即可與查找結(jié)點的操作一樣，插入一個新結(jié)點操作的時間復(fù)雜度是根到插入位置的路徑長度，因此在樹形比較平衡時二叉搜索樹的效率相當高

16/98二叉搜索樹刪除操作情況1葉子結(jié)點：直接刪除，更改它的父親結(jié)點的相應(yīng)指針場為空。如：刪除值為15、70的結(jié)點。15607030205060302050子樹的根結(jié)點：若被刪結(jié)點的左兒子為空或者右兒子為空。如何處理呢？17/98二叉搜索樹刪除操作情況212225030011020099105230400450500子樹的根結(jié)點：若被刪結(jié)點的左兒子為空或者右兒子為空。如刪除結(jié)點的關(guān)鍵值為99結(jié)點。被刪結(jié)點12225030020023040045050011010518/98要刪除的節(jié)點有兩個子節(jié)點合并刪除通過復(fù)制進行刪除二叉搜索樹刪除操作情況319/98合并刪除要刪除的節(jié)點有兩個子節(jié)點——合并刪除rootrootnode->leftnode->rightnodenode->leftnode->right左子樹中最右側(cè)的節(jié)點20/98合并刪除刪除node153020401510302011125401011512在合并刪除后，樹的高度增加21/98合并刪除刪除node15302040151030205402610526在合并刪除后，樹的高度降低22/98復(fù)制刪除要刪除的節(jié)點有兩個子節(jié)點——通過復(fù)制進行刪除選取“替身”取代被刪結(jié)點。如何選擇？左子樹中最大的結(jié)點或右子樹中最小的結(jié)點。23/98復(fù)制刪除12225030011020099105330400450500被刪結(jié)點替身11025030010520099330400450500將替身的數(shù)據(jù)場復(fù)制到被刪結(jié)點的數(shù)據(jù)場。刪除值為122的結(jié)點。24/98復(fù)制刪除

12225030011020099105330400450500被刪結(jié)點替身將替身的數(shù)據(jù)場復(fù)制到被刪結(jié)點的數(shù)據(jù)場。刪除值為122的結(jié)點。

2002503001109910540045050033025/98內(nèi)容提要5.4二叉搜索樹BST12.4.2平衡的二叉搜索樹5.5堆與優(yōu)先隊列5.6哈夫曼樹及其應(yīng)用二叉樹與樹26/98平衡的二叉搜索樹(AVL)

BST受輸入順序影響最好O(logn)

最壞O(n)

怎樣使得BST始終保持O(logn)級的平衡狀態(tài)？Adelson-Velskii和Landis發(fā)明了AVL樹一種平衡的二叉搜索樹任何結(jié)點的左子樹和右子樹高度最多相差127/98AVL樹的性質(zhì)可以為空具有n個結(jié)點的AVL樹，高度為O(logn)

（why？）如果T是一棵AVL樹那么它的左右子樹TL、TR也是AVL樹并且|hL-hR|≤1hL、hR是它的左右子樹的高度

28/98HeightofanAVLTreeProperty:

TheheightofanAVLtreestoringnkeysisO(logn)Proof:

LetusboundN(h):theminimumnumberofinternalnodesofanAVLtreeofheighthN(1)=1

and

N(2)=2Forh>2,anAVLtreeofheighthcontainsatleastarootnode,oneAVLsubtreeofheighth-1,andoneAVLsubtreeofheighth-2,soN(h)=1+N(h-1)+N(h-2)SinceN(h-1)>N(h-2),wehaveN(h)>2N(h-2),andsoN(h)>2N(h-2),N(h)>4N(h-4),

N(h)>8N(h-6),…,etc.N(h)>2iN(h-2i)34N(1)N(2)29/98HeightofanAVLTreeProperty:

TheheightofanAVLtreestoringnkeysisO(logn)Proof:

LetusboundN(h):theminimumnumberofinternalnodesofanAVLtreeofheighthN(1)=1andN(2)=2N(h)>2iN(h-2i)Choosei=h/2-1:

N(h)>2

h/2-1N(h-2(h/2-1))=2

h/2-1N(2)=2

h/2-1

2

h<2logN(h)2logn

So

theheightofanAVLtreeisO(logn)34N(1)N(2)后面有更復(fù)雜的證明（書上的證明）30/98平衡因子平衡因子，用bf(x)來表示結(jié)點x的平衡因子。它被定義為：

bf(x)=x的右子樹的高度

–

x的左子樹的高度對于一個AVL樹中的結(jié)點平衡因子之可能取值為0，1和-1

31/98平衡樹（AVL樹）舉例141253928635360501718730-1-1+1+1+100000000平衡二叉樹：每個結(jié)點的平衡因子都為＋1、－1、0的二叉搜索樹。或者說每個結(jié)點的左右子樹的高度最多差一的二叉搜索樹。145392863536050171830-1-2+1+100000-1+132/98平衡樹（AVL樹）的插入操作

在左圖所示的平衡樹中插入數(shù)據(jù)值為2的結(jié)點。插入之后仍應(yīng)保持平衡分類二叉樹的性質(zhì)不變。141253928635360501718730-1-1+1+1+100000000平衡樹141253928635360501718730-1-1+1+1+1000000002-1-1-2原平衡度為0危機結(jié)點如何用最簡單、最有效的辦法保持平衡二叉樹的性質(zhì)不變？0033/98恢復(fù)平衡插入17后導(dǎo)致不平衡重新調(diào)整為平衡結(jié)構(gòu)110-1803212115017010-180301501701234/98不平衡的情況AVL樹任意結(jié)點A的平衡因子只能是0，1，-1A本來左重，A.bf=＝-1，插入一個結(jié)點導(dǎo)致A.bf變?yōu)?2LL型：插入到A的左子樹的左子樹左重＋左重，A.bf變?yōu)?2

LR型：插入到A的左子樹的右子樹左重＋右重，A.bf變?yōu)?2類似地，A.bf=＝1，插入新結(jié)點使得A.bf變?yōu)?

RR型：導(dǎo)致不平衡的結(jié)點為A的右子樹的右結(jié)點RL型：導(dǎo)致不平衡的結(jié)點為A的右子樹的左結(jié)點Go35/98LL不平衡-2a-1bhhh+1-1a0bhhh圓圈表示節(jié)點；橢圓表示子樹（內(nèi)部符號表示其高度）36/98RR不平衡圓圈表示節(jié)點；橢圓表示子樹（內(nèi)部符號表示其高度）2a1bhhh+11a0bhhh37/98LR不平衡-1a0bhh-1h0ch-1-2a+1bhhh-1ch-1圓圈表示節(jié)點；橢圓表示子樹（內(nèi)部符號表示其高度）38/98RL不平衡+1a0bhh-1h0ch-1+2a-1bhh-1h+1ch圓圈表示節(jié)點；橢圓表示子樹（內(nèi)部符號表示其高度）39/98不平衡情況總結(jié)LL型和RR型是對稱的，LR型和RL型是對稱的

不平衡的結(jié)點一定在根結(jié)點與新加入結(jié)點之間的路徑上

它的平衡因子只能是2或者-2如果是2，它在插入前的平衡因子是1如果是-2，它在插入前的平衡因子是-1

40/98平衡化旋轉(zhuǎn)如果在一棵平衡的二叉搜索樹中插入一個新結(jié)點，造成了不平衡。此時必須調(diào)整樹的結(jié)構(gòu)，使之平衡化。平衡化旋轉(zhuǎn)有兩類：

單旋轉(zhuǎn)(左旋和右旋)

雙旋轉(zhuǎn)(左平衡和右平衡)每插入一個新結(jié)點時，AVL樹中相關(guān)結(jié)點的平衡狀態(tài)會發(fā)生改變。因此，在插入一個新結(jié)點后，需要從插入位置沿通向根的路徑回溯，檢查各結(jié)點的平衡因子(左、右子樹的高度差)。如果在某一結(jié)點發(fā)現(xiàn)高度不平衡，停止回溯。41/98從發(fā)生不平衡的結(jié)點起，沿剛才回溯的路徑取直接下兩層的結(jié)點。如果這三個結(jié)點處于一條直線上(LL或RR)，則采用單旋轉(zhuǎn)進行平衡化。單旋轉(zhuǎn)可按其方向分為左單旋轉(zhuǎn)和右單旋轉(zhuǎn)，其中一個是另一個的鏡像，其方向與不平衡的形狀相關(guān)。如果這三個結(jié)點處于一條折線上(LR或RL)，則采用雙旋轉(zhuǎn)進行平衡化。雙旋轉(zhuǎn)分為先左后右和先右后左兩類。右單旋轉(zhuǎn)左單旋轉(zhuǎn)左右雙旋轉(zhuǎn)右左雙旋轉(zhuǎn)42/98LL單旋轉(zhuǎn)

T3

h

h+1T2

h

-1b

-2aT1如果在子樹T1中插入一個新結(jié)點，該子樹高度增1導(dǎo)致結(jié)點a的平衡因子變成+2，出現(xiàn)不平衡。沿插入路徑檢查三個結(jié)點a、b和c。它們處于一條方向為“/”的直線上，需要做右單旋轉(zhuǎn)。以結(jié)點b為旋轉(zhuǎn)軸，讓結(jié)點a順時針旋轉(zhuǎn)。c43/98LL單旋轉(zhuǎn)

T3

h

T2

h

h+1-2a

-1bT144/98LL單旋轉(zhuǎn)

a

T3

h

T2

h

b-2-100

h+1T1T2

h

45/98雙旋轉(zhuǎn)

RL或者LR需要進行雙旋轉(zhuǎn)這兩種情況是對稱的我們只討論RL的情況LR是一樣的46/98RL型雙旋轉(zhuǎn)第一步T3

h

2aT0

h

-1

b1c或-1T1

h-1/hT2

h/h-1

aRL第一步插入前a子樹高h+2插入后a子樹高h+3需要進行先右后左的雙旋轉(zhuǎn)。先做右單旋轉(zhuǎn),再做左單旋轉(zhuǎn)47/98RL型雙旋轉(zhuǎn)第一步1b2aRL第一步T0

h

1cT1

h-1/hT3

h

T2

h/h-1

插入前a子樹高h+2插入后a子樹高h+348/98RL型雙旋轉(zhuǎn)第一步1b2aRL第一步T0

h

1cT1

h-1/hT3

h

T2

h/h-1

RL第二步中間狀態(tài)平衡因子無意義插入前a子樹高h+2插入后a子樹高h+349/98RL型雙旋轉(zhuǎn)第二步baT0

h

cT1

h-1/hT3

h

T2

h/h-1

RL第二步插入前a子樹高h+2插入后a子樹高h+350/98RL型雙旋轉(zhuǎn)第二步baT0

h

cT1

h-1/hT3

h

T2

h/h-1

T1

h-1/h0

a的平衡因子為-1或0b的平衡因子為0或1RL第二步插入前a子樹高h+2調(diào)整后c子樹高h+251/98旋轉(zhuǎn)運算的實質(zhì)把樹做任何一種旋轉(zhuǎn)（RR、RL、LL、LR）新樹保持了原來的中序周游順序旋轉(zhuǎn)處理中僅需改變少數(shù)指針而且新的子樹高度為h+2，保持插入前子樹的高度不變原來二叉樹在a結(jié)點上面的其余部分（若還有的話）總是保持平衡的

52/98AVL樹的插入在向一棵本來是高度平衡的AVL樹中插入一個新結(jié)點時，如果樹中某個結(jié)點的平衡因子的絕對值|balance|>1，則出現(xiàn)了不平衡，需要做平衡化處理。算法從一棵空樹開始，通過輸入一系列對象的關(guān)鍵碼，逐步建立AVL樹。在插入新結(jié)點時使用了前面所給的算法進行平衡旋轉(zhuǎn)。53/98例，輸入關(guān)鍵碼序列為{16,3,7,11,9,26,18,14,15}，插入和調(diào)整過程如下。160163-10163701-2左右雙旋731600073110-1116右單旋37169000111371126916011273161190-1-2254/98右左雙旋左單旋18160007326119003160917112627390182611-1161183-1-171614026911155/98左右雙旋15231816-20714911261-218730011-116150126149從空樹開始的建樹過程56/98課堂練習假定一組數(shù)據(jù)對象為（40，28，16，56，50，32，30，63），按次序插入每個對象生成一棵AVL樹（高度平衡的二叉搜索樹）。給出插入各結(jié)點后的AVL樹。57/98平衡樹（AVL樹）的刪除操作首先按照二叉查找樹刪除結(jié)點的同樣的方法進行刪除結(jié)點的操作。然后，執(zhí)行刪除替身的操作。該替身為根的子樹的高度將減少1，沿著其父結(jié)點至該結(jié)點的方向進行調(diào)整。隨時調(diào)整相關(guān)結(jié)點的平衡度。一旦發(fā)現(xiàn)在路徑上的祖先結(jié)點的高度不變，那么調(diào)整將結(jié)束。遇到的情況共有以下幾種：141253928635360501718730-1-1+1+1+100000000刪除該結(jié)點58/98平衡樹（AVL樹）的刪除操作具體情況分析：以在左子樹進行刪除為例。

1、結(jié)點平衡度原為0。高度不變，調(diào)整結(jié)束。Ah調(diào)整hh-10Ahhh-1+1

2、結(jié)點平衡度原為－1。高度少1，繼續(xù)調(diào)整。Ah-1調(diào)整hh-1-10Ah-1hh-159/98平衡樹（AVL樹）的刪除操作具體情況分析：以在左子樹進行刪除為例。

3、結(jié)點平衡度原為＋1。有三種情況。

A、右兄弟平衡因子為0。A調(diào)整h-1h-2+1+2Bh-1h-10Bh-1h-2-1Ah-1h-1+160/98平衡樹（AVL樹）的刪除操作具體情況分析：以在左子樹進行刪除為例。

3、結(jié)點平衡度原為＋1。有三種情況。

B、右兄弟平衡因子為＋1A調(diào)整h-1h-2+1+2Bh-1h-2+1Bh-1h-20Ah-2h-1061/98平衡樹（