平衡二叉樹(shù)(Balanced binary tree)是由阿德?tīng)柹?/span>-維爾斯和蘭迪斯(Adelson-Velskii and Landis)于1962年首先提出的，所以又稱為AVL樹(shù)。

定義：平衡二叉樹(shù)或?yàn)榭諛?shù),或?yàn)槿缦滦再|(zhì)的二叉排序樹(shù):

  （1）左右子樹(shù)深度之差的絕對(duì)值不超過(guò)1;

  （2）左右子樹(shù)仍然為平衡二叉樹(shù).

      平衡因子BF=左子樹(shù)深度－右子樹(shù)深度.

平衡二叉樹(shù)每個(gè)結(jié)點(diǎn)的平衡因子只能是1，0，-1。若其絕對(duì)值超過(guò)1，則該二叉排序樹(shù)就是不平衡的。

如圖所示為平衡樹(shù)和非平衡樹(shù)示意圖：

二、平衡二叉樹(shù)算法思想

若向平衡二叉樹(shù)中插入一個(gè)新結(jié)點(diǎn)后破壞了平衡二叉樹(shù)的平衡性。首先要找出插入新結(jié)點(diǎn)后失去平衡的最小子樹(shù)根結(jié)點(diǎn)的指針。然后再調(diào)整這個(gè)子樹(shù)中有關(guān)結(jié)點(diǎn)之間的鏈接關(guān)系，使之成為新的平衡子樹(shù)。當(dāng)失去平衡的最小子樹(shù)被調(diào)整為平衡子樹(shù)后，原有其他所有不平衡子樹(shù)無(wú)需調(diào)整，整個(gè)二叉排序樹(shù)就又成為一棵平衡二叉樹(shù)。

        失去平衡的最小子樹(shù)是指以離插入結(jié)點(diǎn)最近，且平衡因子絕對(duì)值大于1的結(jié)點(diǎn)作為根的子樹(shù)。假設(shè)用A表示失去平衡的最小子樹(shù)的根結(jié)點(diǎn)，則調(diào)整該子樹(shù)的操作可歸納為下列四種情況。

 （1）LL型平衡旋轉(zhuǎn)法

由于在A的左孩子B的左子樹(shù)上插入結(jié)點(diǎn)F，使A的平衡因子由1增至2而失去平衡。故需進(jìn)行一次順時(shí)針旋轉(zhuǎn)操作。 即將A的左孩子B向右上旋轉(zhuǎn)代替A作為根結(jié)點(diǎn)，A向右下旋轉(zhuǎn)成為B的右子樹(shù)的根結(jié)點(diǎn)。而原來(lái)B的右子樹(shù)則變成A的左子樹(shù)。

（2）RR型平衡旋轉(zhuǎn)法

由于在A的右孩子C 的右子樹(shù)上插入結(jié)點(diǎn)F，使A的平衡因子由-1減至-2而失去平衡。故需進(jìn)行一次逆時(shí)針旋轉(zhuǎn)操作。即將A的右孩子C向左上旋轉(zhuǎn)代替A作為根結(jié)點(diǎn)，A向左下旋轉(zhuǎn)成為C的左子樹(shù)的根結(jié)點(diǎn)。而原來(lái)C的左子樹(shù)則變成A的右子樹(shù)。

（3）LR型平衡旋轉(zhuǎn)法

由于在A的左孩子B的右子數(shù)上插入結(jié)點(diǎn)F，使A的平衡因子由1增至2而失去平衡。故需進(jìn)行兩次旋轉(zhuǎn)操作（先逆時(shí)針，后順時(shí)針）。即先將A結(jié)點(diǎn)的左孩子B的右子樹(shù)的根結(jié)點(diǎn)D向左上旋轉(zhuǎn)提升到B結(jié)點(diǎn)的位置，然后再把該D結(jié)點(diǎn)向右上旋轉(zhuǎn)提升到A結(jié)點(diǎn)的位置。即先使之成為LL型，再按LL型處理。

      如圖中所示，即先將圓圈部分先調(diào)整為平衡樹(shù)，然后將其以根結(jié)點(diǎn)接到A的左子樹(shù)上，此時(shí)成為LL型，再按LL型處理成平衡型。

（4）RL型平衡旋轉(zhuǎn)法  

由于在A的右孩子C的左子樹(shù)上插入結(jié)點(diǎn)F，使A的平衡因子由-1減至-2而失去平衡。故需進(jìn)行兩次旋轉(zhuǎn)操作（先順時(shí)針，后逆時(shí)針），即先將A結(jié)點(diǎn)的右孩子C的左子樹(shù)的根結(jié)點(diǎn)D向右上旋轉(zhuǎn)提升到C結(jié)點(diǎn)的位置，然后再把該D結(jié)點(diǎn)向左上旋轉(zhuǎn)提升到A結(jié)點(diǎn)的位置。即先使之成為RR型，再按RR型處理。

 如圖中所示，即先將圓圈部分先調(diào)整為平衡樹(shù)，然后將其以根結(jié)點(diǎn)接到A的左子樹(shù)上，此時(shí)成為RR型，再按RR型處理成平衡型。

平衡化靠的是旋轉(zhuǎn)。參與旋轉(zhuǎn)的是3個(gè)節(jié)點(diǎn)（其中一個(gè)可能是外部節(jié)點(diǎn)NULL），旋轉(zhuǎn)就是把這3個(gè)節(jié)點(diǎn)轉(zhuǎn)個(gè)位置。注意的是，左旋的時(shí)候p->right一定不為空，右旋的時(shí)候p->left一定不為空，這是顯而易見(jiàn)的。

如果從空樹(shù)開(kāi)始建立，并時(shí)刻保持平衡，那么不平衡只會(huì)發(fā)生在插入刪除操作上，而不平衡的標(biāo)志就是出現(xiàn)bf == 2或者 bf == -2的節(jié)點(diǎn)。