AVL 树 Java 代码

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(t.data<s&&insert(t.rChild,t,1,s)){
    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(t.data<s){
   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];
    IO.p.print("<"+n2.data+","+n2.bf+">   ");
    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(){
}
}