1、4.5平衡二叉樹平衡二叉樹 假定二叉搜索樹中每個結點的查找概率都是相同的，稱查找所有結點的比較次數的平均值為樹的“平均查找長度”（ASL)。一、什么是平衡二叉樹例搜索樹結點不同插入次序，將導致不同的深度和平均查找長度ASLJanAprAprFebMarJuneMayFebJulyMayAugAugJulySeptAugJanMarOctOctDecOctAprDecJuneNovSeptSeptNov(a) 自然月份序列ASL(a)=(1+22+33+43+52+61)/12 = 3.5(b) 按July, Feb, May, Mar,Aug, Jan, Apr, Jun, Oct, Sept

2、,Nov, DecASL(b)=3.0(c)月份字符串月份字符串大小順序ASL(c)= 6.5 樹深在最好的情況下是O（logN),所以，二叉搜索樹在最好情況下的查找復雜度是O（logN)。 上述ASL的計算結果表明，一棵樹的ASL值越小，它的結構越好，與完全二叉樹越接近，其查找時間復查度也越接近O（logN)。因此，為了保證二叉搜索樹查找的對數級時間效率，應盡可能創建枝繁葉茂的樹，而避免樹枝過長、過少。 最好的結構是完美二叉樹，從根到葉的各條路徑都是相同的，稱這種樹為完全平衡的。 二、定義“平衡因子（Balance Factor，簡稱BF）: BF(T) = hL-hR，其中hL和hR分別為

3、T的左、右子樹的高度。 平衡二叉樹（Balanced Binary Tree）（AVL樹）空樹，或者任一結點左、右子樹高度差的絕對值不超過1，即|BF(T) | 1 因此，平衡二叉樹上每個結點的平衡因子只可能是-1、0和1，否則，只要有一個結點的平衡因子的絕對值大于1， 該二叉樹就不是平衡二叉樹。三、平衡二叉樹的調整 一般的二叉排序樹是不平衡的，若能通過某種方法使其既保持有序性，又具有平衡性，就找到了構造平衡二叉排序樹的方法，該方法稱為平衡化旋轉。 在對AVL樹進行插入或刪除一個結點后，通常會影響到從根結點到插入(或刪除)結點的路徑上的某些結點，這些結點的子樹可能發生變化。這時就需要做“平衡化

4、”處理，即相應的局部“旋轉”調整，使得調整后的樹達到平衡。1000MarMayNov2Mar1右單旋 MayMay00Mar0NovNov 不平衡的“發現者”是Mar，“麻煩結點”Nov 在發現者右子樹的右邊，因而叫 RR 插入，需要RR 旋轉（右單旋）AL1A0BRR插入AL2A1BRR旋轉0A0BBRBLBRBLBRALBL1.單旋調整cc1010011AugApr22May0LL旋轉左單旋12May00AugMarNov0AprAug0MarNov0Apr“發現者”是Mar，“麻煩結點”Apr 在發現者左子樹的左邊，因而叫 LL 插入，需要LL 旋轉（左單旋）0B1AARLL插入1B2A

5、ARLL旋轉BL0B0ABLBRBLBRBRARcc001000110001Jan0Apr1Aug02May1Mar0NovLR左-右雙旋0Apr1Aug2Mar0Jan1May0NovJan旋轉“發現者”是May，“麻煩結點”Jan在左子樹的右邊，因而叫 LR 插入，需要LR 旋轉LR2LR0B0A插入1BA1旋轉0 or 10C1 or 0CARCARBABLCLCRBLCLCRBLCLCRAROROR2.雙旋調整DDDDD0Apr200110110200011010001DecJulyFeb0Apr1Aug1Dec2Mar0Jan01May0July20NovRL右-左雙旋旋轉 1Dec

6、1Aug0Feb2Mar1Jan1May0July0NovFeb一般情況調整如下:RL2RLA00B插入A11B旋轉0 or 10C1 or 0ALCALCABCLCRBRCLCRBRALCLCRBRORORDDDDD1 01Jan1 10 01 2110Dec MarMay110100AprApr0 Feb 0 July0112 020 010 2020 11Nov00JuneOctSeptApr June1 1 0Dec Dec MarAugAug Feb JanJulyAug Feb July0 0 011JanMar1 1 0 00 1June2MayNov0MayJune1Nov 0

