AIM
To implement the AVL tree with
insert & delete operations using Java.
ALGORITHM
Step 1:
Start the program by defining the functions.
Step 2:
Insert the elements to the AVL tree.
Step 3:
Check the tree if it is balanced or not.
Step 4:
The balance factor is one of 0, 1 and -1.
Step 5:
If it is not balanced, balance the tree using
(i)
Left-left
(ii)
Left-right
(iii) Right-left
(iv) Right-right
Balancing
Step
6:
And if the tree is balanced and then the insert() and
the delete() operations are performed.
Step 7:
Stop the program.
PROGRAM
AVL TREE
import java.io.*;
class node
{
public int
data;
public node
LC,RC;
public int bf;
}
class avltree
{
node root =
null;
public boolean
insert()
{
int
newelt=0;
try
{
System.out.println("Enter the
element:");
DataInputStream din=new
DataInputStream(System.in);
newelt=Integer.parseInt(din.readLine());
}
catch(Exception e){}
if(root==null)
{
node y=new node();
y.data=newelt;
y.bf=0;
y.LC=null;
y.RC=null;
root=y;
return true;
}
node
f,a,q,p;
node b,c;
int
d;
node
y=new node();
boolean
found, unbalanced;
f=null;
a=root;
p=root;
q=null;
found=false;
while
(p!=null && found!=true)
{
if(p.bf!=0)
{a=p;f=q;}
if(newelt<p.data){q=p;p=p.LC;}
else
if(newelt>p.data){q=p;p=p.RC;}
else
{y=p;found=true;}
}
if(found==false)
{
y.data=newelt;
y.bf=0;
y.LC=null;
y.RC=null;
if(newelt<q.data)
q.LC=y;
else
q.RC=y;
if(newelt >a.data)
{p=a.RC;b=p;d=-1;}
else
{p=a.LC;b=p;d=1;}
while(p!=y)
{
if(newelt
> p.data)
{p.bf=-1;p=p.RC;}
else
{p.bf=1;p=p.LC;}
}
unbalanced=true;
if((a.bf==0)||((a.bf+d)==0))
{a.bf+=d;unbalanced=false;}
if(unbalanced==true)
{
if(d==1)
{
if(b.bf==1)
{
System.out.println("LL
imbalance");
a.LC=b.RC;
b.RC=a;
a.bf=0;
b.bf=0;
}
else
{
System.out.println("LR
imbalance");
c=b.RC;
b.RC=c.LC;
a.LC=c.RC;
c.LC=b;
c.RC=a;
