一个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=0
int 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);
else
t=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);
else
t=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;
}
}