7、Oct0Oct 0Sept注意：有時候插入元素即便不需要調整結構，也可能需要重新計算一些平衡因子。typedef struct AVLNode *Position;typedef Position AVLTree; /* AVL樹類型 */typedef struct AVLNode ElementType Data; /* 結點數據 */ AVLTree Left; /* 指向左子樹 */ AVLTree Right; /* 指向右子樹 */ int Height; /* 樹高 */四、AVL樹的插入int Max ( int a, int b ) return a b ? a : b;AV

8、LTree Insert( AVLTree T, ElementType X ) /* 將X插入AVL樹T中，并且返回調整后的AVL樹 */if ( !T ) /* 若插入空樹，則新建包含一個結點的樹 */ T = (AVLTree)malloc(sizeof(struct AVLNode); T-Data = X; T-Height = 0; T-Left = T-Right = NULL; /* if (插入空樹) 結束 */ else if ( X Data ) /* 插入T的左子樹 */ T-Left = Insert( T-Left, X); /* 如果需要左旋 */ if ( Ge

9、tHeight(T-Left)-GetHeight(T-Right) = 2 ) if ( X Left-Data ) T = SingleLeftRotation(T); /* 左單旋 */ else T = DoubleLeftRightRotation(T); /* 左-右雙旋 */ /* else if (插入左子樹) 結束 */ else if ( X T-Data ) /* 插入T的右子樹 */ T-Right = Insert( T-Right, X ); /* 如果需要右旋 */ if ( GetHeight(T-Left)-GetHeight(T-Right) = -2 )

10、if ( X T-Right-Data ) T = SingleRightRotation(T); /* 右單旋 */ else T = DoubleRightLeftRotation(T); /* 右-左雙旋 */ /* else if (插入右子樹) 結束 */ /* else X = T-Data，無須插入 */T-Height = Max( GetHeight(T-Left), GetHeight(T-Right) ) + 1; /* 別忘了更新樹高 */return T;AVLTree SingleLeftRotation ( AVLTree A )16. /* 注意：A必須有一個左

11、子結點B */17. /* 將A與B做左單旋，更新A與B的高度，返回新的根結點B */ 18. 19. AVLTree B = A-Left;20. A-Left = B-Right;21. B-Right = A;22. A-Height = Max( GetHeight(A-Left), GetHeight(A-Right) ) + 1;23. B-Height = Max( GetHeight(B-Left), A-Height ) + 1;24. 25. return B;26.27. 28.AVLTree DoubleLeftRightRotation ( AVLTree A )29

12、. /* 注意：A必須有一個左子結點B，且B必須有一個右子結點C */30. /* 將A、B與C做兩次單旋，返回新的根結點C */31. 32. /* 將B與C做右單旋，C被返回 */33. A-Left = SingleRightRotation(A-Left);34. /* 將A與C做左單旋，C被返回 */35. return SingleLeftRotation(A);36.37. 38./*/39./* 對稱的右單旋與右-左雙旋請自己實現 */40./*/41. AVLTree SingleLeftRotation ( AVLTree A ) /* 注意：A必須有一個左子結點B */

13、/* 將A與B做左單旋，更新A與B的高度，返回新的根結點B */ AVLTree B = A-Left; A-Left = B-Right; B-Right = A; A-Height = Max( GetHeight(A-Left), GetHeight(A-Right) ) + 1; B-Height = Max( GetHeight(B-Left), A-Height ) + 1; return B; AVLTree DoubleLeftRightRotation ( AVLTree A ) /* 注意：A必須有一個左子結點B，且B必須有一個右子結點C */ /* 將A、B與C做兩次單旋

14、，返回新的根結點C */A-Left = SingleRightRotation(A-Left); /* 將B與C做右單旋，C被返回 */ return SingleLeftRotation(A);/* 將A與C做左單旋，C被返回 */ 作業：1、在分量111的數組中按從小到大順序存放11個元素，如果用順序查找和二分查找分別查找這11個元素，哪個位置的元素在這兩種方法的查找中總次數最少？.A.1 B.2 C.3 D.62、在分量111的數組中按從小到大順序存放11個元素，如果進行二分查找，查找次數最少的元素位于什么位置？.A.1 B.5 C.6 D.11測驗：1.1.設有如圖設有如圖6-27所

15、示的二叉樹。所示的二叉樹。 分別用順序存儲方法和鏈接存儲方法畫出該二叉樹的存分別用順序存儲方法和鏈接存儲方法畫出該二叉樹的存儲結構。儲結構。 寫出該二叉樹的先序、中序、后序遍歷序列。寫出該二叉樹的先序、中序、后序遍歷序列。2.2.已知一棵二叉樹的先序遍歷序列和中序遍歷序列分別為已知一棵二叉樹的先序遍歷序列和中序遍歷序列分別為ABDGHCEFI和和GDHBAECIF，請畫出這棵二叉樹，然后給出該，請畫出這棵二叉樹，然后給出該樹的后序遍歷序列。樹的后序遍歷序列。圖圖6-27 二叉樹二叉樹adebfgchkmn3、一棵度為 m的樹有n個節點。若每個節點直接用m個鏈指向相應的兒子，則表示這個樹所需要的

16、總空間是n*(m+1) (假定每個鏈以及表示節點的數據域都是一個單位空間).。當采用兒子/兄弟（First Child/Next Sibling）表示法時，所需的總空間是：.A.3n B.2n C.n*m D.n*(m-1)4、如果一個完全二叉樹最底下一層為第六層（根為第一層）且該層共有8個葉結點，那么該完全二叉樹共有多少個結點？.A.31 B.39 C.63 D.715、若有一二叉樹的總結點數為98，只有一個兒子的結點數為48，則該樹的葉結點數是多少？.A.25 B.50 C.不確定 D.這樣的樹不存在6、設深度為d（只有一個根結點時，d為1）的二叉樹只有度為0和2的結點，則此類二叉樹的結點

17、數至少為2d-1.A. B.7、假定只有四個結點A、B、C、D的二叉樹，其前序遍歷序列為ABCD，則下面哪個序列是不可能的中序遍歷序列？.A. ABCD B. ACDB C. DCBA D. DABC8、對于二叉樹，如果其中序遍歷結果與前序遍歷結果一樣，那么可以斷定該二叉樹_.A.是完全二叉樹 B.所有結點都沒有左兒子C.所有結點都沒有右兒子 D.這樣的樹不存在9、已知一二叉樹的后序和中序遍歷的結果分別是FDEBGCA 和FDBEACG,那么該二叉樹的前序遍歷結果是什么？.A. ABDFECG B. ABDEFCG C. ABDFEGC D. ABCDEFG10、假定只有四個結點A、B、C、D

18、的二叉樹，其前序遍歷序列為ABCD，則下面哪個序列是不可能的中序遍歷序列？.A. ABCD B. ACDB C. DCBA D. DABC11、對于二叉樹，如果其中序遍歷結果與前序遍歷結果一樣，那么可以斷定該二叉樹_.A.是完全二叉樹 B.所有結點都沒有左兒子C.所有結點都沒有右兒子 D.這樣的樹不存在12、已知一二叉樹的后序和中序遍歷的結果分別是FDEBGCA 和FDBEACG,那么該二叉樹的前序遍歷結果是什么？.A. ABDFECG B. ABDEFCG C. ABDFEGC D.ABCDEFG13、非遞歸方法中序遍歷下面這顆二叉樹，其堆棧操作序列（P代表為push,O代表為pop)是什么？.A.PPOOPOPPOOB.PPPPPOOOOOC.PPOOOPPOOD.PPOPOOPPOO14、已知有顆5個結點的二叉樹，其前序遍歷序列是a?，中序遍歷序列是a?，可以斷定：.A.該樹根結點是a，且沒有左子樹 B.該樹根結點是a，且沒有右子樹C.該樹最左邊的結點