平衡二叉樹（AVL）
一、 平衡二叉樹
在二叉查找樹T中，若所有結點的平衡因子的絕對值均不超過1，則稱T為一棵AVL樹。
平衡二叉樹又稱AVL樹，它是具有如下性質的二叉樹：
• 左、右子樹是平衡二叉樹；
• 所有結點的左、右子樹深度之差的絕對值≤ 1
為了友善起見，給每個結點附加一個數字，給出該結點左子樹與右子樹的高度差。這個數字稱為結點的平衡因子balance。這樣，可以得到AVL樹的其它性質：
• 任一結點的平衡因子隻能取：-1、0或 1；如果樹中任意一個結點的平衡因子的絕對值大于1，則這棵二叉樹就失去平衡，不再是AVL樹；；
•對于一棵有n個結點的AVL樹，其高度保持在O(log2n)數量級，ASL也保持在O(log2n)量級。
二、 平衡調整----旋轉
如果在一棵AVL樹中插入一個新結點，就有可能造成失衡，此時必須重新調整樹的結構，使之恢複平衡。我們稱調整平衡過程為平衡旋轉。無論是右旋還是左旋，都不改變二叉樹的中序周遊結果。
1. 右旋（順時針方向旋轉）
結點v 是結點p 的左孩子，X和Y分别是v 的左、右子樹，Z為p的右子樹。所謂圍繞結點p 的右旋操作，就是重新調整這些結點位置，将p作為v 的右孩子，将X 作為v 的左子樹，将Y和Z分别作為p的左、右子樹。圍繞p右旋的結果。
2. 左旋（逆時針方向旋轉）
結點v 是結點p 的右孩子，Y 和Z 分别是v的左、右子樹，X 為p 的左子樹。所謂圍繞結點p 的左旋操作，就是将p 作為v 的左孩子，将Z 作為v 的右子樹，将X 和Y 分别作為p 的左、右子樹。圍繞p左旋的結果如圖所示。
三、 插入操作
一般的，若在插入新的結點x 之後AVL 樹T失去平衡，則失去平衡的結點隻可能是x的祖先，且層次數小于等于x 的祖父的結點；也就是說失去平衡的結點是從x 的祖父到根的路徑上的結點，但這些結點并不都是失去平衡的結點，有些結點仍然可能是平衡的。為了修正失衡的現象，可以從結點x 出發逆行向上，依次檢查x 祖先的平衡因子，找到第一個失衡的祖先結點g。在從x 到g 的路徑上，假設p 為g 的孩子結點，v 為p 的孩子結點。有結點p、v 必不為空，p 至少是x 的父親，v 至少是x 本身。結點g、p、v 之間的父子關系共有4 種不同的組合，以下根據這4 種不同的組合，通過對結點g、p的旋轉，使這一局部恢複平衡。
平衡旋轉可以歸納為四類：
- LL平衡旋轉
- RR平衡旋轉
- LR平衡旋轉
- RL平衡旋轉
1）LL平衡旋轉： p 是g的左孩子，且v是p的左孩子；
在這種情況下，必定是由于在v 的後代中插入了新結點x 而使得g不再平衡。針對這種情況，可以簡單的通過結點g 的單向右旋，即可使得以g為根的子樹得到平衡
2）RR平衡旋轉： p是g的右孩子，且v 是p的右孩子；
與第一種情況對稱，此時，失衡是由于在g 的右孩子的右子樹中插入結點x造成的。在這種情況下需要通過結點g 的單向左旋來完成局部的平衡。
3）LR平衡旋轉： p是g的左孩子，且v是p的右孩子；
如果是在p 的左孩子的右子樹中插入一個結點，則對應為第三種情況。在這種情況中，要使得局部的失衡重新平衡，那麼需要先後進行先左後右的雙向旋轉：第一次是結點p的左旋，第二次是結點g 的右旋。
4）RL平衡旋轉：
p是g的右孩子，且v是p的左孩子；第四種情況與第三種情況對稱，其平衡調整過程也與第三種情況對稱，可以通過先右後左的雙向旋轉來完成，其中第一次是結點p 的右旋，第二次是結點g的左旋。
四、 删除節點
按照通常的二叉查找樹删除結點的方法在AVL樹中删除結點x之後，如果發生失衡現象，為了重新平衡，同樣從x出發逆行向上找到第一個失衡的結點g，通過旋轉操作實作AVL樹的重新平衡。使得結點g失衡的原因可以看成四種：
1. 失衡是由于 g 的左孩子的左子樹過高造成的；
2. 失衡是由于 g 的右孩子的右子樹過高造成的；
3. 失衡是由于 g 的左孩子的右子樹過高造成的；
4. 失衡是由于 g 的右孩子的左子樹過高造成的。
這四種情況與插入結點導緻失衡的四種情況進行平衡化的旋轉方法相同。但是需要注意兩個特殊情況：失衡可能是由于左（右）孩子的左、右子樹同時過高造成的，
五、 旋轉操作的統一實作方法
前面介紹的4 種平衡旋轉操作，需要根據結點g、p、v（p是g的孩子，v是p的孩子）之間的互相關系來判斷應該使用的旋轉方法。為此，在這裡引入一種統一的算法，這種實作簡潔、直覺，容易實作。
在插入或删除結點x 之後，從x出發逆行向上，找到第一個失衡的結點g，然後根據g失衡的原因,設定p和v的指向，p 和v都是其父結點較高子樹的根。此時，在這一局部，以p的兄弟為根有一棵子樹，即g 較矮的子樹；以v的兄弟為根有一棵子樹，即p較矮的子樹；v有兩棵子樹；一共有4棵子樹。注意，在這4棵子樹中可能有空樹。顯然，以失衡結點g 為根的局部平衡是在這3 個結點和4棵子樹間完成的。
在确定了這3 個結點和4棵子樹之後，接着為它們重命名。具體的命名方法是，從左到右将4 棵子樹命名為T0、T1、T2、T3；按照中序順序将結點g、p、v 分别命名為a、b、c。
四種不同旋轉情況的命名見圖所示。
一旦完成重命名，無論對于那種情況，我們都能以相同的方法将這3 個結點和4棵子樹重新組合起來，以達到旋轉平衡的目的。如圖（e）所示，以結點b作為局部子樹的根，結點a 和c 分别是b 的左孩子和右孩子，結點a 的左右子樹分别是T0、T1，結點c的左右子樹分别是T2、T3。
算法rotate
輸入：失衡的結點z
輸出：平衡後子樹的根結點
private BinTreeNode rotate(BinTreeNode z) {
BinTreeNode y = higherSubT(z); // 取y為z更高的孩子
BinTreeNode x = higherSubT(y); // 取x為y更高的孩子
boolean isLeft = z.isLChild(); // 記錄：z是否左孩子
BinTreeNode p = z.getParent(); // p為z的父親
BinTreeNode a, b, c; // 自左向右，三個節點
BinTreeNode t0, t1, t2, t3; // 自左向右，四棵子樹
// 以下分四種情況
if (y.isLChild()) { // 若y是左孩子，則
c = z;
t3 = z.getRChild();
if (x.isLChild()) { // 若x是左孩子(左左失衡)
b = y;
t2 = y.getRChild();
a = x;
t1 = x.getRChild();
t0 = x.getLChild();
} else { // 若x是右孩子(左右失衡)
a = y;
t0 = y.getLChild();
b = x;
t1 = x.getLChild();
t2 = x.getRChild();
}
} else { // 若y是右孩子，則
a = z;
t0 = z.getLChild();
if (x.isRChild()) { // 若x是右孩子(右右失衡)
b = y;
t1 = y.getLChild();
c = x;
t2 = x.getLChild();
t3 = x.getRChild();
} else { // 若x是左孩子(右左失衡)
c = y;
t3 = y.getRChild();
b = x;
t1 = x.getLChild();
t2 = x.getRChild();
}
}
// 摘下三個節點
z.sever();
y.sever();
x.sever();
// 摘下四棵子樹
if (t0 != null)
t0.sever();
if (t1 != null)
t1.sever();
if (t2 != null)
t2.sever();
if (t3 != null)
t3.sever();
// 重新連結
a.setLChild(t0);
a.setRChild(t1);
c.setLChild(t2);
c.setRChild(t3);
b.setLChild(a);
b.setRChild(c);
// 子樹重新接入原樹
if (p != null)
if (isLeft)
p.setLChild(b);
else
p.setRChild(b);
return b;// 傳回新的子樹根
}
AVL 樹也是一棵二叉查找樹，則AVL 樹的實作可以通過繼承二叉查找樹來實作。AVL樹與一般二叉查找樹不同的是，在插入和删除結點之後需要重新進行平衡。是以，隻需要重寫insert 和remove 方法即可。
package dsa.adt;
import dsa.strategy.Strategy;
public class AVLTree extends BSTree {
public AVLTree() {
super();
}
public AVLTree(Strategy strategy) {
super(strategy);
}
private boolean isBalance(BinTreeNode v) {
if (v == null)
return true;
int lH = (v.hasLChild()) ? v.getLChild().getHeight() : -1;
int rH = (v.hasRChild()) ? v.getRChild().getHeight() : -1;
return (Math.abs(lH - rH) <= 1);
}
private BinTreeNode higherSubT(BinTreeNode v) {
if (v == null)
return null;
int lH = (v.hasLChild()) ? v.getLChild().getHeight() : -1;
int rH = (v.hasRChild()) ? v.getRChild().getHeight() : -1;
if (lH > rH)
return v.getLChild();
if (lH < rH)
return v.getRChild();
if (v.isLChild())
return v.getLChild();
else
return v.getRChild();
}
private BinTreeNode rotate(BinTreeNode z) {
BinTreeNode y = higherSubT(z); // 取y為z更高的孩子
BinTreeNode x = higherSubT(y); // 取x為y更高的孩子
boolean isLeft = z.isLChild(); // 記錄：z是否左孩子
BinTreeNode p = z.getParent(); // p為z的父親
BinTreeNode a, b, c; // 自左向右，三個節點
BinTreeNode t0, t1, t2, t3; // 自左向右，四棵子樹
// 以下分四種情況
if (y.isLChild()) { // 若y是左孩子，則
c = z;
t3 = z.getRChild();
if (x.isLChild()) { // 若x是左孩子(左左失衡)
b = y;
t2 = y.getRChild();
a = x;
t1 = x.getRChild();
t0 = x.getLChild();
} else { // 若x是右孩子(左右失衡)
a = y;
t0 = y.getLChild();
b = x;
t1 = x.getLChild();
t2 = x.getRChild();
}
} else { // 若y是右孩子，則
a = z;
t0 = z.getLChild();
if (x.isRChild()) { // 若x是右孩子(右右失衡)
b = y;
t1 = y.getLChild();
c = x;
t2 = x.getLChild();
t3 = x.getRChild();
} else { // 若x是左孩子(右左失衡)
c = y;
t3 = y.getRChild();
b = x;
t1 = x.getLChild();
t2 = x.getRChild();
}
}
// 摘下三個節點
z.sever();
y.sever();
x.sever();
// 摘下四棵子樹
if (t0 != null)
t0.sever();
if (t1 != null)
t1.sever();
if (t2 != null)
t2.sever();
if (t3 != null)
t3.sever();
// 重新連結
a.setLChild(t0);
a.setRChild(t1);
c.setLChild(t2);
c.setRChild(t3);
b.setLChild(a);
b.setRChild(c);
// 子樹重新接入原樹
if (p != null)
if (isLeft)
p.setLChild(b);
else
p.setRChild(b);
return b;// 傳回新的子樹根
}
private BinTreeNode reBalance(BinTreeNode v) {
if (v == null)
return root;
BinTreeNode c = v;
while (v != null) { // 從v開始，向上逐一檢查z的祖先
if (!isBalance(v))
v = rotate(v); // 若v失衡，則旋轉使之重新平衡
c = v;
v = v.getParent(); // 繼續檢查其父親
}// while
return c;
}
// 按關鍵字插入元素ele
public void insert(Object ele) {
super.insert(ele);
root = reBalance(startBN);
}
// 若查找表中存在與元素ele關鍵字相同元素，則删除一個并傳回；否則，傳回null
public Object remove(Object ele) {
Object obj = super.remove(ele);
root = reBalance(startBN);
return obj;
}
}