DS06-樹(shù)b-陳越主編-數(shù)據(jù)結(jié)構(gòu)

第4章樹(shù)§4.4二叉搜索樹(shù)【定義】一個(gè)二叉搜索樹(shù)是一棵二叉樹(shù)，它可以為空。如果不為空，它將滿(mǎn)足以下性質(zhì)：非空左子樹(shù)的所有鍵值小于其根結(jié)點(diǎn)的鍵值。非空右子樹(shù)的所有鍵值大于其根結(jié)點(diǎn)的鍵值。左、右子樹(shù)都是二叉搜索樹(shù)。

二叉搜索樹(shù)“二叉搜索樹(shù)〔BST，BinarySearchTree〕”也稱(chēng)二叉排序樹(shù)或二叉查找樹(shù)，它是一種對(duì)排序和查找都很有用的特殊二叉樹(shù)。18105207223015413350631479510211811個(gè)元素二分查找的判定樹(shù)1

二叉搜索樹(shù)的動(dòng)態(tài)查找二叉搜索樹(shù)作為抽象數(shù)據(jù)結(jié)構(gòu)的定義與普通二叉樹(shù)相同，但操作集中多了以下幾個(gè)特別的函數(shù)：

PositionFind(ElementTypeX,BinTreeBST)：從二叉搜索樹(shù)BST中查找元素X，返回其所在結(jié)點(diǎn)的地址

PositionFindMin(BinTreeBST)：從二叉搜索樹(shù)BST中查找并返回最小元素所在結(jié)點(diǎn)的地址

PositionFindMax(BinTreeBST)：從二叉搜索樹(shù)BST中查找并返回最大元素所在結(jié)點(diǎn)的地址第4章樹(shù)§4.4二叉搜索樹(shù)

BinTreeInsert(ElementTypeX,BinTreeBST)

BinTreeDelete(ElementTypeX,BinTreeBST)2

二叉搜索樹(shù)的查找操作Find第4章樹(shù)§4.4二叉搜索樹(shù)查找從根結(jié)點(diǎn)開(kāi)始，如果樹(shù)為空，返回NULL，表示未找到關(guān)鍵字為X的結(jié)點(diǎn)。假設(shè)搜索樹(shù)非空，那么根結(jié)點(diǎn)關(guān)鍵字和X進(jìn)行比較，依據(jù)比較結(jié)果，需要進(jìn)行不同的處理：假設(shè)根結(jié)點(diǎn)鍵值小于X，滿(mǎn)足條件的結(jié)點(diǎn)將不會(huì)出現(xiàn)在它的左子樹(shù)，接下來(lái)的搜索只需在右子樹(shù)中進(jìn)行；如果根結(jié)點(diǎn)的鍵值大于X，接下來(lái)的搜索將在左子樹(shù)中進(jìn)行；假設(shè)兩者比較結(jié)果是相等，搜索完成，返回指向此結(jié)點(diǎn)的指針。PositionFind(ElementTypeX,BinTreeBST){if(!BST)returnNULL;/*查找失敗*/if(X>BST->Data)

returnFind(X,BST->Right);/*在右子樹(shù)中繼續(xù)查找*/Elseif(X<BST->Data)

returnFind(X,BST->Left);/*在左子樹(shù)中繼續(xù)查找*/else

/*X==BST->Data*/returnBST;/*查找成功，返回找到的結(jié)點(diǎn)的地址*/}是否應(yīng)領(lǐng)先考察空樹(shù)？都是“尾遞歸”3PositionIterFind(ElementTypeX,BinTreeBST){

while(BST){

if(X>BST->Data) BST=BST->Right;/*向右子樹(shù)中移動(dòng)，繼續(xù)查找*/

elseif(X<BST->Data) BST=BST->Left;/*向左子樹(shù)中移動(dòng)，繼續(xù)查找*/

else

/*X==BST->Data*/

returnBST;/*查找成功，返回找到的結(jié)點(diǎn)的地址*/}

returnNULL;/*查找失敗*/}

由于非遞歸函數(shù)的執(zhí)行效率高，一般采用非遞歸的迭代來(lái)實(shí)現(xiàn)查找。

