AVL树是带有平衡条件的二叉查找树，其查找和删除的时间复杂度为logn,是对二叉查找树的改进，我们将节点的左子树和右子树深度之差称为平衡因子（BF），其中的每一个节点的平衡因子的绝对值不大于1。
距离插入节点最近的，并且平衡因子绝对值大于1的节点为根的子树，称为最小不平衡子树。
要实现AVL树，就必须保证在插入的时候消除不平衡的子树，即通过某种方式，使每次插入一个节点，都是平衡的BST树，下面我们讨论一下插入的时候四种情况：
1：对左孩子的左子树进行一次插入；
2：对左孩子的右子树进行一次插入；
3：对右孩子的左子树进行一次插入；
4：对右孩子的右子树进行一次插入；
其中情况1和情况4是关于镜像对称的，情况2和情况3是关于镜像对称的，
由于图片原因，我就上了几张不好看的图片，其中x，y,z和A,B,C,D为对应的节点的孩子，我直接对四种情况进行讲解：
情况1：假设节点k1,k1的左孩子k2,
单右旋转：对k1节点的左孩子k2的左子树进行插入，这样使得k1的BF为2，此时最小不平衡子树是以k1为根节点的子树，因此对其进行右旋转操作，使得新子树的根节点为原节点的左孩子即k2，k2的右孩子为k1,k1的左孩子为原子树中k2的右孩子；
双左旋转：对以k2为根节点的子树进行插入操作，这时最小的不平衡子树是以k1为根节点的子树，但是单纯的左旋转不能解决问题，这和情况1有所区别，其原因在于K1的BF为2，而K3的BF为-1，两者的符号不一致，导致了不能只是进行一次旋转，所以分为两次旋转：
1：先对以K3为根节点的子树进行左旋转，
2：再对以K1为根节点的子树进行右旋转，
得到图中所示的结果，，此时K2左子树B是K3右子树，K2右子树C是K1左子树，K2左孩子为K3,K2右孩子为K1;
情况3：
假设节点k1,k1的右孩子k3,k3的左孩子k2,
双右旋转：对以k2为根节点的子树进行插入操作，这时最小的不平衡子树是以k1为根节点的子树，但是单纯的左旋转不能解决问题，这和情况1有所区别，其原因在于K1的BF为-2，而K3的BF为1，两者的符号不一致，导致了不能只是进行一次旋转，所以分为两次旋转：
1：先对以K3为根节点的子树进行右旋转，
2：再对以K1为根节点的子树进行左旋转，
得到图中所示的结果，此时K2右子树C是K3左子树，K2左子树B是K1右子树，K2左孩子为K1,K2右孩子为K3;
情况1：假设节点k1,k1的左孩子k2,
单右旋转：对k1节点的左孩子k2的左子树进行插入，这样使得k1的BF为2，此时最小不平衡子树是以k1为根节点的子树，因此对其进行右旋转操作，使得新子树的根节点为原节点的左孩子即k2，k2的右孩子为k1,k1的左孩子为k2的右孩子；
情况4：假设节点k1,k1的右孩子k2,
单右旋转：对k1节点的右孩子k2的左子树进行插入，这样使得k1的BF为-2，此时最小不平衡子树是以k1为根节点的子树，因此对其进行左旋转操作，使得新子树的根节点为原节点的右孩子即k2，k2的左孩子为k1,k1的左孩子为原子树中k2的左孩子；
下面是Java代码实现：
package data_structure;@SuppressWarnings("rawtypes")public class AVL<AnyType extends Comparable> {private AVLNode root;//定义范型Anytype的大小比较方法@SuppressWarnings("unused")/*private class Anytype implements Comparable<AnyType>{private AnyType x;@Overridepublic int compareTo(AnyType o) {String s=x.toString();String target=o.toString();return s.compareTo(target);}}*/private class AVLNode<AnyType>{AnyType element;AVLNode<AnyType> left;AVLNode<AnyType> right;int height;@SuppressWarnings("unused")public AVLNode(AnyType data){this(data,null,null);}public AVLNode(AnyType data,AVLNode<AnyType> lc,AVLNode<AnyType> rc){element=data;left=lc;right=rc;height=0;}}private int getHeight(AVLNode<AnyType> t){return t==null?-1:t.height;}@SuppressWarnings("unchecked")private int compare(AnyType x,AnyType y){if(x.compareTo(y)>0)return 1;else if(x.compareTo(y)<0)return -1;return 0;}//单旋转左旋转private AVLNode<AnyType> rotateWithLeftChild(AVLNode<AnyType> k1){AVLNode<AnyType> k2=k1.right;k1.right=k2.left;k2.left=k1;k2.height=Math.max(getHeight(k2.left), getHeight(k2.right))+1;k1.height=Math.max(getHeight(k1.left), getHeight(k1.right))+1;return k2;}//单旋转右旋转private AVLNode<AnyType> rotateWithRightChild(AVLNode<AnyType> k1){AVLNode<AnyType> k2=k1.left;k1.left=k2.right;k2.right=k1;k2.height=Math.max(getHeight(k2.left), getHeight(k2.right))+1;k1.height=Math.max(getHeight(k1.left), getHeight(k1.right))+1;return k2;}//双旋转左旋转，分为两个步骤：先右旋转以右孩子为根的子树，然后左旋转k1private AVLNode<AnyType> doubleWithLeftChild(AVLNode<AnyType> k1){k1.right=rotateWithRightChild(k1.right);//千万要注意k1.right不要掉了，不然k2丢了return rotateWithLeftChild(k1);}//双旋转右旋转，分为两个步骤：先左旋转以右孩子为根的子树，然后右旋转k1private AVLNode<AnyType> doubleWithRightChild(AVLNode<AnyType> k1){k1.left=rotateWithLeftChild(k1.left);//千万要注意k1.left不要掉了，不然k2丢了return rotateWithRightChild(k1);}//使用递归的方式插入，每次返回插入子树根节点，x为待插入元素@SuppressWarnings("unchecked")private AVLNode<AnyType> insert(AnyType x,AVLNode<AnyType> t){System.out.print(x+" ");if(t==null)return new AVLNode(x,null,null);int result=compare(x, t.element);if(result<0){t.left=insert(x, t.left);if(getHeight(t.left)-getHeight(t.right)==2)if(compare(x, t.left.element)<0)t=rotateWithRightChild(t);if(compare(x, t.left.element)>0)t=doubleWithRightChild(t);}if(result>0){t.right=insert(x, t.right);if(getHeight(t.right)-getHeight(t.left)==2)if(compare(x,t.right.element)>0)t=rotateWithLeftChild(t);if(compare(x,t.right.element)<0)t=doubleWithLeftChild(t);}t.height=Math.max(getHeight(t.left), getHeight(t.right))+1;return t;}@SuppressWarnings("unchecked")private void createAVl(AnyType [] data){for(AnyType a:data)root=insert(a, root);}private void printTree(AVLNode root){if(root==null)return ;printTree(root.left);System.out.print(root.element+" ");printTree(root.right);}public static void main(String []args){Integer []data={2,6,8,4,12,45,25,14,28};AVL<Integer> avl=new AVL<Integer>();avl.createAVl(data);System.out.println();avl.printTree(avl.root);}}
因为有梦，所以勇敢出发，选择出发，便只顾风雨兼程。
