DS06-樹b-陳越主編-數據結構

第4章樹§4.4二叉搜索樹【定義】一個二叉搜索樹是一棵二叉樹，它可以為空。如果不為空，它將滿足以下性質：非空左子樹的所有鍵值小于其根結點的鍵值。非空右子樹的所有鍵值大于其根結點的鍵值。左、右子樹都是二叉搜索樹。

二叉搜索樹“二叉搜索樹〔BST，BinarySearchTree〕”也稱二叉排序樹或二叉查找樹，它是一種對排序和查找都很有用的特殊二叉樹。18105207223015413350631479510211811個元素二分查找的判定樹1

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

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

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

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

BinTreeInsert(ElementTypeX,BinTreeBST)

BinTreeDelete(ElementTypeX,BinTreeBST)2

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

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

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

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

while(BST){

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

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

else

/*X==BST->Data*/

returnBST;/*查找成功，返回找到的結點的地址*/}

returnNULL;/*查找失敗*/}

由于非遞歸函數的執(zhí)行效率高，一般采用非遞歸的迭代來實現查找。

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

查找最大和最小元素第4章樹

最大元素一定是在樹的最右分枝的端結點上

最小元素一定是在樹的最左分枝的端結點上181015207229最左端點最右端點§4.4二叉搜索樹5第4章樹

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

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

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

returnBST;}PositionFindMin(BinTreeBST){

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

else

if(!BST->Left)

returnBST;/*找到最左葉結點并返回*/

else

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

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

二叉搜索樹的刪除第4章樹§4.4二叉搜索樹

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

要刪除的是葉結點——可以直接刪除，然后再修改其父結點的指針。圖4.28二叉搜索樹葉結點的刪除301541335035要刪除結點〖例〗：刪除3510第4章樹§4.4二叉搜索樹圖4.29具有一個子樹的結點刪除

要刪除的結點只有一個孩子結點——刪除之前需要改變其父結點的指針，指向要刪除結點的孩子結點。要刪除結點（只有一個孩子）3015415035333015415035〖例〗：刪除3311第4章樹§4.4二叉搜索樹圖4.30具有兩個子樹的結點刪除

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

if(!BST)printf("要刪除的元素未找到");

else

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

else

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

else

/*找到要刪除的結點*/

if(BST->Left&&BST->Right){/*被刪除結點有左右兩個子結點*/Tmp=FindMin(BST->Right);

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

/*在刪除結點的右子樹中刪除最小元素*/}else{/*被刪除結點有一個或無子結點*/Tmp=BST;

if(!BST->Left)/*有右孩子或無子結點*/BST=BST->Right;

else

if(!BST->Right)/*有左孩子或無子結點*/BST=BST->Left;free(Tmp);}

returnBST;}13第4章樹§4.5平衡二叉樹

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

按ASL的定義，可以分別計算出三棵二叉搜索樹的平均查找長度：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；查找二叉搜索樹〔BST〕的時間復雜度〔最壞情況下〕用查找過程中的比較次數來衡量，它取決于樹的深度。14

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

1MayMay0NovNov0

1

2May0

1Nov00

2

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

平衡二叉樹的調整第4章樹§4.5AVL樹16AugMay0

1Nov00

2

1Mar011Aug0AprApr0122LL旋轉左單旋May0

1Nov00

2

1Aug011

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

1Nov00

2

1Aug011

1Mar00Apr0JanJan01

12LR旋轉Mar0

1May0

1

2

1Aug010

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

1BLARC1CRCLORLR旋轉BLARC0A

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

1May0

1

2

1Aug011

1Jan0Apr0Nov0July0Dec0FebFeb0

11

22RL旋轉July0Dec0

1Aug01

2

1Jan010

1Feb00Apr0Mar0

1May0

1

2

11Nov0

一般情況調整如下:A1B0BRALC0CLCRRL插入A2B1BRALC1CLCRORRL旋轉BRALC0A0or1CLB

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

1Aug01

2

1Jan010

1Feb00Apr0Mar0

1May0

1

2

11Nov0JuneOctSeptJune0

1

1

12Nov0Dec0

1Aug1

2

1Feb01July1Apr0Mar0May1June0Jan0Oct01211Oct0Dec0

1Aug1

2

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

其中

h

是二叉樹的高度，但是，

h=?設

nh

為高度為h的平衡二叉樹的最小結點數.二