什么是AVL樹？
首先，回憶一下二分搜索樹的問題，在二分搜索樹中有一個(gè)很嚴(yán)重的問題，什么問題呢？
在二分搜索樹中如果順序添加元素會轉(zhuǎn)化為鏈表，這就會大大降低二分搜索樹的效率。比如說1、2、3、4、5、6。
二分搜索樹如圖：
那么如何解決這個(gè)問題？
需要在二分搜索樹的基礎(chǔ)上添加一定的機(jī)制，使得二分搜索樹能夠維持平衡二叉樹這樣的性質(zhì)。AVL樹就是一種經(jīng)典的平衡二叉樹。
在AVL樹中維護(hù)平衡型的條件是，對于任意一個(gè)節(jié)點(diǎn)，左子樹和右子樹的高度差不能超過1。
如圖：
平衡因子：計(jì)算節(jié)點(diǎn)左右子樹節(jié)點(diǎn)的高度差為該節(jié)點(diǎn)的平衡因子。平衡二叉樹上所有節(jié)點(diǎn)的平衡因子只可能是-1、0、1。如果某個(gè)節(jié)點(diǎn)的平衡因子大于1則說明此樹不是平衡二叉樹。
如圖：
如果不是平衡二叉樹，那么什么時(shí)候維護(hù)平衡呢？
在二分搜索樹中如果插入一個(gè)節(jié)點(diǎn)的話，會從根節(jié)點(diǎn)開始進(jìn)行尋找，直到找到這個(gè)節(jié)點(diǎn)的正確位置，并且正確的位置一般都是葉子節(jié)點(diǎn)的位置。
大家可以想象一下，由于新添加了節(jié)點(diǎn)才有可能導(dǎo)致二分搜索樹不再滿足平衡性，那么相應(yīng)的這個(gè)不平衡的節(jié)點(diǎn)只有可能發(fā)生在從我們插入的位置開始向父親節(jié)點(diǎn)去找，發(fā)生在這些節(jié)點(diǎn)中，為什么呢？這是因?yàn)?，在插入新?jié)點(diǎn)后才破壞了整棵樹的平衡性。
那么，破壞整棵樹的平衡性，將反映在新節(jié)點(diǎn)的父親節(jié)點(diǎn)或祖先節(jié)點(diǎn)，因?yàn)椴迦胄鹿?jié)點(diǎn)之后它的父親節(jié)點(diǎn)或祖先節(jié)點(diǎn)相應(yīng)的左右子樹的高度值需要進(jìn)行更新，更新之后有可能平衡因子就會大于1或小于-1。
所以維護(hù)平衡的時(shí)機(jī)，應(yīng)該是當(dāng)我們添加節(jié)點(diǎn)之后，沿著該節(jié)點(diǎn)向上回溯來維護(hù)平衡性。
旋轉(zhuǎn)操作
1、右旋轉(zhuǎn)（LL）
上圖中，對于這個(gè)y節(jié)點(diǎn)來說，它已經(jīng)不滿足平衡二叉樹的條件了，也就是說左子樹的高度比右子樹的告訴要高，并且這個(gè)高度差大于1，與此同時(shí)，它的左孩子也是這樣的情況，左子樹的高度大于等于右子樹的。
以y節(jié)點(diǎn)為根節(jié)點(diǎn)的這顆子樹整體不滿足平衡二叉樹的性質(zhì)，并且整體是向左傾斜的，它們的右側(cè)也有可能有子樹。如圖：
如上圖，對于二分搜索樹來說，它就會存在 T1 < z < T2 < x < T3 < y < T4 這樣的關(guān)系。
在這個(gè)圖中，y節(jié)點(diǎn)的左子樹過于高了，所以經(jīng)過一系列操作使得y節(jié)點(diǎn)保持平衡性，并且整顆子樹不能夠失去二分搜索樹的性質(zhì)，這個(gè)操作就叫作右旋轉(zhuǎn)。
右旋轉(zhuǎn)的過程：
首先讓x的右子樹變成以y為根的子樹，之后讓y節(jié)點(diǎn)的左子樹變成剛剛x節(jié)點(diǎn)的右子樹T3，這樣做完以后，讓x變成新的二分搜索樹的根節(jié)點(diǎn)，這樣的過程就叫做右旋轉(zhuǎn)。
這個(gè)過程對于y節(jié)點(diǎn)來說，它順時(shí)針轉(zhuǎn)到x節(jié)點(diǎn)的右子樹的位置，這個(gè)順時(shí)針的方向從x的角度來看就是向右進(jìn)行一個(gè)旋轉(zhuǎn)，此時(shí)這顆樹既滿足二分搜索樹的性質(zhì)又滿足平衡二叉樹的性質(zhì)。
如圖：
2、左旋轉(zhuǎn)（RR）
左旋轉(zhuǎn)與右旋轉(zhuǎn)相反，右旋轉(zhuǎn)插入的元素在不平衡節(jié)點(diǎn)的左側(cè)的左側(cè)，而左旋轉(zhuǎn)對應(yīng)的要做的事情
就是要糾正如果插入的元素在不平衡節(jié)點(diǎn)的右側(cè)的右側(cè)。
上圖中，所展示的二叉樹與右旋轉(zhuǎn)所展示的二叉樹完全是一個(gè)左右對稱的情況，只不過對于這顆二叉樹來說，當(dāng)前不平衡節(jié)點(diǎn)為y的話，它的右子樹高度值比左子樹值相差大于1，換句話說左子樹的高度值減去右子樹的高度值小于-1，這樣的情況下，要進(jìn)行左旋轉(zhuǎn)。
當(dāng)前這顆二叉樹的大小關(guān)系如下：T4 < y < T3 < x <T1 < z < T2
左旋轉(zhuǎn)的過程：
首先讓x的左子樹為y，之后讓y的右子樹為剛剛的x的左子樹，這樣以后讓x變?yōu)樾碌母?jié)點(diǎn)，這樣的過程就叫做左旋轉(zhuǎn)。
如圖：
3、LR
LR的情況是插入的元素在左側(cè)的右側(cè)。如圖：
那么如何處理呢？
首先對x節(jié)點(diǎn)進(jìn)行左旋轉(zhuǎn)，轉(zhuǎn)化為LL的情況。如圖：
此時(shí)再對y節(jié)點(diǎn)進(jìn)行右旋轉(zhuǎn)。
4、RL
RL的情況是插入的元素在右側(cè)的左側(cè)。如圖：
RL和LR處理的情況相反，首先對x節(jié)點(diǎn)進(jìn)行右旋轉(zhuǎn)，轉(zhuǎn)化為RR的情況。如圖：
此時(shí)再對y節(jié)點(diǎn)進(jìn)行左旋轉(zhuǎn)。
AVL的實(shí)現(xiàn)
代碼如下：
/**
* 描述：平衡二叉樹（AVL樹）。
* <p>
* Create By ZhangBiao
* 2020/5/17
*/
public class AVLTree<K extends Comparable<K>, V> {
private Node root;
private int size;
public AVLTree() {
this.root = null;
this.size = 0;
}
@Override
public void add(K key, V value) {
root = add(root, key, value);
}
/**
* 向以node為根節(jié)點(diǎn)的二分搜索樹中插入元素(key, value)（遞歸算法）并返回插入新節(jié)點(diǎn)后二分搜索樹的根節(jié)點(diǎn)
*
* @param node
* @param key
* @param value
* @return
*/
private Node add(Node node, K key, V value) {
if (node == null) {
size++;
return new Node(key, value);
}
if (key.compareTo(node.key) < 0) {
node.left = add(node.left, key, value);
} else if (key.compareTo(node.key) > 0) {
node.right = add(node.right, key, value);
} else {
node.value = value;
}
//更新height
node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
//計(jì)算平衡因子
int balanceFactor = getBalanceFactor(node);
/*if (Math.abs(balanceFactor) > 1) {
System.out.println("unbalanced: " + balanceFactor);
}*/
//平衡維護(hù)
//LL
if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0) {
return rightRotate(node);
}
//RR
if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0) {
return leftRotate(node);
}
//LR
if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
//RL
if (balanceFactor < -1 && getBalanceFactor(node.right) > 0) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
return node;
}
/**
* 返回以node為根節(jié)點(diǎn)的二分搜索樹的最小值所在的節(jié)點(diǎn)
*
* @param node
* @return
*/
private Node minimum(Node node) {
if (node.left == null) {
return node;
}
return minimum(node.left);
}
/**
* 刪除掉以node為根的二分搜索樹中的最小節(jié)點(diǎn)并返回刪除節(jié)點(diǎn)后新的二分搜索樹的根
*
* @param node
* @return
*/
private Node removeMin(Node node) {
if (node.left == null) {
Node rightNode = node.right;
node.right = null;
size--;
return rightNode;
}
node.left = removeMin(node.left);
return node;
}
@Override
public V remove(K key) {
Node node = getNode(root, key);
if (node != null) {
root = remove(root, key);
return node.value;
}
return null;
}
private Node remove(Node node, K key) {
if (node == null) {
return null;
}
Node retNode;
if (key.compareTo(node.key) < 0) {
node.left = remove(node.left, key);
retNode = node;
} else if (key.compareTo(node.key) > 0) {
node.right = remove(node.right, key);
retNode = node;
} else { //key.compareTo(node.key) == 0
//待刪除節(jié)點(diǎn)左子樹為空的情況
if (node.left == null) {
Node rightNode = node.right;
node.right = null;
size--;
retNode = rightNode;
} else if (node.right == null) {
//待刪除節(jié)點(diǎn)右子樹為空的情況
Node leftNode = node.left;
node.left = null;
size--;
retNode = leftNode;
} else {
Node successor = minimum(node.right);
successor.right = remove(node.right, successor.key);
successor.left = node.left;
node.left = node.right = null;
retNode = successor;
}
}
if (retNode == null) {
return null;
}
//更新height
retNode.height = 1 + Math.max(getHeight(retNode.left), getHeight(retNode.right));
//計(jì)算平衡因子
int balanceFactor = getBalanceFactor(retNode);
//平衡維護(hù)
//LL
if (balanceFactor > 1 && getBalanceFactor(retNode.left) >= 0) {
return rightRotate(retNode);
}
//RR
if (balanceFactor < -1 && getBalanceFactor(retNode.right) <= 0) {
return leftRotate(retNode);
}
//LR
if (balanceFactor > 1 && getBalanceFactor(retNode.left) < 0) {
retNode.left = leftRotate(retNode.left);
return rightRotate(retNode);
}
//RL
if (balanceFactor < -1 && getBalanceFactor(retNode.right) > 0) {
retNode.right = rightRotate(retNode.right);
return leftRotate(retNode);
}
return retNode;
}
@Override
public boolean contains(K key) {
return getNode(root, key) != null;
}
@Override
public V get(K key) {
Node node = getNode(root, key);
return node == null ? null : node.value;
}
@Override
public void set(K key, V newValue) {
Node node = getNode(root, key);
if (node == null) {
throw new IllegalArgumentException(key + " not exist!");
}
node.value = newValue;
}
@Override
public int getSize() {
return this.size;
}
@Override
public boolean isEmpty() {
return this.size == 0;
}
/**
* 獲取節(jié)點(diǎn)node的高度
*
* @param node
* @return
*/
private int getHeight(Node node) {
if (node == null) {
return 0;
}
return node.height;
}
/**
* 獲取節(jié)點(diǎn)node的平衡因子
*
* @param node
* @return
*/
private int getBalanceFactor(Node node) {
if (node == null) {
return 0;
}
return getHeight(node.left) - getHeight(node.right);
}
/**
* 判斷該二叉樹是否是一顆二分搜索樹
*
* @return
*/
public boolean isBST() {
ArrayList<K> keys = new ArrayList<>();
inOrder(root, keys);
for (int i = 1; i < keys.size(); i++) {
if (keys.get(i - 1).compareTo(keys.get(i)) > 0) {
return false;
}
}
return true;
}
private void inOrder(Node node, ArrayList<K> keys) {
if (node == null) {
return;
}
inOrder(node.left, keys);
keys.add(node.key);
inOrder(node.right, keys);
}
/**
* 判斷該二叉樹是否是一顆平衡二叉樹
*
* @return
*/
public boolean isBalanced() {
return isBalanced(root);
}
/**
* 判斷以node為根節(jié)點(diǎn)的二叉樹是否是一顆平衡二叉樹（遞歸算法）
*
* @param node
* @return
*/
private boolean isBalanced(Node node) {
if (node == null) {
return true;
}
int balanceFactor = getBalanceFactor(node);
if (Math.abs(balanceFactor) > 1) {
return false;
}
return isBalanced(node.left) && isBalanced(node.right);
}
// 對節(jié)點(diǎn)y進(jìn)行向右旋轉(zhuǎn)操作，返回旋轉(zhuǎn)后新的根節(jié)點(diǎn)x
// y x
// / \ / \
// x T4 向右旋轉(zhuǎn) (y) z y
// / \ - - - - - - - -> / \ / \
// z T3 T1 T2 T3 T4
// / \
// T1 T2
private Node rightRotate(Node y) {
Node x = y.left;
Node T3 = x.right;
//向右旋轉(zhuǎn)過程
x.right = y;
y.left = T3;
//更新height
y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
return x;
}
// 對節(jié)點(diǎn)y進(jìn)行向左旋轉(zhuǎn)操作，返回旋轉(zhuǎn)后新的根節(jié)點(diǎn)x
// y x
// / \ / \
// T1 x 向左旋轉(zhuǎn) (y) y z
// / \ - - - - - - - -> / \ / \
// T2 z T1 T2 T3 T4
// / \
// T3 T4
private Node leftRotate(Node y) {
Node x = y.right;
Node T2 = x.left;
//向左旋轉(zhuǎn)過程
x.left = y;
y.right = T2;
//更新height
y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
return x;
}
/**
* 返回以node為根節(jié)點(diǎn)的二分搜索樹中key所在的節(jié)點(diǎn)
*
* @param node
* @param key
* @return
*/
private Node getNode(Node node, K key) {
if (node == null) {
return null;
}
if (key.equals(node.key)) {
return node;
} else if (key.compareTo(node.key) < 0) {
return getNode(node.left, key);
} else {
return getNode(node.right, key);
}
}
private class Node {
public K key;
public V value;
public Node left;
public Node right;
public int height;
public Node(K key, V value, Node left, Node right) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
this.height = 1;
}
public Node(K key, V value) {
this(key, value, null, null);
}
public Node() {
this(null, null, null, null);
}
}
}
