1、4.5平衡二叉樹平衡二叉樹 假定二叉搜索樹中每個結(jié)點的查找概率都是相同的，稱查找所有結(jié)點的比較次數(shù)的平均值為樹的“平均查找長度”（ASL)。一、什么是平衡二叉樹例搜索樹結(jié)點不同插入次序，將導致不同的深度和平均查找長度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的計算結(jié)果表明，一棵樹的ASL值越小，它的結(jié)構(gòu)越好，與完全二叉樹越接近，其查找時間復查度也越接近O（logN)。因此，為了保證二叉搜索樹查找的對數(shù)級時間效率，應盡可能創(chuàng)建枝繁葉茂的樹，而避免樹枝過長、過少。 最好的結(jié)構(gòu)是完美二叉樹，從根到葉的各條路徑都是相同的，稱這種樹為完全平衡的。 二、定義“平衡因子（Balance Factor，簡稱BF）: BF(T) = hL-hR，其中hL和hR分別為

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

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

5、ARLL旋轉(zhuǎn)BL0B0ABLBRBLBRBRARcc001000110001Jan0Apr1Aug02May1Mar0NovLR左-右雙旋0Apr1Aug2Mar0Jan1May0NovJan旋轉(zhuǎn)“發(fā)現(xiàn)者”是May，“麻煩結(jié)點”Jan在左子樹的右邊，因而叫 LR 插入，需要LR 旋轉(zhuǎn)LR2LR0B0A插入1BA1旋轉(zhuǎn)0 or 10C1 or 0CARCARBABLCLCRBLCLCRBLCLCRAROROR2.雙旋調(diào)整DDDDD0Apr200110110200011010001DecJulyFeb0Apr1Aug1Dec2Mar0Jan01May0July20NovRL右-左雙旋旋轉(zhuǎn) 1Dec

6、1Aug0Feb2Mar1Jan1May0July0NovFeb一般情況調(diào)整如下:RL2RLA00B插入A11B旋轉(zhuǎn)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注意：有時候插入元素即便不需要調(diào)整結(jié)構(gòu)，也可能需要重新計算一些平衡因子。typedef struct AVLNode *Position;typedef Position AVLTree; /* AVL樹類型 */typedef struct AVLNode ElementType Data; /* 結(jié)點數(shù)據(jù) */ 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中，并且返回調(diào)整后的AVL樹 */if ( !T ) /* 若插入空樹，則新建包含一個結(jié)點的樹 */ T = (AVLTree)malloc(sizeof(struct AVLNode); T-Data = X; T-Height = 0; T-Left = T-Right = NULL; /* if (插入空樹) 結(jié)束 */ 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 (插入左子樹) 結(jié)束 */ 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 (插入右子樹) 結(jié)束 */ /* else X = T-Data，無須插入 */T-Height = Max( GetHeight(T-Left), GetHeight(T-Right) ) + 1; /* 別忘了更新樹高 */return T;AVLTree SingleLeftRotation ( AVLTree A )16. /* 注意：A必須有一個左

11、子結(jié)點B */17. /* 將A與B做左單旋，更新A與B的高度，返回新的根結(jié)點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必須有一個左子結(jié)點B，且B必須有一個右子結(jié)點C */30. /* 將A、B與C做兩次單旋，返回新的根結(jié)點C */31. 32. /* 將B與C做右單旋，C被返回 */33. A-Left = SingleRightRotation(A-Left);34. /* 將A與C做左單旋，C被返回 */35. return SingleLeftRotation(A);36.37. 38./*/39./* 對稱的右單旋與右-左雙旋請自己實現(xiàn) */40./*/41. AVLTree SingleLeftRotation ( AVLTree A ) /* 注意：A必須有一個左子結(jié)點B */

13、/* 將A與B做左單旋，更新A與B的高度，返回新的根結(jié)點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必須有一個左子結(jié)點B，且B必須有一個右子結(jié)點C */ /* 將A、B與C做兩次單旋

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

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

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

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

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