一个AVL树是其每个节点的左子树和右子树的高度差最多差1的二叉查找树；AVL树是一种最古老的平衡查找树
上代码：
package com.itany.avlshu;public class AVLTree<T extends Comparable<?super T>>{private static class AvlNode<T>{private int height;private T element;private AvlNode<T> left;private AvlNode<T> right;public AvlNode(T element){this(element,null,null);}public AvlNode(T element,AvlNode<T> left,AvlNode right){this.element=element;this.left=left;this.right=right;height=0;}}private int height(AvlNode<T> node){return (node==null)?-1:node.height;}private int compare(T x, T element){return x.compareTo(element);}private AvlNode<T> insert(T x,AvlNode<T> t){if(t==null)return new AvlNode<T>(x,null,null);//创造出来时 默认height=0int compareResult=compare(x,t.element);if(compareResult<0){t.left=insert(x,t.left);//做完了插入之后 立马比较t的左右儿子的高度差是否等于2 若是 则进行相应旋转 若不是那么下一步 直接更新这个t的height值//此时左边儿子高度比较大if(height(t.left)-height(t.right)==2){//下面分两种旋转情况 一种是单旋转 另一种是双旋转if(compare(x,t.left.element)<0)t=rotateWithLeftChild(t);elset=doubleRotateWithLeftChild(t);}}else if(compareResult>0){t.right=insert(x,t.right);//做完了插入之后 立马比较t的左右儿子的高度差是否等于2 若是 则进行相应旋转 若不是那么下一步 直接更新这个t的height值//此时右边儿子高度比较大if(height(t.right)-height(t.left)==2){//下面分两种旋转情况 一种是单旋转 另一种是双旋转if(compare(x,t.right.element)<0)t=doubleRotateWithRightChild(t);elset=rotateWithRightChild(t);}}else;t.height=Math.max(height(t.left), height(t.right))+1;//+1是加一个自己return t;}private AvlNode<T> rotateWithRightChild(AvlNode<T> k1){AvlNode<T> k2=k1.right;k1.right=k2.left;k2.left=k1;k2.height=Math.max(height(k2.left),height(k2.right))+1;k1.height=Math.max(height(k1.left),height(k1.right))+1;return k2;}private AvlNode<T> doubleRotateWithRightChild(AvlNode<T> k3){k3.right=rotateWithLeftChild(k3.right);return rotateWithRightChild(k3);}//双旋转是由两次单旋转得来private AvlNode<T> doubleRotateWithLeftChild(AvlNode<T> k3){k3.left=rotateWithRightChild(k3.left);return rotateWithLeftChild(k3);}private AvlNode<T> rotateWithLeftChild(AvlNode<T> k2){AvlNode<T> k1=k2.left;k2.left=k1.right;k1.right=k2;k2.height=Math.max(height(k2.left),height(k2.right))+1;k1.height=Math.max(height(k1.left),height(k1.right))+1;return k1;}}
，夫妇一条心，泥土变黄金。
