- 定义
在计算机科学中，AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。
在之前的二分搜索树中，有一个很大的问题，如果我们添加节点的顺序是有序的，那么树将会退化成链表，导致失去了树的优势，查询的时间复杂度变为了 O(n)。平衡二叉树的出现解决了这种问题，它是一种在添加节点时可以自平衡的二叉树。
平衡二叉树的高度和节点数量之间的关系是O(logN)的。根据平衡二叉树的性质，左右子树的高度差不能超过一，所以需要跟踪每一个节点高度，以求出当前节点的平衡因子，然后通过旋转重新平衡当前树，我们可以在二叉搜索树的基础上增加一个属性height，如下:
class Node{
E e;
int height;
Node left, right;
}
- 基本使用
由于AVL树和之前的二分搜索树类似，所以我们可以直接使用之前的代码，然后将其改造。首先我们添加节点时，我们要更新该节点和其父节点的高度，然后计算平衡因子（左子树高度减去右子树高度），如果平衡因子的绝对值大于一，表示当前的树已经出现 "倾斜"，所以我们必须通过树左旋和右旋完成树的重新平衡。
在添加节点之后，如果出现不平衡，那肯定出现在新节点的祖先节点中。所以我们加入节点之后，沿着节点向上维护平衡性。
（1）LL（右旋转）
当插入的元素在不平衡节点左侧的左侧时，可以通过右旋转来重新维护平衡，具体流程如下:
右旋
private Node rightRotate(Node root){
Node newRoot = root.left;
root.left = newRoot.right;
newRoot.right = root;
root.height = Math.max(getHeight(root.left) , getHeight(root.right)) + 1;
newRoot.height = Math.max(getHeight(newRoot.left), getHeight(newRoot.right)) + 1;
return newRoot;
}
（2）RR（左旋转）
当插入的元素在不平衡节点右侧的右侧时，可以通过右旋转来重新维护平衡（和右旋镜像）。
/*
* 当插入的节点在不平很节点右侧的右侧，进行左旋转
* y x
* / \ / \
* t4 x y z
* / \ ==> x.left = y; y.right = t3; / \ / \
* t3 z t4 t3 t2 t1
* / \
* t2 t1
* */
private Node leftRotate(Node root){
Node newRoot = root.right;
if(newRoot != null) root.right = newRoot.left;
newRoot.left = root;
root.height = Math.max(getHeight(root.left) , getHeight(root.right)) + 1;
newRoot.height = Math.max(getHeight(newRoot.left), getHeight(newRoot.right)) + 1;
return newRoot;
}
（3）LR
当插入的元素在不平衡节点左侧的右侧时，先对左侧的子节点进行左旋，然后在对当前节点右旋，具体流程如下：
lr
（4）RL
当插入的元素在不平衡节点的右侧的左侧时，先对右侧的节点进行右旋，然后在对当前的节点左旋，具体流程如下:
rl
（5）添加和删除节点（详细代码略）
// 左节点的高度减去右节点的高度
int balanceFactor = getBanlanceFactor(root);
//当插入的节点在不平衡节点左侧的左侧，要进行右旋
if(getBanlanceFactor(root) > 1 && getBanlanceFactor(root.left) >= 0){
return rightRotate(root);
}
//当插入的节点在不平衡节点右侧的右侧，要进行左旋
if(getBanlanceFactor(root) < -1 && getBanlanceFactor(root.right) <= 0){
return leftRotate(root);
}
//lr
if(getBanlanceFactor(root) > 1 && getBanlanceFactor(root.left) < 0){
return rightLeftRotate(root);
}
//rl
if(getBanlanceFactor(root) < -1 && getBanlanceFactor(root.right) > 0){
return leftRightRotate(root);
}
