將二叉樹節(jié)點的左子樹的深度減去它的右子樹的深度稱為平衡因子BF，則平衡二叉樹上所有節(jié)點的平衡因子只可能是-1、0和1，如下圖左邊的為平衡二叉樹，右邊的為非平衡二叉樹。
因為平衡二叉樹上任何節(jié)點的左、右子樹的深度之差都不會超過1，可以證明它的深度和n個節(jié)點的完全二叉樹的深度?log2n?\\\\lfloor log_2n \\\\rfloor?log2n? 1是同數(shù)量級的。因此，它的平均查找次數(shù)也是和?log2n?\\\\lfloor log_2n \\\\rfloor?log2n? 1同數(shù)量級的。
要構(gòu)造一棵平衡二叉樹，Georgii M. Adelson-Velskii 和 Evgenii M. Landis 提出了一種動態(tài)保持二叉平衡樹的方法，其基本思想是：在構(gòu)造二叉排序樹的時候，每當插入一個節(jié)點時，先檢查是否因插入節(jié)點而破壞了樹的平衡性，如果是，則找出其中最小不平衡子樹，在保持排序樹的前提下，調(diào)整最小不平衡子樹中各節(jié)點之間的連接關(guān)系，以達到新的平衡，所以這樣的平衡二叉樹簡稱AVL樹。其中最小平衡子樹是指：離插入節(jié)點最近，且平衡因子絕對值大于1的節(jié)點作為根節(jié)點的子樹。
調(diào)整最小不平衡子樹一般有四種情況：單向右旋(LL型)： 插入位置為左子樹的左子樹，以左子樹為軸心，進行單次向右旋轉(zhuǎn)，如下圖所示。節(jié)點旁邊的數(shù)字為該節(jié)點的平衡因子，I節(jié)點為當前插入節(jié)點(如果I節(jié)點處于正中，則表示I節(jié)點既可以是左孩子也可以是右孩子。
注意LL型，以中間節(jié)點為軸心進行旋轉(zhuǎn)。為什么這里I為BL左孩子不能將B-BL-I作為LL型，是因為A節(jié)點才是離I節(jié)點最近的平衡因子絕對值>1的子樹，其余節(jié)點的平衡因子絕對值都沒有超過1；同理當I為BL右孩子，也不能將B-BL-I作為LR型。
2. 單向左旋(RR型)： 插入位置為右子樹的右子樹，右子樹為軸心，進行單次向左旋轉(zhuǎn)
注意RR型，以中間節(jié)點為軸心進行旋轉(zhuǎn)。這里I為左右子樹并不影響其實RR型，原理同上。
3. 雙向旋轉(zhuǎn)先左后右(LR型)：插入位置為左子樹的右子樹，要進行兩次旋轉(zhuǎn)，先向左旋轉(zhuǎn)，再向右旋轉(zhuǎn)。
插入節(jié)點為左孩子：注意為什么不能B-C-I作為子樹將其定為RL型，原理同RR型中的解釋，對于LR型，，是以R端或者L靠近插入節(jié)點端作為旋轉(zhuǎn)軸心（如下圖相當于先旋轉(zhuǎn)以B為根的子樹后，成為了LL型，再旋轉(zhuǎn)以A為根的子樹）。
插入節(jié)點為右孩子：
4. 雙向旋轉(zhuǎn)先右后左(RL型)：插入位置為右子樹的左子樹，進行兩次調(diào)整，先右旋轉(zhuǎn)再左旋轉(zhuǎn)；處理情況與LR類似。
插入節(jié)點為左孩子：
插入節(jié)點為右孩子：
經(jīng)過上面的我們可以發(fā)現(xiàn)，平衡因子與類型有很大的關(guān)系，需要以離插入節(jié)點最近且平衡因子絕對值>1的節(jié)點作為根節(jié)點的子樹進行判定是哪種類型。
練習
如下圖所示，先插入節(jié)點2后，成為LL型，然后整體右旋處理后平衡。
再依次插入8和6之后，節(jié)點5的平衡因子絕對值>1，成為RL型，所以先以5為根節(jié)點，將其子樹8-6右旋（成為RR型），然后將5為根節(jié)點的整棵樹再左旋。
繼續(xù)插入節(jié)點9后，節(jié)點4的平衡因子>1，成為RR型，所以以4為根節(jié)點，將整體左旋。
更多關(guān)于云服務(wù)器，域名注冊，虛擬主機的問題，請訪問西部數(shù)碼官網(wǎng)：m.ps-sw.cn
