-
1.平衡二叉樹
結點的平衡因子：該結點的右子樹高度減去左子樹高度蜜另。
如果結點的平衡因子為-1（左偏重）、0或者1（有偏重）糠亩，那么這個結點是平衡的舌狗。
-
2.重新平衡樹
AVL樹中插入或刪除操作與普通二叉查找樹相同，不同的是必須在插入或者刪除操作之后進行重新平衡俱两。
1). 左子樹過高
a) LL型
在LL型的不平衡樹中饱狂，我們首先找到最小不平衡子樹，再以其根結點向右旋轉锋华。為何是向右旋轉呢嗡官？應該不難理解，向右旋轉后毯焕，相當于右邊的子樹樹高增加了1衍腥，而左邊的子樹樹高降低了1，而原本的樹高之差為2,那么就能夠將根的平衡因子就化為0纳猫。旋轉之后為“原來根結點的左孩子作為新的根結點”婆咸。
我們對樹以根結點為中心，向右旋轉芜辕。旋轉步驟如下：
i. 將2作為根結點
ii. 將3作為2的右孩子
iii. 將2的右孩子作為3的左孩子（維護樹的有序性尚骄，只是此處為NULL而已）
b) LR型
對于LR，要分為兩步進行旋侵续。旋轉之后為“原來根結點的左孩子的右孩子作為新的根結點”倔丈。
第一：（轉換成LL型）
以較高子樹的根憨闰，即1，為中心向左旋轉需五。具體步驟如下鹉动。
i. 將2的左子樹作為1的右子樹（維護樹的有序性，只是此處為NULL而已）
ii. 將1作為2的左子樹
iii. 將2作為3的左子樹
第二：和LL型處理方式相同
以原樹的根宏邮，即3為中心泽示，向右旋轉。最后結果如下
2). 右子樹過高
a) RR型
還是引用一下之前的例子蜜氨。旋轉的步驟如下械筛。旋轉之后為“原來根結點的右孩子作為新的根結點”。
i. 將2作為根結點
ii. 將1作為2的左孩子
iii. 將2的左孩子作為1的右孩子（維護樹的有序性飒炎，只是此處為NULL而已）
b)RL型
與LR型類似埋哟，我們需要進行兩次旋轉。旋轉之后為“原來根結點的右孩子的左孩子作為新的根結點”厌丑。
第一定欧，轉換成RR型
以根結點的右孩子即3為中心向右旋轉，結果如下怒竿。具體步驟如下
i. 將2作為1的右孩子
ii. 將3作為2的右孩子
iii. 將2的右孩子作為3的左孩子（維護樹的有序性砍鸠，只是此處為NULL而已）
第二，與RR型處理方式相同
以原根結點即1耕驰，作為中心爷辱，向左旋轉。結果如下朦肘。具體步驟如下
i. 將2作為根結點
ii. 將1作為2的左孩子
iii. 將2的左孩子作為1的右孩子（維護樹的有序性饭弓，只是此處為NULL而已）
3.設計平衡二叉樹
4.AVL樹時間復雜度分析
