AVL 树 Java 代码

2016-08-01 11:25:10 暂无评论阳光倾城算法与数据结构 678

AVL 树 java 代码

public class AVLTree{
int count;
int[] datas;
Node tree;
int tall;
int low;
private void lRotate(Node t){
Node p=t.rChild;
int temp=p.data;
p.data=t.data;
t.data=temp;
t.rChild=p.rChild;
p.rChild=p.lChild;
p.lChild=t.lChild;
t.lChild=p;
}
private void rRotate(Node t){
Node p=t.lChild;
int temp=t.data;
t.data=p.data;
p.data=temp;
t.lChild=p.lChild;
p.lChild=p.rChild;
p.rChild=t.rChild;
t.rChild=p;
}
public boolean insert(int s){
Node p=new Node();
p.rChild=this.tree;
boolean bool=insert(this.tree,p,1,s);
this.tree=p.rChild;
return bool;
}
private boolean insert(Node t,Node p,int d,int s){
if(t==null){
   switch(d){
    case 0:p.lChild=new Node(s);break;
    case 1:p.rChild=new Node(s);break;
   }
   tall=1;return true;
}else{
   if(t.data==s) {tall=0;return false;}
   if(t.data>s&&insert(t.lChild,t,0,s)){
    if(tall==1){
     switch(t.bf){
      case 0: tall=1;t.bf=1;break;
      case 1: tall=0;leftBalance(t);
      case -1:tall=0;t.bf=0;break;
     }
    }
    return true;
   }

    if(tall==1){
     switch(t.bf){
      case 0: tall=1;t.bf=-1;break;
      case 1: tall=0;t.bf=0;
      case -1:tall=0;rightBalance(t);
     }
    }
    return true;
   }
   return false;
}
}
private void leftBalance(Node t){
Node p1=t.lChild;
switch(p1.bf){
   case 1:rRotate(t);t.bf=0;t.rChild.bf=0;break;
   case -1: int tt=p1.rChild.bf;
            lRotate(p1);rRotate(t);t.bf=0;
            switch(tt){
       case 0:t.lChild.bf=t.rChild.bf=0;break;
       case 1:t.lChild.bf=0;t.rChild.bf=-1;break;
       case -1:t.lChild.bf=1;t.rChild.bf=0;break;
      }
}
}
private void rightBalance(Node t){
Node p1=t.rChild;
switch(p1.bf){
   case -1:lRotate(t);t.bf=0;t.lChild.bf=0;break;
   case 1: int tt=p1.lChild.bf;
            rRotate(p1);lRotate(t);t.bf=0;
            switch(tt){
       case 0:t.lChild.bf=t.rChild.bf=0;break;
       case 1:t.lChild.bf=0;t.rChild.bf=-1;break;
       case -1:t.lChild.bf=1;t.rChild.bf=0;break;
      }
}
}
public void gShow(){
IO.p.println("This tree's view is:");
Node[] n=new Node[100];
int[] is=new int[100];
int top=0;
if(this.tree!=null)
n[top++]=this.tree;
while(top>0){
   switch(is[top-1]){
    case 0: IO.p.println(bank(top)+n[top-1].data);is[top-1]++;
            if(n[top-1].lChild!=null){n[top]=n[top-1].lChild;top++;}break;
    case 1: is[top-1]++;if(n[top-1].rChild!=null){n[top]=n[top-1].rChild;top++;}break;
    case 2: is[--top]=0;
   }
}
}
private String bank(int i){
String s="";
while(i>1){s+=".";i--;}
return s;
}
public boolean delete(int s){
Node p=new Node();p.rChild=this.tree;
boolean bool=delete(this.tree,p,1,s);
this.tree=p.rChild;
return bool;
}
private boolean delete(Node t,Node p,int d,int s){
if(t==null) {low=0;return false;}
if(t.data==s){
   if(t.lChild!=null&&t.rChild!=null){
    Node t1=t.lChild;
    while(t1.rChild!=null){t1=t1.rChild;}
    int temp=t.data;
    t.data=t1.data;
    t1.data=temp;
    delete(t.lChild,t,0,s);
    if(low==1){
      switch(t.bf){
     case 0:t.bf=-1;low=0;break;
     case 1:t.bf=0;low=1;break;
     case -1:low=1;rightBalance(t);
      }
       }
   }else{
    Node t0=null;
       if(t.lChild==null)t0=t.rChild;
       if(t.rChild==null)t0=t.lChild;
       switch(d){
        case 0:p.lChild=t0;break;
        case 1:p.rChild=t0;break;
       }
       low=1;
   }
   return true;
}
if(t.data>s){
   if(!delete(t.lChild,t,0,s)) return false;
   if(low==1){
    switch(t.bf){
     case 0:t.bf=-1;low=0;break;
     case 1:t.bf=0;low=1;break;
     case -1:low=1;rightBalance(t);
    }
   }
}

   if(!delete(t.rChild,t,1,s)) return false;
   if(low==1){
    switch(t.bf){
     case 0: t.bf=1;low=0;break;
     case -1:t.bf=0;low=1;break;
     case 1:low=1;leftBalance(t);
    }
   }
}
return false;
}
public void show(){
     IO.p.print("The tree's natural order is: ");
Node[] stack=new Node[100];
int top=0;
stack[top++]=this.tree;
while(top>0){
   Node n1;
   while((n1=stack[top-1])!=null) stack[top++]=n1.lChild;
   top--;
   if(top>0){
    Node n2=stack[--top];

    stack[top++]=n2.rChild;
   }
}
IO.p.println();
}
public static void main(String[] args){
AVLTree avl=new AVLTree();
IO.p.print("Input the datas one by one and split by space:");
int[] is=IO.readInts();
for(int i:is) avl.insert(i);
avl.show();
avl.gShow();
IO.p.print("The delete data:");
is=IO.readInts();
while(is[0]!=0){
   for(int i:is) avl.delete(i);
      avl.show();
      avl.gShow();
      IO.p.print("The delete data:");
      is=IO.readInts();
}
}
}
class Node{
int data;
Node lChild;
Node rChild;
int bf;
Node(int data){
this.data=data;
}
Node(){
}
}