Program For AVL Tree

import java.io.*;
import java.util.*;


class Nodetype
{
int info;
int ht;
Nodetype left;
Nodetype right;
Nodetype(int i)
{
info=i;
ht=0;
left=null;
right=null;
}
}
class Functions
{
Nodetype AVLroot;
void create ()
{
int x,n,i;
AVLroot=null;
System.out.println("\nEnter no.of elements :");
n=getNumber();
System.out.println("\nEnter tree info :");
for(i=0;i<n;i++)
{
x=getNumber();
AVLroot=insert(AVLroot,x);
}
System.out.println("\nPreorder sequence : ");
preorder(AVLroot);
System.out.println("\nInorder sequence : ");
inorder(AVLroot);
System.out.println("\nPostorder sequence : ");
postorder(AVLroot);
}
int getNumber()
{
String str;
int ne=0;
InputStreamReader input=new InputStreamReader(System.in);
BufferedReader in=new BufferedReader(input);
try
{
str=in.readLine();
ne=Integer.parseInt(str);
}
catch(Exception e)
{
System.out.println("I/O Error");
}
return ne;
}/*end getnumber*/


Nodetype insert(Nodetype T,int x)
{
if(T==null)
{
Nodetype node=new Nodetype(x);
T=node;
}
else
if(x > T.info)                // insert in right subtree
{
T.right=insert(T.right,x);
if(BF(T)==-2)
if(x>T.right.info)
T=RR(T);
else
T=RL(T);
}
else
if(x<T.info)             //insert in right subtree
{
T.left=insert(T.left,x);
if(BF(T)==2)
if(x < T.left.info)
T=LL(T);
else
T=LR(T);
}
T.ht=height(T);
return(T);
}
int height(Nodetype T)
{
int lh,rh;
if(T==null)
return(0);


if(T.left==null)
lh=0;
else
lh=1+T.left.ht;


if(T.right==null)
rh=0;
else
rh=1+T.right.ht;


if(lh>rh)
return(lh);
return(rh);
}
Nodetype rotateright(Nodetype x)
{
Nodetype y;
y=x.left;
x.left=y.right;
y.right=x;
x.ht=height(x);
y.ht=height(y);
return(y);
}
Nodetype rotateleft(Nodetype x)
{
Nodetype y;
y=x.right;
x.right=y.left;
y.left=x;
x.ht=height(x);
y.ht=height(y);
return(y);
}
Nodetype RR(Nodetype T)
{
T=rotateleft(T);
return(T);
}
Nodetype LL(Nodetype T)
{
T=rotateright(T);
return(T);
}
Nodetype LR(Nodetype T)
{
T.left=rotateleft(T.left);
T=rotateright(T);
return(T);
}
Nodetype RL(Nodetype T)
{
T.right=rotateright(T.right);
T=rotateleft(T);
return(T);
}
int BF(Nodetype T)
{
int lh,rh;
if(T==null)
return(0);
if(T.left==null)
lh=0;
else
lh=1+T.left.ht;
if(T.right==null)
rh=0;
else
rh=1+T.right.ht;
return(lh-rh);
}
void preorder(Nodetype T)
{
if(T!=null)
{
System.out.print(" "+T.info);
preorder(T.left);
preorder(T.right);
}
}
void inorder(Nodetype T)
{
if(T!=null)
{
inorder(T.left);
System.out.print(" "+T.info);
inorder(T.right);
}
}
void postorder(Nodetype T)
{
if(T!=null)
{
postorder(T.left);
postorder(T.right);
System.out.print(" "+T.info);
}
}
}
class AVL
{
public static void main(String args[])
{
Functions f=new Functions();
f.create();
}
}


/*
Sample input and output :
Enter no.of elements :
10


Enter tree info :
1
2
3
4
5
6
7
8
9
10


Preorder sequence :
 4 2 1 3 8 6 5 7 9 10
Inorder sequence :
 1 2 3 4 5 6 7 8 9 10
Postorder sequence :
 1 3 2 5 7 6 10 9 8 4
*/