Complete implementation only without the delete method ... If anyone wants it i will post it later in the comments :
import java.io.*;
class Node
{
int data;
Node leftchild;
Node rightchild;
Node parent;
public Node(int d)
{
data=d;
leftchild=null;
rightchild=null;
}
public int get_data()
{
return data;
}
public Node get_leftchild()
{
return leftchild;
}
public Node get_rightchild()
{
return rightchild;
}
public void set_data(int d)
{
data=d;
}
public void set_leftchild(Node n)
{
leftchild=n;
}
public void set_rightchild(Node n)
{
rightchild=n;
}
public void set_parent(Node n)
{
parent=n;
}
public Node get_parent()
{
return parent;
}
}
//end of the node class
//start
class Avl
{
Node root;
public Avl()
{
root=null;
}
public int max(int a,int b)
{
if(a>b)
return a;
else
return b;
}
public int get_height(Node n)
{
if(n==null)
return 0;
else
return max(get_height(n.get_leftchild()),get_height(n.get_rightchild()))+1;
}
public void left_left_rot(Node k2)
{
Node k1=k2.get_leftchild();
Node B=k1.get_rightchild();
Node gp=k2.get_parent();
if(gp!=null)
{
if(gp.get_rightchild()==k2)
{
gp.set_rightchild(k1);
k1.set_parent(gp);
}
else
{
gp.set_leftchild(k1);
k1.set_parent(gp);
}
}
else
{
k1.set_parent(null);
}
k1.set_rightchild(k2);
if(k1!=null)
k2.set_parent(k1);
k2.set_leftchild(B);
if(B!=null)
B.set_parent(k2);
}
public void right_right_rot(Node x)
{
Node y=x.get_rightchild();
Node B=y.get_leftchild();
Node gp=x.get_parent();
if(gp.get_rightchild()==x)
{
gp.set_rightchild(y);
y.set_parent(gp);
}
else
{
gp.set_leftchild(y);
y.set_parent(gp);
}
y.set_leftchild(x);
x.set_parent(y);
x.set_rightchild(B);
if(B!=null)
B.set_parent(x);
}
public void left_right_rot(Node k3)
{
Node k1=k3.get_leftchild();
Node k2=k1.get_rightchild();
Node B=k2.get_leftchild();
Node C=k2.get_rightchild();
Node par=k3.get_parent();
if(par.get_leftchild()==k3)
par.set_leftchild(k2);
else
par.set_rightchild(k2);
if(k2!=null)
k2.set_parent(par);
k2.set_leftchild(k1);
if(k1!=null)
k1.set_parent(k2);
k2.set_rightchild(k3);
if(k3!=null)
k3.set_parent(k2);
k1.set_rightchild(B);
k3.set_leftchild(C);
if(B!=null)
B.set_parent(k1);
if(C!=null)
C.set_parent(k3);
}
public void right_left_rot(Node k1)
{
Node k3=k1.get_rightchild();
Node k2=k3.get_leftchild();
Node C=k2.get_rightchild();
Node B=k2.get_leftchild();
Node par=k1.get_parent();
if(par.get_leftchild()==k1)
par.set_leftchild(k2);
else
par.set_rightchild(k2);
if(k2!=null)
k2.set_parent(par);
k2.set_rightchild(k3);
k2.set_leftchild(k1);
if(k3!=null)
k3.set_parent(k2);
if(k1!=null)
k1.set_parent(k2);
k1.set_rightchild(B);
k3.set_leftchild(C);
if(B!=null)
B.set_parent(k1);
if(C!=null)
C.set_parent(k3);
}
public int balance_factor(Node n)
{
Node n1=n.get_rightchild();
Node n2=n.get_leftchild();
int h1,h2;
h1=get_height(n1);
h2=get_height(n2);
return (h2-h1);
}
public Node returnUnbalanced(Node n)
{
Node unbal=null;
int checkflag=1;
if(get_height(n.get_parent())==1)
return unbal;
int bf;
while(n.get_parent()!=null)
{
n=n.get_parent();
bf=balance_factor(n);
if(checkflag==1)
if((bf==2)||(bf==-2))
{
unbal=n;
checkflag=0;
}
}
return unbal;
}
public void insert(Node n,Node bs)
{
if(bs==null)
{
root=n;
}
else
{
if(bs.get_data()>n.get_data())
{
if(bs.get_leftchild()==null)
{
bs.set_leftchild(n);
n.set_parent(bs);
Node unbal=returnUnbalanced(n);
if(unbal!=null)
{//balance it
int bf=balance_factor(unbal);
System.out.println("node ::"+unbal.get_data());
if(bf==2)
{
int bf2=balance_factor(unbal.get_leftchild());
if(bf2==1)
left_left_rot(unbal);
if(bf2==-1)
left_right_rot(unbal);
}
if(bf==-2)
{
int bf2=balance_factor(unbal.get_rightchild());
if(bf2==1)
right_left_rot(unbal);
if(bf2==-1)
right_right_rot(unbal);
}
}
}
else
insert(n,bs.get_leftchild());
}
else
{
if(bs.get_rightchild()==null)
{
bs.set_rightchild(n);
n.set_parent(bs);
Node unbal=returnUnbalanced(n);
if(unbal!=null)
{//perform the req bal op
int bf=balance_factor(unbal);
System.out.println("node::"+unbal.get_data());
if(bf==2)
{
int bf2=balance_factor(unbal.get_leftchild());
if(bf2==1)
left_left_rot(unbal);
if(bf2==-1)
left_right_rot(unbal);
}
if(bf==-2)
{
int bf2=balance_factor(unbal.get_rightchild());
if(bf2==1)
right_left_rot(unbal);
if(bf2==-1)
right_right_rot(unbal);
}
}
}
else
insert(n,bs.get_rightchild());
}
}
}
public void search(int n,Node bs)
{
if(bs==null)
System.out.println("not present in tree");
else
{
if(bs.get_data()==n)
System.out.println("Node is present in Tree");
else if(bs.get_data()>n)
search(n,bs.get_leftchild());
else
search(n,bs.get_rightchild());
}
}
public Node findmin(Node bs)
{
if(bs!=null)
while(bs.get_leftchild()!=null)
bs=bs.get_leftchild();
return bs;
}
public Node findmax(Node bs)
{
if(bs!=null)
while(bs.get_rightchild()!=null)
bs=bs.get_rightchild();
return bs;
}
public void del(int n,Node bs)
{
if(bs==null)
System.out.println("node not found in tree");
else
{
if(bs.get_data()==n)
{
//do the three cases
//case 1.Node has no children;
if((bs.get_leftchild()==null)&&(bs.get_rightchild()==null))
{
Node par=bs.get_parent();
if(par.get_rightchild()==bs)
par.set_rightchild(null);
else
par.set_leftchild(null);
}
//case 2.if Node has 1 child
else
{
if((bs.get_leftchild()==null)||(bs.get_rightchild()==null))
{
//System.out.println("here");
Node par=bs.get_parent();
Node child;
if(bs.get_leftchild()==null)
child=bs.get_rightchild();
else
child=bs.get_leftchild();
if(par.get_leftchild()==bs)
par.set_leftchild(child);
else
par.set_rightchild(child);
}
else //Node has 2 children
{
Node min_r=findmin(bs.get_rightchild());
int tset=min_r.get_data();
//min would be that node itself or left leaf
Node par=min_r.get_parent();
if(par==bs)
{
bs.set_rightchild(min_r.get_rightchild());
bs.set_data(tset);
}
else
{
par.set_leftchild(null);
bs.set_data(tset);
}
}
}
}
else if(bs.get_data()>n)
del(n,bs.get_leftchild());
else
del(n,bs.get_rightchild());
}
}
public void preorder(Node bs)
{
if(bs==null)
return;
else
{
System.out.print(bs.get_data()+" ");
preorder(bs.get_leftchild());
preorder(bs.get_rightchild());
}
}
public void postorder(Node bs)
{
if(bs==null)
return;
else
{
postorder(bs.get_leftchild());
postorder(bs.get_rightchild());
System.out.print(bs.get_data()+" ");
}
}
public void inorder(Node bs)
{
if(bs==null)
return;
else
{
inorder(bs.get_leftchild());
System.out.print(bs.get_data()+" ");
inorder(bs.get_rightchild());
}
}
}
class check
{
public static void main(String[] args)throws IOException
{
FileReader fr=new FileReader("input.txt");
BufferedReader br=new BufferedReader(fr);
InputStreamReader isr=new InputStreamReader(System.in);
BufferedReader br1=new BufferedReader(isr);
String line=br.readLine();
String[] numS=line.split(" ");
int[] numbers=new int[numS.length];
//create the bst
Avl tree=new Avl();
//input the elements
for(int i=0;i<numS.length;i++)
{
numbers[i]=Integer.parseInt(numS[i]);
Node n=new Node(numbers[i]);
tree.insert(n,tree.root);
}
//print the preorder
System.out.println("preorder traversal ::");
tree.preorder(tree.root);
System.out.println("\nPostorder traversal::");
tree.postorder(tree.root);
System.out.println("\ninorder traversal ::");
tree.inorder(tree.root);
//options
Node nn;
int d,s;
while(true)
{
System.out.println("\n1.tree height\n2.Search(int)\n3.findmin()\n4.findmax()\n5.preorder()\n6.postorder()\n7.inorder()\n8.exit\n");
int input=Integer.parseInt(br1.readLine());
switch(input)
{
/*case 1: d=Integer.parseInt(br1.readLine());
tree.del(d,tree.root);
break;*/
case 2: s=Integer.parseInt(br1.readLine());
tree.search(s,tree.root);
break;
case 3: nn=tree.findmin(tree.root);
System.out.println(nn.get_data());
break;
case 4: nn=tree.findmax(tree.root);
System.out.println(nn.get_data());
break;
case 5:tree.preorder(tree.root);
System.out.println();
break;
case 6:tree.postorder(tree.root);
System.out.println();
break;
case 7:tree.inorder(tree.root);
System.out.println();
break;
case 1:System.out.println(tree.get_height(tree.root));
break;
case 8:System.exit(1000);
break;
default:System.out.println("Not an option");
break;
}
}
}
}
