Running AVL Tree Tester…. Only left rotations have been implemented

c:\Program Files\Java\jdk1.6.0_03\bin>java AVLTreeTest

enter an int 999 to quit

165

build new root... value is 165

enter an int 999 to quit

140

not found:140 must insert

build new node on left of165 for value 140

140 inserted on left of165

enter an int 999 to quit

100

not found:100 must insert

build new node on left of140 for value 100

100 inserted on left of165

inserted on left of165 tree is unbalanced

LL rotate

enter an int 999 to quit

25

not found:25 must insert

build new node on left of100 for value 25

25 inserted on left of140

enter an int 999 to quit

40

not found:40 must insert

build new node on right of25 for value 40

40 inserted on left of100

inserted on left of100 tree is unbalanced

LR rotate

enter an int 999 to quit

//tester

import java.util.*;

public class AVLTreeTester{

public static void main(String args[]){

AVLTree tree=new AVLTree();

Scanner s=new Scanner(System.in);

System.out.println("enter an int 999 to quit");

int data=s.nextInt();

while(data!=999){

tree.add(data);

System.out.println("enter an int 999 to quit");

data=s.nextInt();

}//while

}//main

}//class

//AVLTree

public class AVLTree{

private AVLNode root;

protected class AVLNode{

int data;

AVLNode parent, left,right;

int bf;

public AVLNode(int x,AVLNode y){

data=x;

parent=y;

left=right=null;

bf=0;

}}

public boolean add(int x){

AVLNode a,b,y;

boolean found,unbal;

if(root==null){

root=new AVLNode(x,null);

System.out.println("build new root... value is "+ x);

return true;}

else{//else not root

found=false;//assume not there

AVLNode p,q,f;

int d;

p=a=root;q=f=null;

while(p!=null &&!found)

{

if(p.bf!=0){a=p;f=q;}//a is last node ==+/-1 and f is a's parent

// int v=(Comparable)x.compareTo(p.data);

q=p;

if(x<p.data)

p=p.left;

else if(x>p.data)p=p.right;

else {y=p;found=true;}

}//not found loop

if(!found)//insert node and rebalance tree...x is child of q

{ System.out.println("not found:"+ x+ " must insert");

if(x<q.data){y=q.left=new AVLNode(x,q);System.out.println("build new node on left of" +q.data+" for value "+ x);}

else {y=q.right=new AVLNode(x,q); System.out.println("build new node on right of" +q.data+" for value "+ x);}

//adjust bfs from a on down to q to be +/-1

//d will indicate if x is left or rt subtree of a

if(x>a.data){p=a.right;b=p;d=-1;System.out.println(x+ " inserted on right of" +a.data);}

else {p=a.left;b=p;d=1;System.out.println(x+ " inserted on left of" +a.data);}

while(p!=y)

if(x>p.data){p.bf=-1;p=p.right;}

else {p.bf=1;p=p.left;}

unbal=true;//assume not balanced

if(a.bf==0||a.bf+d==0)//then still balanced

{a.bf+=d;unbal=false;}

if(unbal){System.out.println(" inserted on left of" +a.data+ " tree is unbalanced");

if(d==1){//left fix needed

if(b.bf==1){//it is LL

System.out.println("LL rotate");

a.left=b.right;

b.right=a;

a.bf=0;

b.bf=0;}//end LL

else {//it is LR

System.out.println("LR rotate");

AVLNode c=b.right;

b.right=c.left;

a.left=c.right;

c.left=b;

c.right=a;

//need to fix BFs before we continue

switch(c.bf)

{

case 1://LR(b)

a.bf=-1;

b.bf=0;break;

case -1://LR(c)

b.bf=1;

a.bf=0;

break;

case 0://LR(a)

b.bf=0;

a.bf=0;

}//switch

c.bf=0;

b=c;}//end LR

}//end d==1

else{//Right side is symmetric...d==-1

//...handle RR and RL

}

if (a.parent==null)root=b;

else if(a==a.parent.left)f.left=b;

else if(a==a.parent.right)f.right=b;

}

return true;//was added

}

return false;}

//add

}//not root

}//class