平衡二叉树定义
AVL树也就是所谓的平衡二叉树，查找、删除、插入最坏情况下为O(log n)，维持树的平衡只需要几次旋转即可。保证任意一个节点的左子树高度与右子树高度相差不大于1，默认树为空时高度为0。
节点结构
为了后续操作简洁性，先给出节点结构
final class node{
int value=0;//键值
int height=1;//节点高度
node left=null;//左右孩子
node right=null;
node(int value){
this.value=value;
}
}
旋转类型
维持平衡的操作就是树的旋转，旋转类型可以分为四种：
1.右旋LL类型
单个右旋，将k1的右子树作为k2的左子树，k2作为k1的右子树。该操作只是对于k1，k2进行，所以X,Y,X子树的高度不变，在旋转完成后，只需更新k1,k2高度即可
node l_l_rotate(node root){//LL旋转
node temp=root.left;//将左节点拿出来
root.left=temp.right;
temp.right=root;
root.height=Math.max(get_height(root.left),get_height(root.right))+1;//更新原root的height
root=temp;
root.height=Math.max(get_height(root.left),get_height(root.right))+1;//更新新root的height
return root;
}
简单说就是，将节点的左节点的右子树作为节点的左子树，节点作为其原来左节点的右子树。
2.左旋RR性
跟右转刚好反过来，k2的左子树作为k1的右子树，k1作为k2的左子树。跟上面一样，更改完成后，更新k1，k2的高度即可
node r_r_rotate(node root){//RR旋转
node temp=root.right;//将右节点拿出来
root.right=temp.left;
temp.left=root;
root.height=Math.max(get_height(root.left),get_height(root.right))+1;//更新原root的height
root=temp;
root.height=Math.max(get_height(root.left),get_height(root.right))+1;//更新新root的height
return root;
}
节点的右节点的左子树作为节点的右子树，节点作为其原来右节点的左子树。
3.先左旋再右旋LR
两次操作而已，k1,k2执行RR旋转，然后对k3执行LL右旋操作。
node l_r_rotate(node root){//LR旋转
root.left=r_r_rotate(root.left);//先RR旋转
return l_l_rotate(root);//再LL旋转
}
4.先右旋再左旋RL
先对k3,k2执行LL右旋，再对k1执行RR左旋操作。
node r_l_rotate(node root){//RL旋转
root.right=l_l_rotate(root.right);//先LL旋转
return r_r_rotate(root);//再LL旋转
}
（用LL表示右旋操作，是因为LL表示的是结构上是个“左边形”，所以要向右旋转）
判断旋转操作
node check(node root){//检查高度，判断是否需要旋转操作
root.height=(Math.max(get_height(root.left),get_height(root.right))+1);//更新节点高度
if(get_height(root.left)-get_height(root.right)==2){//左边增高了
if(get_height(root.left.left)>=get_height(root.left.right)){//LL型
root=l_l_rotate(root);//LL旋转
}else{//LR型
root=l_r_rotate(root);//LR旋转
}
}else if(get_height(root.right)-get_height(root.left)==2){//右边增高了
if(get_height(root.right.left)>get_height(root.right.right)){//RL型
root=r_l_rotate(root);//RL旋转
}else{//RR型
root=r_r_rotate(root);//RR旋转
}
}
return root;
}
判断很简单，在插入或者删除操作之后，在从根节点到操作的（插入或删除）的那个节点的这条路径上，更新该路径上的节点的高度，并判断是否需要旋转操作来维持平衡。
插入节点操作
从根节点开始到插入位置的这条路径上，在插入节点操作完成之后之后，需要依次从下（插入节点）向上，更新每个该路径上的节点的高度（height属性）信息，借助上面的check函数，在需要旋转的情况下判断条件，进行旋转操作。
由此可知，插入操作需要以递归函数的方式进行。原因如下：
1.建立新插入的节点与原有节点（父节点）之间的引用关系
例如，待插入节点的value值小于root节点时：root.left=insert(root.left,value);将新建立的节点作为其父节点的左子节点，建立联系。
2.回退时更新父节点的高度（height属性）信息
在完成最底层，带插入位置的插入操作之后，即root.left=new node(value);进行root节点的高度更新
参考代码：
node insert(node root,int value){//插入节点
if(root==null){//找到插入位置
node t=new node(value);//创建该节点
return t;
}
if(root.value==value){//相等就算了，不过此处没有优化，相等的节点上层仍需要check检查
System.out.println("already exists");
return root;
}
if(value<root.value){//左子树上创建节点
root.left=insert(root.left,value);
}else{//右子树上创建节点
root.right=insert(root.right,value);
}
root=check(root);//检查高度，判断是否需要旋转操作
return root;
}
删除节点操作
删除节点有两个情况
1.待删除的节点具有左子树和右子树
这种情况下待删除的节点可以看做是个官二代，要把他删除了，但有权有势的人家直接找了个替罪羊，自己改个名字照样活的自在。真实情况应该是，将节点删除，在其左子树和右子树中，选择较高的一个子树的极值，放于删除节点出，无图无真相
要删除节点5，则在节点5左子树和右子树中选择较高的一个，这里一样高就随便选了，比如选择右子树，则选择右子树的最小值，即6，放到节点5的位置上；如果选择左子树，则选择最大值，即3，放到5的位置上。然后删除选择的6或者3节点。所以可以看出来，这操作其实根本就不是删除5，而是删除左子树的最大值或者右子树的最小值，5节点一直存在，不过就是换个value值而已，对象不变。
这样的好处，一个是操作简单，不用创建新对象，直接在原对象上修改即可，另外就是可以在删除操作中维持二叉树的平衡，不需要进行旋转操作（当然更新高度还是要有的）
2.待删除的节点不同时具有左子树和右子树
当然不可能每个节点都是官二代，待删除的节点可能是叶子节点或者只有一个子树不为空的节点，此时就需要放弃节点对象了。
删除操作仍然是以递归的形式进行的，原理相同，从根到待删除的节点，在该影响路径上，由下向上依次递归更新。在从根节点找到官二代节点的情形中，同样如此，不过就是换个方向继续向下而已，所以方式一致。
参考代码：
node delete(node root,int value){//根据值来删除节点
if(root==null){//即使没找到也会check检查height
System.out.println("not found");
return null;
}
if(value<root.value){//左子树上去找
root.left=delete(root.left,value);
}else if(value>root.value){//右子树上去找
root.right=delete(root.right,value);
}else{//找到了
if(root.left!=null&&root.right!=null){//左右都不等于null，删除之后仍然平衡
if(root.left.height>root.right.height){//只是需要更新height
root.value=max(root.left);//取左子树最大值
root.left=delete(root.left,root.value);//删除该最大值
}else{
root.value=min(root.right);//取右子树最小值
root.right=delete(root.right,root.value);//删除该最小值
}
}else{//左右子树部分或者全部为null
root=(root.left!=null?root.left:root.right);
return root;
}
}
root=check(root);
return root;
}
参考示例：
建立平衡二叉树：1,2,3,7,8,9,4,5,6
删除：4,6
插入3节点时，RR旋转
插入8节点时，RR旋转
插入9节点，RR旋转
添加6节点后，RR左旋
删除4,6操作
删除6节点，LL右旋
参考代码：
public class t{
public static void main(String[] args){
int[] arr=new int[]{1,2,3,7,8,9,4,5,6};
tree tr=new tree();
for(int i:arr){
tr.insert(i);
}
tr.delete(4);
tr.delete(6);
tree.pre_show(tr);
}
}
final class node{
int value=0;//键值
int height=1;//节点高度
node left=null;//左右孩子
node right=null;
node(int value){
this.value=value;
}
}
final class tree{
node root=null;
tree(){}
void insert(int value){
if(root==null){
root=new node(value);
}else{
root=insert(root,value);
}
}
node insert(node root,int value){//插入节点
if(root==null){//找到插入位置
node t=new node(value);//创建该节点
return t;
}
if(root.value==value){//相等就算了，不过此处没有优化，相等的节点上层仍需要check检查
System.out.println("already exists");
return root;
}
if(value<root.value){//左子树上创建节点
root.left=insert(root.left,value);
}else{//右子树上创建节点
root.right=insert(root.right,value);
}
root=check(root);//检查高度，判断是否需要旋转操作
return root;
}
int get_height(node t){//节点高度，空树高度为0
return t==null?0:t.height;
}
node check(node root){//检查高度，判断是否需要旋转操作
root.height=(Math.max(get_height(root.left),get_height(root.right))+1);//更新节点高度
if(get_height(root.left)-get_height(root.right)==2){//左边增高了
if(get_height(root.left.left)>=get_height(root.left.right)){//LL型
root=l_l_rotate(root);//LL旋转
}else{//LR型
root=l_r_rotate(root);//LR旋转
}
}else if(get_height(root.right)-get_height(root.left)==2){//右边增高了
if(get_height(root.right.left)>get_height(root.right.right)){//RL型
root=r_l_rotate(root);//RL旋转
}else{//RR型
root=r_r_rotate(root);//RR旋转
}
}
return root;
}
void delete(int value){
root=delete(root,value);
}
node delete(node root,int value){//根据值来删除节点
if(root==null){//即使没找到也会check检查height
System.out.println("not found");
return null;
}
if(value<root.value){//左子树上去找
root.left=delete(root.left,value);
}else if(value>root.value){//右子树上去找
root.right=delete(root.right,value);
}else{//找到了
if(root.left!=null&&root.right!=null){//左右都不等于null，删除之后仍然平衡
if(root.left.height>root.right.height){//只是需要更新height
root.value=max(root.left);//取左子树最大值
root.left=delete(root.left,root.value);//删除该最大值
}else{
root.value=min(root.right);//取右子树最小值
root.right=delete(root.right,root.value);//删除该最小值
}
}else{//左右子树部分或者全部为null
root=(root.left!=null?root.left:root.right);
return root;
}
}
root=check(root);
return root;
}
int max(node root){
if(root==null){
System.out.println("search and not found");
return -1;
}
while(root.right!=null){
root=root.right;
}
return root.value;
}
int min(node root){
if(root==null){
System.out.println("search and not found");
return -1;
}
while(root.left!=null){
root=root.left;
}
return root.value;
}
node l_l_rotate(node root){//LL旋转
node temp=root.left;//将左节点拿出来
root.left=temp.right;
temp.right=root;
root.height=Math.max(get_height(root.left),get_height(root.right))+1;//更新原root的height
root=temp;
root.height=Math.max(get_height(root.left),get_height(root.right))+1;//更新新root的height
return root;
}
node r_r_rotate(node root){//RR旋转
node temp=root.right;//将右节点拿出来
root.right=temp.left;
temp.left=root;
root.height=Math.max(get_height(root.left),get_height(root.right))+1;//更新原root的height
root=temp;
root.height=Math.max(get_height(root.left),get_height(root.right))+1;//更新新root的height
return root;
}
node l_r_rotate(node root){//LR旋转
root.left=r_r_rotate(root.left);//先RR旋转
return l_l_rotate(root);//再LL旋转
}
node r_l_rotate(node root){//RL旋转
root.right=l_l_rotate(root.right);//先LL旋转
return r_r_rotate(root);//再LL旋转
}
static void pre_show(tree tr){//前序遍历树
pre_show(tr.root);
}
static void pre_show(node root){//前序遍历树
if(root!=null){
System.out.println("value:"+root.value+",height:"+root.height);
pre_show(root.left);
pre_show(root.right);
}
}
}
结果：
E:\>java t value:7,height:4 value:2,height:3 value:1,height:1 value:5,height:2 value:3,height:1 value:8,height:2 value:9,height:1
总结
平衡二叉树提供复杂度为O(Log n)的查询、修改操作，通过对树的旋转来保持树的平衡性质。
参考：http://www.cnblogs.com/skywang12345/p/3576969.html#top