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;
@Override
public 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;
}
//双旋转左旋转，分为两个步骤：先右旋转以右孩子为根的子树，然后左旋转k1
private AVLNode<AnyType> doubleWithLeftChild(AVLNode<AnyType> k1){
k1.right=rotateWithRightChild(k1.right);//千万要注意k1.right不要掉了，不然k2丢了
return rotateWithLeftChild(k1);
}
//双旋转右旋转，分为两个步骤：先左旋转以右孩子为根的子树，然后右旋转k1
private 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);
}
}
