1、概念： AVL树本质上还是一个二叉搜索树，不过比二叉搜索树多了一个平衡条件：每个节点的左右子树的高度差不大于1。二叉树的应用是为了弥补链表的查询效率问题，但是极端情况下，二叉搜索树会无限接近于链表，这种时候就无法体现二叉搜索树在查询时的高效率，而最初出现的解决方式就是AVL树。如下图：
2、旋转 说到AVL树就不得不提到树的旋转，旋转是AVL维持平衡的方式，主要有以下四种类型。 2.1、左左旋转 如图2-1所示，此时A节点的左树与右树的高度差为2，不符合AVL的定义，此时以B节点为轴心，AB间连线为转轴，将A节点旋转至B节点下方，由B节点的父节点变成子节点。实现所有节点的左右子树高 度差小于等于1。如图2-2。
2.2、右右旋转
右右旋转与左左旋转类似，但是动作相反，如图2-3，2-4所示，以B节点为轴心，BC间连线为轴，将C节点旋转至B下方，成为B的子节点。实现所有节点的左右子树高度差小于等于1。 
2.3、左右旋转 左右旋转稍复杂一点，需要旋转两次，如果用左左旋转的方式直接旋转图2-5中的树，会变成图2-8的样子，此时B节点的左右子树高度差依然没有平衡，所以要先对2-5的树做一步处理，就是以BC为轴， 将C节点旋转至B节点的位置，如图2-6所示，此时就将树转换成了左左旋转的场景，之后使用左左旋转即可完成平衡。
2.4、右左旋转 右左旋转与左右旋转类似，也是旋转两次。如下图，具体细节请看下面的代码详解。
3、代码实现 3.1、新增 二叉树的插入不在赘述，这里只分析插入时的平衡方法。如果新增节点没有兄弟节点时会引起树的高度变化，此时需要对上层节点的平衡值进行修改，如果出现了不平衡树，则需要调用平衡方法，代码如下：
private void balance(Node node){
Node parent = node.getParent();
Node node_middle = node;
Node node_prev = node; Boolean avl = true;
do{
if(node_middle == parent.getLeft() && (-1 <= parent.getAVL()-1 && parent.getAVL()-1 <= 1)){
//node_middle为parent的左树，此时parent左树高度+1不会造成不平衡。
parent.subAVL();
node_prev = node_middle;
node_middle = parent;
//由于上面对parent的平衡值进行了修改，如果修改后的平衡值为0，说明此时parent节点的高度没有改变，之前较短的左树高度+1，变为与右树高度相同。
if(parent != null && parent.getAVL() == 0)
parent = null;
else
parent = parent.getParent();
}else if(node_middle == parent.getRight() && (-1 <= parent.getAVL()+1 && parent.getAVL()+1 <= 1)){
//node_middle为parent的右树，此时parent右树高度+1不会造成不平衡。
parent.addAVL();
node_prev = node_middle;
node_middle = parent;
//由于上面对parent的平衡值进行了修改，如果修改后的平衡值为0，说明此时parent节点的高度没有改变，之前较短的右树高度+1，变为与左树高度相同。
if(parent != null && parent.getAVL() == 0)
parent = null;
else
parent = parent.getParent();
}else{//出现最小不平衡节点，新增时不需要考虑更高节点，所以直接中断循环，调用平衡方法
avl = false;
}
}while(parent != null && avl); if(parent == null){
return;
}
//选择相应的旋转方式
chooseCalculation(parent, node_middle, node_prev);
}
3.2、删除
删除较新增复杂一些，主要是因为存在一次旋转无法达到平衡效果的情况，而且删除本身也分为三种情况，分别是： 3.2.1、删除叶子节点 由于叶子节点没有子树，不涉及替换的问题，所以直接删除即可，如果删除节点没有兄弟节点会引起高度变化，此时依次对父级节点的平衡值做对应修改，如果出现不平衡树则要进行旋转。 3.2.2、删除节点存在一个子节点 此时将子节点上移，替换删除节点的位置，这个操作势必会造成所在子树的高度变化，所以需要依次对父级节点的平衡值做对应修该，如果出现不平衡树进行旋转操作。 3.2.3、删除节点存在两个子节点 这种情况比较复杂，由于存在两个子节点，所以不能简单的将其中一个子节点提高一级，因此需要在节点的子树中搜索一个合适的节点进行替换，之前自己构思的时候选择的是搜寻一个最长子树的最 接近删除节点的值的叶子节点，具体实现的时候发现需要考虑的场景太多，并不适合，参考算法导论上的思路后改成了搜寻左树的最大节点，此时只需考虑左树的情况即可。实现方法如下：
public void deleteNode(int item){ Node node = get(item);
if(node == null)
return;
Node parent = node.getParent();
if(!node.hasChild()){//叶子节点
if(parent == null){//删除最后节点
root = null;
return;
}
if(node.hasBrother()){//node有兄弟节点时，需要判断是否需要调用平衡方法
if(node == parent.getLeft())
isBalance(node, 1);
else
isBalance(node, -1);
parent.deleteChildNode(node);
}else{//node没有兄弟节点时，高度减一，需要进行平衡
deleteAvl(node);
parent.deleteChildNode(node);
}
}else if(node.getLeft() != null && node.getRight() == null){//有一个子节点时，将子节点上移一位，然后进行平衡即可
if(parent == null){//删除的是根节点
root = node;
return;
}
if(node == parent.getLeft()){
parent.setLeft(node.getLeft());
}else{
parent.setRight(node.getLeft());
}
node.getLeft().setParent(parent);
deleteAvl(node.getLeft());
}else if(node.getLeft() == null && node.getRight() != null){//有一个子节点时，将子节点上移一位，然后进行平衡即可
if(parent == null){//删除的是根节点
root = node;
return;
}
if(node == parent.getRight()){
parent.setRight(node.getRight());
}else{
parent.setLeft(node.getRight());
}
node.getRight().setParent(parent);
deleteAvl(node.getRight());
}
else{//有两个子节点时，先在节点左树寻找最大节点last，然后删除last，最后将被删除节点的value替换为last的value
Node last = findLastNode(node);
int tmp = last.getValue();
deleteNode(last.getValue());
node.setValue(tmp);
}
node = null;//GC
}
3.3、旋转 3.3.1、左左旋转
private void LeftLeftRotate(Node node){ Node parent = node.getParent(); if(parent.getParent() != null && parent == parent.getParent().getLeft()){
node.setParent(parent.getParent());
parent.getParent().setLeft(node);
}else if(parent.getParent() != null && parent == parent.getParent().getRight()){
node.setParent(parent.getParent());
parent.getParent().setRight(node);
}else{
root = node;
node.setParent(null);
}
parent.setParent(node);
parent.setLeft(node.getRight());
if(node.getRight() != null)
node.getRight().setParent(parent);
node.setRight(parent); if(node.getAVL() == -1){//只有左节点时，parent转换后没有子节点
parent.setAVL(0);
node.setAVL(0);
}else if(node.getAVL() == 0){//node有两个子节点，转换后parent有一个左节点
parent.setAVL(-1);
node.setAVL(1);
}//node.getAVL()为1时会调用左右旋转
}
3.3.2、右右旋转
private void RightRightRotate(Node node){ Node parent = node.getParent(); if(parent.getParent() != null && parent == parent.getParent().getLeft()){
node.setParent(parent.getParent());
parent.getParent().setLeft(node);
}else if(parent.getParent() != null && parent == parent.getParent().getRight()){
node.setParent(parent.getParent());
parent.getParent().setRight(node);
}else{
root = node;
node.setParent(null);
}
parent.setParent(node);
parent.setRight(node.getLeft());
if(node.getLeft() != null)
node.getLeft().setParent(parent);
node.setLeft(parent); if(node.getAVL() == 1){
node.setAVL(0);
parent.setAVL(0);
}else if(node.getAVL() == 0){//当node有两个节点时，转换后层数不会更改，左树比右树高1层，parent的右树比左树高一层
parent.setAVL(1);
node.setAVL(-1);
}
}
3.3.3、左右旋转
private void LeftRightRotate(Node node){ Node parent = node.getParent();
Node child = node.getRight(); //左右旋转时node的avl必为1，所以只需考虑child的avl
if(!child.hasChild()){
node.setAVL(0);
parent.setAVL(0);
}else if(child.getAVL() == -1){
node.setAVL(0);
parent.setAVL(1);
}else if(child.getAVL() == 1){
node.setAVL(-1);
parent.setAVL(0);
}else if(child.getAVL() == 0){
node.setAVL(0);
parent.setAVL(0);
}
child.setAVL(0); //第一次交换
parent.setLeft(child);
node.setParent(child);
node.setRight(child.getLeft());
if(child.getLeft() != null)
child.getLeft().setParent(node);
child.setLeft(node);
child.setParent(parent); //第二次交换
if(parent.getParent() != null && parent == parent.getParent().getLeft()){
child.setParent(parent.getParent());
parent.getParent().setLeft(child);
}else if(parent.getParent() != null && parent == parent.getParent().getRight()){
child.setParent(parent.getParent());
parent.getParent().setRight(child);
}else{
root = child;
child.setParent(null);
}
parent.setParent(child);
parent.setLeft(child.getRight());
if(child.getRight() != null)
child.getRight().setParent(parent);
child.setRight(parent);
}
3.3.4、右左旋转
private void RightLeftRotate(Node node){ Node parent = node.getParent();
Node child = node.getLeft(); if(!child.hasChild()){
node.setAVL(0);
parent.setAVL(0);
}else if(child.getAVL() == -1){
node.setAVL(1);
parent.setAVL(0);
}else if(child.getAVL() == 1){
node.setAVL(0);
parent.setAVL(-1);
}else if(child.getAVL() == 0){
parent.setAVL(0);
node.setAVL(0);
}
child.setAVL(0); //第一次交换
parent.setRight(child);
node.setParent(child);
node.setLeft(child.getRight());
if(child.getRight() != null)
child.getRight().setParent(node);
child.setRight(node);
child.setParent(parent); //第二次交换
if(parent.getParent() != null && parent == parent.getParent().getLeft()){
child.setParent(parent.getParent());
parent.getParent().setLeft(child);
}else if(parent.getParent() != null && parent == parent.getParent().getRight()){
child.setParent(parent.getParent());
parent.getParent().setRight(child);
}else{
root = child;
child.setParent(null);
}
parent.setParent(child);
parent.setRight(child.getLeft());
if(child.getLeft() != null)
child.getLeft().setParent(parent);
child.setLeft(parent);
}
完整代码github地址：https://github.com/ziyuanjg/AVLTree
