平衡樹，又稱AVL樹。（以前蘇聯學者Adelson-Velskii和Landis的名字命名）
定義：所有結點的平衡因子絕對值≤1的二叉樹（高度h控制在結點數n的對數範圍之内 h≤O(logn)的樹都屬于平衡樹（balanced tree））。
平衡因子：右子樹的高hR與v的左子樹高hL之差hR-hL 。
AVL樹各點的平衡因子：隻能是0、1、-1。
性質：高度h≤1.45log2n （n是結點數）
換句話說，以某一點為根結點，再以其右子樹的高度減去其左子樹的高度。其值隻能是0，-1,1。
比如：
最頂端是根結點，其右邊高度減左邊高度，是以其根結點的平衡因子為0。
一、插入引起的旋轉
（1）插入操作的大體步驟
步驟1） 像一般的檢索樹那樣插入x（新葉）
步驟2）沿插入x的路線傳回，修改x祖先的平衡因子
步驟3） 回溯中，一旦發現x的祖先p失衡
由p->bal=1 變成 p->bal=2
由p->bal=-1 變成 p->bal=-2
旋轉以p為根的子樹，使之平衡
（2）平衡因子變化情況分析
x插在p的左子樹上，且使p的左子樹高度增1
當傳回路線沿左路到達p時 ，插入前 ：
p->bal=0（hR=hL=h）
p->bal=1（hR=h，hL=h-1 ）
p->bal=-1（hR=h，hL=h+1 ）
（3）旋轉方法
前提(左子樹) ：p->bal=-1 變為 p->bal=-2
1. LL單旋：p的左兒子作根
2. LR雙旋：p的孫子作根
前提(右子樹) ：p->bal=+1 變為 p->bal=+2
1.RR單旋：p的右兒子作根
2.RL雙旋：p的孫子作根
LL單旋
具體情況及方法：
情況：x插在p的左兒子p1的左子樹上，使p1的左子樹升高，繼而引起p1點升高
插入x前，p1->bal=0；
插入x 使p1的左子樹升高，p1->bal變為-1
現沿左路到達p1，又沿左路到達p。
旋轉方法：
(1)使p1作為子樹之根
(2) p作p1的右兒子；p1的右兒子作p的左兒子
旋轉後：p子樹高度沒有增加，停止回溯
LR雙旋
情況：x插在p的左兒子p1的右子樹上，使p1的右子樹升高，繼而引起p1點升高
插入x 使p1的右子樹升高，p1->bal變為1
現沿右路到達p1，又沿左路到達p
(1)p2作為子樹之根
(2)p1和p分别作p2的左右兒子
(3)p2的原左右兒子分别作p1的右兒子和p的左兒子
結論：
1.插入一個結點，至多旋轉一次
2.從右路傳回到p的處理完全對稱（旋轉：RR單旋、RL雙旋）
3.“左”都換成“右”，“右”都換成“左”
4.正号都換成負号，負号都換成正号
RR單旋
(2) p作p1的左兒子；p1的右兒子作p的左兒子
RL雙旋
(2)p和p1分别作p2的左右兒子
構造AVL樹執行個體
步驟：
1.按照構造有序二叉樹的方法（左小右大），構造有序二叉樹。
2.按照上述方法，使用哪種旋轉方法。可能要使用多種的結合，不局限于一種。
二、删除引起旋轉
（1）删除結點x的大體步驟:
步驟1）用一般檢索樹的删除算法找到并删除結點x，x有兩個兒子時，被删除的是x的中序前趨。
步驟2）沿根到被删除結點的路線之逆逐層向上回溯，檢查該路線上各結點的平衡因子是否變化，如果變化，則及時修改。
步驟3）若發現某結點p的平衡因子，由p->bal=1變成p->bal=2，或由p->bal=-1變成p->bal=-2（失衡），則旋轉以p為根的子樹結構，恢複平衡。
如果旋轉後子樹高度還降低，要繼續回溯。
在p的左子樹上删除，使p的左子樹高度降1。
删除前p的平衡因子（分三種情況）
p->bal=-1
p->bal=0
p->bal=+1
總結：
1．p->bal=-1
p->bal變為0，樹高降低，回溯
2．p->bal=0
p->bal變為-1，樹高不變，平衡
3．p->bal=+1
p->bal變為+2，旋轉
情況：在p的左子樹上删除，使p的左子樹高度降1
删除前，p->bal=+1；
删除後，p->bal變為+2
考慮：p的右兒子p1的平衡因子。
p1->bal=0
p1->bal=+1
p1->bal=-1
旋轉方法（結論）：
情況：在p的左子樹上删除使p的左子樹高度降1
删除前，p->bal=+1
删除後，p->bal變為+2
考慮：p的右兒子p1的平衡因子
p1->bal=0 RR單旋 平衡
p1->bal=+1 RR單旋 樹高降低
p1->bal=-1 RL雙旋 樹高降低
旋轉後：子樹高度如果降低，繼續回溯
删除示例：
删除示例2