AVL TREE
Program Coding:
import java.io.*;
class avlnode
{
public int data,bf;
public avlnode lchild,rchild,parent;
}
class avl
{
public 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;
}
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);
if(currentnode==root)
System.out.println("This
is the root");
System.out.println(currentnode.data+"
bf:"+currentnode.bf);
dispre(currentnode.rchild);
}
}
}
class avlnew
{
public static
void main(String[] args)throws IOException
{
System.out.println("AVL Tree");
DataInputStream in=new DataInputStream(System.in);
System.out.println("Insert your values");
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("Want to continue press 1");
ans=Integer.parseInt(in.readLine());
}while(ans==1);
}
}
Output:
AVL
TREE:
Enter
your choice:
Enter
a data:
40
Want
to continue press1:
1
Enter
a data:
70
The
tree before rotation:
This
the root
40bf:-1
70bf:0
Want
to continue press1:
1
Enter
a data:
50
Want
to continue press1:
The
tree before rotation:
40bf:-2
50
bf:0
70
bf:1
Right-Left
Rotation:
40bf:0
This the root
50
bf:0
70
bf:0
Want
to continue press1:
0
No comments:
Post a Comment