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
Recommended Answers
Jump to PostSo what is the error you are getting .The title seems like compiler is throwing warnings.
Post your error messages here..
Jump to PostLook at those compiler warnings. The compiler will also suggest to you an argumnet to use during compilation. Do so, and it will tell you exactly what needs to be changed.
All 5 Replies
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.