參考：https://www.cnblogs.com/skywang12345/p/3577479.html
AVL樹(shù)本質(zhì)上還是一棵二叉搜索樹(shù)，它的特點(diǎn)是：
1.本身首先是一棵二叉搜索樹(shù)猩谊。
2.帶有平衡條件：每個(gè)結(jié)點(diǎn)的左右子樹(shù)的高度之差的絕對(duì)值（平衡因子）最多為1千劈。
也就是說(shuō)，AVL樹(shù)牌捷，本質(zhì)上是帶了平衡功能的二叉查找樹(shù)（二叉排序樹(shù)，二叉搜索樹(shù)）涡驮。
以下為四種不平衡的臨界條件暗甥，分別為L(zhǎng)L（leftleft）,LR（leftright）,RL,RR。
當(dāng)每次到達(dá)這四種不平衡的臨界條件時(shí)捉捅，都進(jìn)行旋轉(zhuǎn)樹(shù)操作撤防，那么樹(shù)就能維持平衡：
private AVLTreeNode leftLeftRotation(AVLTreeNode node) {
checkNull(node);
AVLTreeNode leftChild = node.left;
node.left = leftChild.right;
leftChild.right = node;
//reset the height
node.height = max(height(node.left), height(node.right)) + 1;
leftChild.height = max(height( leftChild.left), height( leftChild.right)) + 1;
return leftChild;
}
private AVLTreeNode rightRightRotation(AVLTreeNode node) {
checkNull(node);
AVLTreeNode rightChild = node.right;
node.right = rightChild.left;
rightChild.left = node;
node.height = max(height(node.left), height(node.right)) + 1;
rightChild.height = max(height( rightChild.left), height( rightChild.right)) + 1;
return rightChild;
}
private AVLTreeNode leftRightRotation(AVLTreeNode node) {
node.left = rightRightRotation(node.left);//先對(duì)node.left旋轉(zhuǎn)
return leftLeftRotation(node);//后對(duì)自己旋轉(zhuǎn)
}
private AVLTreeNode rightLeftRotation(AVLTreeNode node) {
node.right = leftLeftRotation(node.right);
return rightRightRotation(node);
}
結(jié)合插入和刪除，AVL樹(shù)的實(shí)現(xiàn)：
package DataStructureAndAlgor;
/**
* AVL樹(shù)
* 回顧的時(shí)候棒口，最好把LL,RR,LR,RL旋轉(zhuǎn)的四張圖畫(huà)出來(lái)寄月，好理解。
*
* @param <T>
*/
public class AVLTree<T extends Comparable<T>> {
class AVLTreeNode {
T key;
int height;
AVLTreeNode left;
AVLTreeNode right;
public AVLTreeNode(T key, AVLTreeNode left, AVLTreeNode right) {
this.key = key;
this.left = left;
this.right = right;
this.height = 0;//初始化的結(jié)點(diǎn)的height都是0无牵，因?yàn)槎际亲鳛槿~子結(jié)點(diǎn)添加到樹(shù)中的漾肮。
}
}
private AVLTreeNode mRoot;
private int height(AVLTreeNode tree) {
if (tree != null) {
return tree.height;
}
return 0;
}
public int height() {
return height(mRoot);
}
public int height(T key) {
AVLTreeNode node = search(mRoot, key);
return height(node);
}
private int max(int a, int b) {
return a > b ? a : b;
}
private AVLTreeNode leftLeftRotation(AVLTreeNode node) {
checkNull(node);
AVLTreeNode leftChild = node.left;
node.left = leftChild.right;
leftChild.right = node;
//reset the height
node.height = max(height(node.left), height(node.right)) + 1;
leftChild.height = max(height( leftChild.left), height( leftChild.right)) + 1;
return leftChild;
}
private AVLTreeNode rightRightRotation(AVLTreeNode node) {
checkNull(node);
AVLTreeNode rightChild = node.right;
node.right = rightChild.left;
rightChild.left = node;
node.height = max(height(node.left), height(node.right)) + 1;
rightChild.height = max(height( rightChild.left), height( rightChild.right)) + 1;
return rightChild;
}
private AVLTreeNode leftRightRotation(AVLTreeNode node) {
node.left = rightRightRotation(node.left);//先對(duì)node.left旋轉(zhuǎn)
return leftLeftRotation(node);//后對(duì)自己旋轉(zhuǎn)
}
private AVLTreeNode rightLeftRotation(AVLTreeNode node) {
node.right = leftLeftRotation(node.right);
return rightRightRotation(node);
}
private void checkNull(AVLTreeNode node) {
if (node == null) {
throw new NullPointerException();
}
}
/**
* 將結(jié)點(diǎn)插入到AVL樹(shù)種，并返回根節(jié)點(diǎn)茎毁。
*
* @param tree AVL樹(shù)的根節(jié)點(diǎn)
* @param key 待插入的結(jié)點(diǎn)的值克懊。
* @return 根節(jié)點(diǎn)
*/
private AVLTreeNode insert(AVLTreeNode tree, T key) {
if (tree == null) {//遞歸終點(diǎn)
tree = new AVLTreeNode(key, null, null);
} else {
int cmp = key.compareTo(tree.key);//compare result
if (cmp < 0) {
tree.left = insert(tree.left, key);//遞歸插入
//插入結(jié)點(diǎn)后，若AVLTree失去平衡七蜘，旋轉(zhuǎn)樹(shù)谭溉。
if (height(tree.left) - height(tree.right) == 2) {//說(shuō)明是tree結(jié)點(diǎn)出問(wèn)題(必須是left-right，否則得負(fù)值)
if (key.compareTo(tree.left.key) < 0) {//這里如果寫(xiě)成tree.right.key會(huì)報(bào)空指針異常
tree = leftLeftRotation(tree);
} else {
tree = leftRightRotation(tree);
}
}
} else if (cmp > 0) {
tree.right = insert(tree.right, key);//遞歸插入
if (height(tree.right) - height(tree.left) == 2) {//說(shuō)明是tree結(jié)點(diǎn)出問(wèn)題(必須是left-right橡卤，否則得負(fù)值)
if (key.compareTo(tree.right.key) < 0) {//這里如果寫(xiě)成tree.left.key會(huì)報(bào)空指針異常
tree = rightLeftRotation(tree);
} else {
tree = rightRightRotation(tree);
}
}
} else { //cmp==0;
System.out.println("添加失敯缒睢！不允許添加相同的結(jié)點(diǎn)碧库！");
}
}
tree.height = max(height(tree.left), height(tree.right)) + 1;
return tree;
}
public void insert(T key) {
mRoot = insert(mRoot, key);
}
/**
* 刪除樹(shù)中的結(jié)點(diǎn)z, 返回根節(jié)點(diǎn)
*
* @param tree 從tree結(jié)點(diǎn)開(kāi)始找尋要?jiǎng)h除的結(jié)點(diǎn)z
* @param z 待刪除的根節(jié)點(diǎn)
* @return 根節(jié)點(diǎn)
*/
private AVLTreeNode remove(AVLTreeNode tree, AVLTreeNode z) {
if (tree == null || z == null) {
return null;
}
int cmp = z.key.compareTo(tree.key);
if (cmp < 0) {//待刪除的結(jié)點(diǎn)在tree的左子樹(shù)
tree.left = remove(tree.left, z);
if (height(tree.right) - height(tree.left) == 2) {//如果刪除后tree失去平衡, 進(jìn)行調(diào)節(jié)
AVLTreeNode r = tree.right;
if (height(r.left) > height(r.right)) {
tree = rightLeftRotation(tree);
} else {
tree = rightRightRotation(tree);
}
}
} else if (cmp > 0) {//待刪除的結(jié)點(diǎn)在tree的右子樹(shù)
tree.right = remove(tree.right, z);
if (height(tree.left) - height(tree.right) == 2) {//失去平衡
AVLTreeNode l = tree.left;
if (height(l.left) < height(l.right)) {
tree = leftRightRotation(tree);
} else {
tree = leftLeftRotation(tree);
}
}
} else {//cmp==0,tree是要?jiǎng)h除的結(jié)點(diǎn)
if (tree.left != null && tree.right != null) {//tree的左右孩子非空
if (height(tree.left) > height(tree.right)) {
/*
如果tree的左子樹(shù)比右子樹(shù)高柜与，則
（1）找出tree的左子樹(shù)中的最大結(jié)點(diǎn)
（2）將該最大結(jié)點(diǎn)的值賦值給tree
(3) 刪除該最大結(jié)點(diǎn) 。
采用該方法的好處是：刪除結(jié)點(diǎn)之后谈为，AVL樹(shù)仍然是平衡的旅挤。
*/
AVLTreeNode max = maximum(tree.left);
tree.key = max.key;
tree.left = remove(tree.left, max);
} else {
/*
如果tree的右子樹(shù)比左子樹(shù)高或相等，則
（1） 找出tree的右子樹(shù)中的最小結(jié)點(diǎn)
（2） 將該最小結(jié)點(diǎn)的值賦值給tree
(3) 刪除該最大結(jié)點(diǎn)
采用該方法的好處是：刪除結(jié)點(diǎn)之后伞鲫，AVL樹(shù)仍然是平衡的粘茄。
*/
AVLTreeNode min = minimum(tree.right);
tree.key = min.key;
tree.right = remove(tree.right, min);
}
} else {
tree = (tree.left != null) ? tree.left : tree.right;
}
}
if (tree != null) {//刪除葉子結(jié)點(diǎn)的時(shí)候，這個(gè)tree是會(huì)返回null的。
tree.height = max(height(tree.left), height(tree.right)) + 1;
}
return tree;
}
public void remove(T key) {
AVLTreeNode z = search(mRoot, key);
if (z != null) {
mRoot = remove(mRoot, z);
}
}
private void preOrderPrint(AVLTreeNode root, int depth) {
if (root != null) {
System.out.println();//換行
for (int i = 0; i < depth; i++) {//for循環(huán)來(lái)打印value前的空格
System.out.print("--");//結(jié)點(diǎn)深度越大柒瓣，空格越多
}
System.out.print(root.key);
depth++;
preOrderPrint(root.left, depth);
preOrderPrint(root.right, depth);
}
}
public void print() {
preOrderPrint(mRoot, 0);
}
private AVLTreeNode search(AVLTreeNode node, T key) {
if (node == null) {
return null;
}
int cmp = key.compareTo(node.key);
if (cmp < 0) {
return search(node.left, key);
} else if (cmp > 0) {
return search(node.right, key);
} else {
return node;
}
}
private AVLTreeNode maximum(AVLTreeNode tree) {
if (tree == null) {
return null;
}
while (tree.right != null) {
tree = tree.right;
}
return tree;
}
private AVLTreeNode minimum(AVLTreeNode tree) {
if (tree == null) {
return null;
}
while (tree.left != null) {
tree = tree.left;
}
return tree;
}
public T maximum() {
AVLTreeNode p = maximum(mRoot);
if (p != null) {
return p.key;
}
return null;
}
public T minimum() {
AVLTreeNode p = minimum(mRoot);
if (p != null) {
return p.key;
}
return null;
}
}
測(cè)試：
public class Main {
public static void main(String[] args) {
AVLTree<Integer> tree = new AVLTree<>();
int arr[] = {33, 22, 4, 7, 0, 60, 13, 32, 21, 99, 6, 15, 27, 2};
for (int i = 0; i < arr.length; i++) {
tree.insert(arr[i]);
}
tree.print();
System.out.println();
System.out.println("樹(shù)的根結(jié)點(diǎn)高度：" + tree.height());
System.out.println("刪除結(jié)點(diǎn)33,32,27,60,99");
tree.remove(33);
tree.remove(32);
tree.remove(27);
tree.remove(60);
tree.remove(99);
tree.print();
System.out.println();
System.out.println("樹(shù)的根結(jié)點(diǎn)高度：" + tree.height());
}
}
打尤宕睢：
22
--7
----4
------0
--------2
------6
----15
------13
------21
--33
----32
------27
----60
------99
樹(shù)的根結(jié)點(diǎn)高度：5
99
0
刪除結(jié)點(diǎn)33,32,27,60,99
7
--4
----0
------2
----6
--15
----13
----22
------21
樹(shù)的根結(jié)點(diǎn)高度：4