很容易將“尾遞歸”函數(shù)改為迭代函數(shù)第4章樹(shù)§4.4二叉搜索樹(shù)4

查找最大和最小元素第4章樹(shù)

最大元素一定是在樹(shù)的最右分枝的端結(jié)點(diǎn)上

最小元素一定是在樹(shù)的最左分枝的端結(jié)點(diǎn)上181015207229最左端點(diǎn)最右端點(diǎn)§4.4二叉搜索樹(shù)5第4章樹(shù)

§4.4二叉搜索樹(shù)PositionFindMax(BinTreeBST){

if(!BST)while(BST->Right)BST=BST->Right;

/*沿右分支繼續(xù)查找，直到最右葉結(jié)點(diǎn)*/

returnBST;}PositionFindMin(BinTreeBST){

if(!BST)returnNULL;/*空的二叉搜索樹(shù)，返回NULL*/

else

if(!BST->Left)

returnBST;/*找到最左葉結(jié)點(diǎn)并返回*/

else

returnFindMin(BST->Left);/*沿左分支繼續(xù)查找*/}代碼4.16查找最小元素的遞歸函數(shù)代碼4.17查找最大元素的迭代函數(shù)6

二叉搜索樹(shù)的插入第4章樹(shù)§4.4二叉搜索樹(shù)〖分析〗將元素X插入二叉搜索樹(shù)BST中，關(guān)鍵是要找到元素應(yīng)該插入的位置。位置確實(shí)定可以利用與查找函數(shù)Find類(lèi)似的方法，如果在樹(shù)BST中找到X，說(shuō)明要插入的元素已存在，可放棄插入操作。如果沒(méi)找到X，查找終止的位置就是X應(yīng)插入的位置。3015413350353015413350357BinTreeInsert(ElementTypeX,BinTreeBST){if(!BST){/*假設(shè)原樹(shù)為空，生成并返回一個(gè)結(jié)點(diǎn)的二叉搜索樹(shù)*/BST=malloc(sizeof(structTreeNode));BST->Data=X;BST->Left=BST->Right=NULL;}else/*開(kāi)始找要插入元素的位置*/if(X<BST->Data)BST->Left=Insert(X,BST->Left);/*遞歸插入左子樹(shù)*/elseif(X>BST->Data)BST->Right=Insert(X,BST->Right);/*遞歸插入右子樹(shù)*//*elseX已經(jīng)存在，什么都不做*/returnBST;}第4章樹(shù)§4.4二叉搜索樹(shù)代碼4.18二叉搜索樹(shù)的插入算法8【例4.8】以一年十二個(gè)月的英文縮寫(xiě)為鍵值，按從一月到十二月順序輸入它們，即輸入序列為〔Jan,Feb,Mar,Apr,May,Jun,July,Aug,Sep,Oct,Nov,Dec〕，將產(chǎn)生什么樣的二叉搜索樹(shù)？第4章樹(shù)§4.4二叉搜索樹(shù)JanFebAprMarJunMayDecOctSeptJulyAugNov9

二叉搜索樹(shù)的刪除第4章樹(shù)§4.4二叉搜索樹(shù)

二叉搜索樹(shù)的刪除操作比其它操作更為復(fù)雜，有三種情況需要考慮：

要?jiǎng)h除的是葉結(jié)點(diǎn)——可以直接刪除，然后再修改其父結(jié)點(diǎn)的指針。圖4.28二叉搜索樹(shù)葉結(jié)點(diǎn)的刪除301541335035要?jiǎng)h除結(jié)點(diǎn)〖例〗：刪除3510第4章樹(shù)§4.4二叉搜索樹(shù)圖4.29具有一個(gè)子樹(shù)的結(jié)點(diǎn)刪除

