import java.io.*;
class avlnode
{
public int data,bf;
public avlnode lchild,rchild,parent;
}
class avl
{
avlnode root=null;
avlnode p=null;
avlnode prev=null;
public void insert(int ele)
{
avlnode temp=new avlnode();
temp.data=ele;
temp.lchild=null;
temp.rchild=null;
temp.parent=null;
p=new avlnode();
prev=new avlnode();
p=root;
if(root==null)
{
root=temp;
}
else
{
while(p!=null)
{
prev=p;
if(p.data>temp.data)
{
p=p.lchild;
}
else
{
p=p.rchild;
}
}
if(prev.data>temp.data)
{
prev.lchild=temp;
prev.lchild.parent=prev;
prev.bf+=1;
}
else
{
prev.rchild=temp;
prev.rchild.parent=prev;
prev.bf-=1;
}
// calculating balance factor..
while((prev!=null) && (prev.bf!=2) && (prev.bf!=-2))
{
p=prev;
prev=prev.parent;
if(prev!=null)
{
if(p==prev.lchild)
prev.bf+=1;
else
prev.bf-=1;
}
}
System.out.println("The tree before rotation");
dispre(root);
if((prev!=null) && (prev.bf==2))
{
switch(p.bf)
{
case 1:
System.out.println("left-left rotation");
ll_rotate();
dispre(root);
break;
case -1:
System.out.println("left-right rotation");
lr_rotate();
dispre(root);
break;
}
}
if((prev!=null) && (prev.bf==-2))
{
switch(p.bf)
{
case 1:
System.out.println("right-left rotation");
rl_rotate();
dispre(root);
break;
case -1:
System.out.println("right-right rotaion");
rr_rotate();
dispre(root);
break;
}
}
}
}
public void ll_rotate()
{
p.parent=prev.parent;
if(prev.parent!=null)
{
prev.parent.lchild=p;
}
p.rchild=prev;
prev.lchild=null;
if(prev==root)
root=p;
prev.bf=0;
p.bf=0;
}
public void rr_rotate()
{
p.parent=prev.parent;
if(prev.parent!=null)
{
prev.parent.rchild=p;
}
p.lchild=prev;
prev.rchild=null;
if(prev==root)
root=p;
prev.bf=0;
p.bf=0;
}
public void lr_rotate()
{
avlnode t=p.rchild;
if(t.lchild!=null)
p.rchild=t.lchild;
else
p.rchild=null;
if(t.rchild!=null)
prev.lchild=t.rchild;
else
prev.lchild=null;
if(prev.parent!=null)
{
t.parent=prev.parent;
prev.parent.lchild=t;
}
else
{
t.parent=null;
root=t;
}
t.rchild=prev;
t.lchild=p;
t.bf=0;
p.bf=0;
prev.bf=0;
}
public void rl_rotate()
{
avlnode t=p.lchild;
if(t.rchild!=null)
p.lchild=t.rchild;
else
p.lchild=null;
if(t.lchild!=null)
prev.rchild=t.lchild;
else
prev.rchild=null;
if(prev.parent!=null)
{
t.parent=prev.parent;
prev.parent.rchild=t;
}
else
{
t.parent=null;
root=t;
}
t.lchild=prev;
t.rchild=p;
t.bf=0;
p.bf=0;
prev.bf=0;
}
public void dispre(avlnode currentnode)
{
if(currentnode!=null)
{
dispre(currentnode.lchild);
System.out.println(currentnode.data+" bf:"+currentnode.bf);
dispre(currentnode.rchild);
}
}
}
class avlmain
{
public static void main(String[] args)throws IOException
{
System.out.println("AVL Tree");
DataInputStream in=new DataInputStream(System.in);
System.out.println("Enter your choice");
avl tree=new avl();
int ans;
do
{
System.out.println("Enter a data");
int val=Integer.parseInt(in.readLine());
tree.insert(val);
System.out.println("Press 1 to insert");
ans=Integer.parseInt(in.readLine());
}while(ans==1);
}
}
hannah shrn j 0 Newbie Poster
harinath_2007 56 Posting Whiz
masijade 1,351 Industrious Poster Team Colleague Featured Poster
hag++ 24 Junior Poster
hannah shrn j 0 Newbie Poster
JamesCherrill 4,733 Most Valuable Poster Team Colleague Featured Poster
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.