首先來介紹一下什麼是AVL（平衡搜尋二叉樹），我們都知道BST（搜素二叉樹）在查詢某個值的時候時間複雜度可以達到O(logn)，但這個時間複雜度是最好的，如果按照BST樹的插入，我要按順序插入1，2，3，4，5這幾個數字，那麼最終的BST樹是這樣的
這棵樹的所有節點的左孩子都為空，這樣不就成了一個連結清單了，如果要搜尋一個數字，那麼時間複雜度就為O(n)，AVL就是使這棵BST樹平衡的一種政策，是以AVL也可以了解為平衡的BST樹。
AVL樹的定義是：該樹的所有節點的左右子樹高度不超過1
舉個例子，下圖就是一個平衡的BST樹
現在來了解一下AVL樹是怎麼樣保持平衡的
了解AVL樹之前，先了解AVL樹的幾個旋轉操作
- 左孩子的左子樹高
Java實作AVL：平衡搜尋二叉樹 首先需要注意這裡的x不管有沒有都可以定義為左孩子的左子樹太高了。
左孩子的左子樹太高時，該節點需要進行右旋，也就是40旋轉下來，這時為了保持BST樹的性質，是以x就得插到40的左邊
僞代碼：
child = node.left;
node.left = child.right;
chlid.right = node;
- 右孩子的右子樹高 右孩子的右子樹太高了，該節點進行左旋，也就是40從左邊旋轉下來，x插入到40的右邊以保證BST樹的性質。
Java實作AVL：平衡搜尋二叉樹
僞代碼：
child = node.right;
node.right = child.left;
child.left = node;
- 左孩子的右子樹高 可以看到導緻不平衡的原因是40的左孩子的右子樹，這時候如果對node直接進行右旋操作，那麼旋轉完還是不平衡的，見下圖：
Java實作AVL：平衡搜尋二叉樹 解決方法是我們需要先對node的左孩子進行左旋轉，然後再對node進行右旋轉，也叫左平衡。見下圖： Java實作AVL：平衡搜尋二叉樹 Java實作AVL：平衡搜尋二叉樹 -
右孩子的左子樹高
與情況3同理，不能一次旋轉就達到平衡，需要先對node的右孩子進行右旋，然後node左旋，也就是右平衡
Java實作AVL：平衡搜尋二叉樹
分析完了這四個過程，我們來把這四個過程封裝成方法
/**
* 以參數node為根節點進行左旋操作，把旋轉後的樹的根節點傳回
* @param node
* @return
*/
private AVLNode<T> leftRotate(AVLNode<T> node){
AVLNode<T> child = node.getRight();
node.setRight(child.getLeft());
child.setLeft(node);
return child;
}
/**
* 以參數node為根節點進行右旋操作，把旋轉後的樹的根節點傳回
* @param node
* @return
*/
private AVLNode<T> rightRotate(AVLNode<T> node){
AVLNode<T> child = node.getLeft();
node.setLeft(child.getRight());
child.setRight(node);
return child;
}
/**
* 以參數node為根節點進行左平衡操作，把旋轉後的樹的根節點傳回
* @param node
* @return
*/
private AVLNode<T> leftBalance(AVLNode<T> node){
node.setLeft(leftRotate(node.getLeft()));
return rightRotate(node);
}
/**
* 以參數node為根節點進行右平衡操作，把旋轉後的樹的根節點傳回
* @param node
* @return
*/
private AVLNode<T> rightBalance(AVLNode<T> node){
node.setRight(rightRotate(node.getRight()));
return leftRotate(node);
}
接下來我們需要定義AVL樹的資料結構，AVL樹比BST樹的節點就多了一個高度屬性，是以資料結構的定義可以參照BST樹來定義。
節點資料結構的定義：
class AVLNode<T extends Comparable<T>>{
private T data;
private AVLNode<T> left;
private AVLNode<T> right;
private int height; // 記錄節點目前的高度值
public AVLNode(T data, AVLNode<T> left, AVLNode<T> right, int height) {
this.data = data;
this.left = left;
this.right = right;
this.height = height;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public AVLNode<T> getLeft() {
return left;
}
public void setLeft(AVLNode<T> left) {
this.left = left;
}
public AVLNode<T> getRight() {
return right;
}
public void setRight(AVLNode<T> right) {
this.right = right;
}
public int getHeight() {
return height;
}
public void setHeight(int height) {
this.height = height;
}
}
AVL樹資料結構的定義：
public class AVL<T extends Comparable<T>> {
private AVLNode<T> root;
public AVL(){
this.root = null;
}
}
友善起見，封裝幾個工具函數
/**
* 擷取node為根節點的樹的高度，如果該節點為null，則傳回0，如果不為null，則傳回實際高度
* @param node
* @return
*/
private int height(AVLNode<T> node){
return node == null ? 0 : node.getHeight();
}
/**
* 傳回以node1和node2為根節點的子樹高度的最大值
* @param node1
* @param node2
* @return
*/
private int maxHeight(AVLNode<T> node1, AVLNode<T> node2){
int l = height(node1);
int r = height(node2);
return l > r ? l : r;
}
定義了資料結構以後，我們就要對上面的四個旋轉過程封裝的函數做一些修正，因為在剛才的過程中我們隻對怎麼樣旋轉做了描述，而沒有去管高度如何變化，是以在這個過程中我們需要加上高度的部分。
/**
* 以參數node為根節點進行左旋操作，把旋轉後的樹的根節點傳回
* @param node
* @return
*/
private AVLNode<T> leftRotate(AVLNode<T> node){
AVLNode<T> child = node.getRight();
node.setRight(child.getLeft());
child.setLeft(node);
//這裡計算高度是從下往上計算，旋轉後的node在下面
node.setHeight(maxHeight(node.getLeft(), node.getRight()) + 1);
child.setHeight(maxHeight(child.getLeft(), child.getRight()) + 1);
return child;
}
/**
* 以參數node為根節點進行右旋操作，把旋轉後的樹的根節點傳回
* @param node
* @return
*/
private AVLNode<T> rightRotate(AVLNode<T> node){
AVLNode<T> child = node.getLeft();
node.setLeft(child.getRight());
child.setRight(node);
node.setHeight(maxHeight(node.getLeft(), node.getRight()) + 1);
child.setHeight(maxHeight(child.getLeft(), child.getRight()) + 1);
return child;
}
/**
* 以參數node為根節點進行左平衡操作，把旋轉後的樹的根節點傳回
* @param node
* @return
*/
private AVLNode<T> leftBalance(AVLNode<T> node){
node.setLeft(leftRotate(node.getLeft()));
return rightRotate(node);
}
/**
* 以參數node為根節點進行右平衡操作，把旋轉後的樹的根節點傳回
* @param node
* @return
*/
private AVLNode<T> rightBalance(AVLNode<T> node){
node.setRight(rightRotate(node.getRight()));
return leftRotate(node);
}
增加删除的過程就是套用BST的過程，隻不過需要注意旋轉和高度的變化
/**
* 遞歸實作AVL樹的插入操作
* @param data
*/
public void insert(T data){
this.root = insert(this.root, data);
}
/**
* 以參數root為起始節點，搜尋一個合适的位置添加data，然後把子樹的根節點傳回
* @param root
* @param data
* @return
*/
private AVLNode<T> insert(AVLNode<T> root, T data) {
if(root == null){
return new AVLNode<>(data, null, null, 1);
}
if(root.getData().compareTo(data) > 0){
root.setLeft(insert(root.getLeft(), data));
// 判斷root節點是否失衡 #1
if(height(root.getLeft()) - height(root.getRight()) > 1){
if(height(root.getLeft().getLeft())
>= height(root.getLeft().getRight())){
// 左孩子的左子樹太高
root = rightRotate(root);
} else {
// 左孩子的右子樹太高
root = leftBalance(root);
}
}
} else if(root.getData().compareTo(data) < 0){
root.setRight(insert(root.getRight(), data));
// 判斷root節點是否失衡 #2
if(height(root.getRight()) - height(root.getLeft()) > 1){
if(height(root.getRight().getRight())
>= height(root.getRight().getLeft())){
// 右孩子的右子樹太高
root = leftRotate(root);
} else {
// 右孩子的左子樹太高
root = rightBalance(root);
}
}
}
// 遞歸回溯過程中，更新節點的高度值 #3
root.setHeight(maxHeight(root.getLeft(), root.getRight()) + 1);
return root;
}
/**
* 實作AVL樹的遞歸删除
* @param data
*/
public void remove(T data){
this.root = remove(this.root, data);
}
private AVLNode<T> remove(AVLNode<T> root, T data) {
if(root == null){
return null;
}
if(root.getData().compareTo(data) > 0){
root.setLeft(remove(root.getLeft(), data));
// #1
if(height(root.getRight()) - height(root.getLeft()) > 1){
if(height(root.getRight().getRight())
>= height(root.getRight().getLeft())){
root = leftRotate(root);
} else {
root= rightBalance(root);
}
}
} else if(root.getData().compareTo(data) < 0){
// #2
root.setRight(remove(root.getRight(), data));
if(height(root.getLeft()) - height(root.getRight()) > 1){
if(height(root.getLeft().getLeft())
>= height(root.getLeft().getRight())){
root = rightRotate(root);
} else {
root= leftBalance(root);
}
}
} else {
if(root.getLeft() != null && root.getRight() != null){
// #3 左右子樹哪個高，删除哪個，為了防止删除帶來的旋轉操作，提高效率
if(height(root.getLeft()) >= height(root.getRight())){
// 用前驅替換
AVLNode<T> pre = root.getLeft();
while(pre.getRight() != null){
pre = pre.getRight();
}
root.setData(pre.getData());
root.setLeft(remove(root.getLeft(), pre.getData())); //删除前驅
} else {
// 用後繼替換
AVLNode<T> post = root.getRight();
while(post.getLeft() != null){
post = post.getLeft();
}
root.setData(post.getData());
root.setRight(remove(root.getRight(), post.getData())); // 删除後繼
}
} else {
if(root.getLeft() != null){
return root.getLeft();
} else if(root.getRight() != null){
return root.getRight();
} else {
return null;
}
}
}
// 遞歸回溯過程中，更新節點的高度值 #4
root.setHeight(maxHeight(root.getLeft(), root.getRight()) + 1);
return root;
}