要?jiǎng)h除的結(jié)點(diǎn)只有一個(gè)孩子結(jié)點(diǎn)——?jiǎng)h除之前需要改變其父結(jié)點(diǎn)的指針，指向要?jiǎng)h除結(jié)點(diǎn)的孩子結(jié)點(diǎn)。要?jiǎng)h除結(jié)點(diǎn)（只有一個(gè)孩子）3015415035333015415035〖例〗：刪除3311第4章樹(shù)§4.4二叉搜索樹(shù)圖4.30具有兩個(gè)子樹(shù)的結(jié)點(diǎn)刪除

要?jiǎng)h除的結(jié)點(diǎn)有左、右兩棵子樹(shù)——為了保持二叉搜索樹(shù)的有序性，替代被刪除的元素的位置可以有兩種選擇：一種是取其右子樹(shù)中的最小元素；另一個(gè)是取其左子樹(shù)中的最大元素。41503015333534〖例〗：刪除41(a)取右子樹(shù)中的最小元素替代41353450301533(b)取左子樹(shù)中的最大元素替代12BinTreeDelete(ElementTypeX,BinTreeBST){PositionTmp;

if(!BST)printf("要?jiǎng)h除的元素未找到");

else

if(X<BST->Data)BST->Left=Delete(X,BST->Left);/*左子樹(shù)遞歸刪除*/

else

if(X>BST->Data)BST->Right=Delete(X,BST->Right);/*右子樹(shù)遞歸刪除*/

else

/*找到要?jiǎng)h除的結(jié)點(diǎn)*/

if(BST->Left&&BST->Right){/*被刪除結(jié)點(diǎn)有左右兩個(gè)子結(jié)點(diǎn)*/Tmp=FindMin(BST->Right);

/*在右子樹(shù)中找最小的元素填充刪除結(jié)點(diǎn)*/BST->Data=Tmp->Data;BST->Right=Delete(BST->Data,BST->Right);

/*在刪除結(jié)點(diǎn)的右子樹(shù)中刪除最小元素*/}else{/*被刪除結(jié)點(diǎn)有一個(gè)或無(wú)子結(jié)點(diǎn)*/Tmp=BST;

if(!BST->Left)/*有右孩子或無(wú)子結(jié)點(diǎn)*/BST=BST->Right;

else

if(!BST->Right)/*有左孩子或無(wú)子結(jié)點(diǎn)*/BST=BST->Left;free(Tmp);}

returnBST;}13第4章樹(shù)§4.5平衡二叉樹(shù)

平衡二叉樹(shù)〖例〗不同的插入次序，將導(dǎo)致不同的深度和平均查找長(zhǎng)度ASL。(a)按一月到十二月的自然月份序列輸入所生成的；(b)輸入序列為〔July,Feb,May,Mar,Aug,Jan,Apr,Jun,Oct,Sept,Nov,Dec〕(c)輸入序列那么是按月份字符串從小到大的順序排列的。JanFebMarAprAugDecJuneJulyMaySeptOctNovJanFebMarAprAugDecJuneJulyMaySeptOctNovAprAugOctSept

按ASL的定義，可以分別計(jì)算出三棵二叉搜索樹(shù)的平均查找長(zhǎng)度：ASL(a)=(1+2×2+3×3+4×3+5×2+6×1)/12=3.5；ASL(b)=(1+2×2+3×4+4×5)/12=3.0；ASL(c)=(1+2×1+3×1+4×1+5×1+6×1+7×1+8×1+9×1+10×1+11×1+12×1)/12=6.5；查找二叉搜索樹(shù)〔BST〕的時(shí)間復(fù)雜度〔最壞情況下〕用查找過(guò)程中的比較次數(shù)來(lái)衡量，它取決于樹(shù)的深度。14

平衡二叉樹(shù)的定義第4章樹(shù)§4.5平衡二叉樹(shù)【定義】對(duì)于二叉樹(shù)中任一結(jié)點(diǎn)T，其“平衡因子〔BalanceFactor，簡(jiǎn)稱(chēng)BF〕”定義為BF(T)=hL-hR，其中hL和hR分別為T(mén)的左、右子樹(shù)的高度?！捌胶舛鏄?shù)〔BalancedBinaryTree〕”又稱(chēng)為“AVL樹(shù)”。AVL樹(shù)或者是一棵空樹(shù)，或者是具有以下性質(zhì)的非空二叉搜索樹(shù)：“任一結(jié)點(diǎn)左、右子樹(shù)高度差的絕對(duì)值不超過(guò)1?！奔磡BF(T)|≤1。64581927258164456321715MarMar0

