一、 為什么會有平衡二叉樹
二叉查找樹雖然在效率上已經(jīng)很高了，但是效率并不是最高的，而且給出一列數(shù)字，我們可以構(gòu)造出多個二叉查找樹出來；不同的二叉查找樹因為樹的深度不同，效率不一樣，因此平衡二叉樹就是解決這個問題的，效率最高，構(gòu)造出來的二叉樹唯一；
二、平衡二叉樹定義
或者是一顆空樹，或者同時具有如下的性質(zhì)：
- 他的左子樹和右子樹都是平衡二叉樹；
- 左子樹和右子樹的深度之差的絕對值不超過1；
平衡因子：一個的左子樹深度減去他的右子樹的深度。則平衡二叉樹的特點可以描述為：平衡二叉樹所有節(jié)點的平衡因子只可能為-1、0、1。
三、研究平衡二叉樹的目的
隨著節(jié)點的插入，不可避免的會破壞平衡二叉樹的結(jié)構(gòu)，因此我們必須讓之回到平衡二叉樹的狀態(tài)；
而且我們只能使用暴力的方式來使二叉樹重新回到平衡狀態(tài)，即每插入一個節(jié)點，就進行一次調(diào)整，
研究平衡二叉樹就是研究這個調(diào)整的過程；
四、 平衡二叉樹代碼實現(xiàn)
public class AVLTree<E> {
//標記左邊高，需要調(diào)整
public static final int LEFT_HIGH = 1;
//標記右邊高，需要調(diào)整
public static final int RIGHT_HIGH = -1;
//標記兩邊一樣高，不需要調(diào)整
public static final int EQUAL_HIGH = 0;
private TreeNode<E> root;
private int size;
/**
* 插入一個元素，同時需要計算平衡因子,檢查平衡情況，做出旋轉(zhuǎn)調(diào)整
* @param element
* @return
*/
public boolean insertElement(E element) {
TreeNode<E> t = root;
//一個節(jié)點都沒有，構(gòu)造節(jié)點，作為根節(jié)點
if (t == null) {
t = new TreeNode<>(element, null);
root = t;
size++;//其實現(xiàn)在size=1;等價于size=1;
return true;
}
//如果走到這里，說明已經(jīng)有了跟節(jié)點，就需要先判斷插入的位置
//這里隱含了一個前提條件，在插入之前，整棵樹已經(jīng)平衡了，
//實際上這個條件是一定滿足的，因為在插入之后，就會判斷樹是否是平衡的
//用來記錄比較樹的平衡度的變量
int comparator = 0;
//保存父節(jié)點
TreeNode<E> parent;
//因為是泛型，不能對象的大小，就通過比較器來實現(xiàn)比較大小
//? super E: E或者E的父類 ? 這里是不是有問題，因該是E或者E的子類
Comparable<? super E> e = (Comparable<? super E>) element;
do {
parent = t;
//把當前結(jié)點和父節(jié)點比較大小，
comparator = e.compareTo(t.element);
if (comparator < 0) {//說明e小,王parent的左子樹上走
t = t.leftChild;
} else if (comparator > 0) {
t = t.rightChild;
} else {
//相等就不需要插入
return false;
}
} while (t != null);
//while循環(huán)結(jié)束之后，就找到了需要插入節(jié)點的位置,即在那個節(jié)點下插入，
// 但是還不能確定是插入在這個節(jié)點的左邊，還是右邊，這個需要判斷
TreeNode<E> child = new TreeNode<>(element, parent);
//插入左邊還是右邊
if (comparator < 0) {
//插入左邊
parent.leftChild = child;
} else {
//插入右邊
parent.rightChild = child;
}
//節(jié)點的位置已經(jīng)找到了，并且成功插入，接下來就要判斷新的樹是否平衡了
//因為在插入之前樹已經(jīng)是平衡的了，所以如果樹是不平衡的，一定是因為新插入的節(jié)點引起的，
//因此采用回溯法來判斷新插入的節(jié)點的父節(jié)點，爺爺節(jié)點是否平衡
while (parent != null) {
comparator = e.compareTo(parent.element);
if (comparator < 0) {
//相當于插在parent的左子樹上，因此parent的平衡因子+1
parent.balance++;
} else {
parent.balance--;
}
if (parent.balance == 0) {
//即插入的節(jié)點使得樹平衡了，說明插入的節(jié)點不影響樹的平衡性
break;
}
//某一個節(jié)點的平衡度最大值只能為2，可能出現(xiàn)的值為-2，-1，0，1，2
//當為-2，2時，需要調(diào)整，這里才出現(xiàn)問題
if (Math.abs(parent.balance) == 2) {
fixAfterInsert(parent);
}
//如果當前節(jié)點沒有問題，就接著回溯
parent = parent.parent;
}
size++;
return true;
}
/**
* 根據(jù)某個不平衡的節(jié)點對樹進行旋轉(zhuǎn)，使其平衡
* @param parent
*/
private void fixAfterInsert(TreeNode<E> parent) {
if (parent.balance == 2) {
//說明左邊高,要進行做平衡操作
leftBalance(parent);
} else if (parent.balance == -2) {
//說明右邊高，要進行右平衡操作
rightBalance(parent);
}
}
private void rightBalance(TreeNode<E> t) {
TreeNode rc = t.rightChild;
switch (rc.balance) {
case LEFT_HIGH:
TreeNode lc = rc.leftChild;
switch (lc.balance) {
case LEFT_HIGH:
t.balance = EQUAL_HIGH;
rc.balance = RIGHT_HIGH;
lc.balance = EQUAL_HIGH;
break;
case RIGHT_HIGH:
t.balance = LEFT_HIGH;
rc.balance = EQUAL_HIGH;
lc.balance = EQUAL_HIGH;
break;
case EQUAL_HIGH:
t.balance = EQUAL_HIGH;
rc.balance = EQUAL_HIGH;
lc.balance = EQUAL_HIGH;
break;
}
rightRotate(t.rightChild);
leftRotate(t);
break;
case RIGHT_HIGH:
leftBalance(t);
//旋轉(zhuǎn)之后節(jié)點的平衡度發(fā)生了變化
rc.balance = EQUAL_HIGH;
t.balance = EQUAL_HIGH;
break;
case EQUAL_HIGH:
break;
}
}
/**
* 節(jié)點t左邊的子樹過高
* @param t
*/
private void leftBalance(TreeNode<E> t) {
TreeNode<E> lc = t.leftChild;
//只知道lc的平衡度除了問題，但是不知道是那種情況，是lc的左邊，右邊，還是左右平衡，因此需要進行判斷
switch (lc.balance) {
case LEFT_HIGH://lc的左邊出了問題，直接進行右旋，但是是旋轉(zhuǎn)t的整個部分
rightRotate(t);
lc.balance = EQUAL_HIGH;
t.balance = EQUAL_HIGH;
break;
case RIGHT_HIGH:
TreeNode rc = lc.rightChild;
switch (rc.balance) {
case LEFT_HIGH:
lc.balance = EQUAL_HIGH;
t.balance = RIGHT_HIGH;
rc.balance = EQUAL_HIGH;
break;
case RIGHT_HIGH:
t.balance = EQUAL_HIGH;
rc.balance = EQUAL_HIGH;
lc.balance = LEFT_HIGH;
break;
case EQUAL_HIGH:
t.balance = EQUAL_HIGH;
lc.balance = EQUAL_HIGH;
rc.balance = EQUAL_HIGH;
break;
}
//統(tǒng)一旋轉(zhuǎn)
leftRotate(t.leftChild);
rightRotate(t);
break;
case EQUAL_HIGH:
break;
}
}
private void leftRotate(TreeNode p) {
if (p != null) {
TreeNode rc = p.rightChild;
p.rightChild = rc.leftChild;//把中間夾的多余的元素鏈接到p的右下
if (rc.leftChild != null) {
rc.leftChild.parent = p;
}
rc.parent = p.parent;//rc旋轉(zhuǎn)過來作為新樹的節(jié)點，任然連著以前的父節(jié)點
if (p.parent == null) {
root = rc;
} else if (p == p.parent.leftChild) {
p.parent.leftChild = rc;
} else if (p == p.parent.rightChild) {
p.parent.rightChild = rc;
}
rc.leftChild = p;
p.parent = rc;
}
}
private void rightRotate(TreeNode<E> p) {
if (p != null) {
TreeNode lc = p.leftChild;
p.leftChild = lc.rightChild;
if (lc.rightChild != null) {
lc.rightChild.parent = p;
}
lc.parent = p.parent;
if (p.parent == null) {
root = lc;
} else if (p == p.parent.leftChild) {
p.parent.leftChild = lc;
} else if (p == p.parent.rightChild) {
p.parent.rightChild = lc;
}
lc.rightChild = p;
p.parent = lc;
}
}
private class TreeNode<E> {
private E element;//節(jié)點的數(shù)據(jù)域
private int balance;//節(jié)點的平衡因子，如果絕對值大于1，就表示需要調(diào)整
private TreeNode leftChild;
private TreeNode rightChild;
private TreeNode parent;
public TreeNode(E element, TreeNode parent) {
this.element = element;
this.parent = parent;
}
@Override
public String toString() {
//打印當前結(jié)點以及平衡因子
return element + ",BF:" + balance;
}
public E getElement() {
return element;
}
public void setElement(E element) {
this.element = element;
}
public int getBalance() {
return balance;
}
public void setBalance(int balance) {
this.balance = balance;
}
public TreeNode getLeftChild() {
return leftChild;
}
public void setLeftChild(TreeNode leftChild) {
this.leftChild = leftChild;
}
public TreeNode getRightChild() {
return rightChild;
}
public void setRightChild(TreeNode rightChild) {
this.rightChild = rightChild;
}
public TreeNode getParent() {
return parent;
}
public void setParent(TreeNode parent) {
this.parent = parent;
}
}
}