1MayMay0NovNov0

1

2May0

1Nov00

2

1Mar000首個(gè)不平衡的“發(fā)現(xiàn)者”是Mar〔未必是根結(jié)點(diǎn)〕，它是調(diào)整起點(diǎn)位置。而“麻煩結(jié)點(diǎn)”Nov在發(fā)現(xiàn)者右子樹(shù)的右邊，因而叫RR插入，需要RR旋轉(zhuǎn)〔右單旋〕；一般情況〔設(shè)A是首個(gè)發(fā)現(xiàn)者〕的調(diào)整方式如下:A1B0BLBRALRR插入RR旋轉(zhuǎn)A2B1BLBRALBLB0AALBR0右單旋

平衡二叉樹(shù)的調(diào)整第4章樹(shù)§4.5AVL樹(shù)16AugMay0

1Nov00

2

1Mar011Aug0AprApr0122LL旋轉(zhuǎn)左單旋May0

1Nov00

2

1Aug011

1Mar00Apr0首個(gè)“發(fā)現(xiàn)者”是Mar；“麻煩結(jié)點(diǎn)”Apr在發(fā)現(xiàn)者左子樹(shù)的左邊，因而叫LL插入；一般情況〔設(shè)A是首個(gè)發(fā)現(xiàn)者〕的調(diào)整方式如下:A1B0BRBLARLL插入A2B1BRBLARLL旋轉(zhuǎn)B0AARBLBR0第4章樹(shù)§4.5AVL樹(shù)17May0

1Nov00

2

1Aug011

1Mar00Apr0JanJan01

12LR旋轉(zhuǎn)Mar0

1May0

1

2

1Aug010

1Jan00Apr0Nov0首個(gè)“發(fā)現(xiàn)者”是May；“麻煩結(jié)點(diǎn)”Jan在左子樹(shù)的右邊，因而叫LR插入；一般情況〔設(shè)A是首個(gè)發(fā)現(xiàn)者〕的調(diào)整如下:A1B0BLARC0CRCLLR插入A2B

1BLARC1CRCLORLR旋轉(zhuǎn)BLARC0A

1or0CRB0or1CLOR左-右雙旋第4章樹(shù)§4.5AVL樹(shù)18DecJulyMar0

1May0

1

2

1Aug011

1Jan0Apr0Nov0July0Dec0FebFeb0

11

22RL旋轉(zhuǎn)July0Dec0

1Aug01

2

1Jan010

1Feb00Apr0Mar0

1May0

1

2

11Nov0

一般情況調(diào)整如下:A1B0BRALC0CLCRRL插入A2B1BRALC1CLCRORRL旋轉(zhuǎn)BRALC0A0or1CLB

1or0CROR第4章樹(shù)§4.5AVL樹(shù)右-左雙旋19July0Dec0

1Aug01

2

1Jan010

1Feb00Apr0Mar0

1May0

1

2

11Nov0JuneOctSeptJune0

1

1

12Nov0Dec0

1Aug1

2

1Feb01July1Apr0Mar0May1June0Jan0Oct01211Oct0Dec0

1Aug1

2

1Feb01July1Apr0Mar0Nov0June0Jan0May0Sept01111注意：有時(shí)候插入元素即便不需要調(diào)整結(jié)構(gòu)，也可能需要重新計(jì)算一些平衡因子。第4章樹(shù)§4.5AVL樹(shù)LL、RR、LR、RL四種不平衡情況及其它們的旋轉(zhuǎn)調(diào)整算法程序，見(jiàn)教材p.131代碼4.20—代碼4.2220最后一個(gè)問(wèn)題:查找和插入的時(shí)間復(fù)雜性Tp=O(h)

其中

h

是二叉樹(shù)的高度，但是，

h=?設(shè)

nh

為高度為h的平衡二叉樹(shù)的最小結(jié)點(diǎn)數(shù).二