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;
switch(c.bf)
{
case 1:
a.bf=-1;
b.bf=0;
break;
case -1:
a.bf=0;
b.bf=1;
break;
case 0:
a.bf=0;
b.bf=0;
break;
}
c.bf=0;
b=c;
}
}
else
{
if(b.bf==-1)
{
System.out.println("RR
imbalance");
a.RC=b.LC;
b.LC=a;
a.bf=0;
b.bf=0;
}
else
{
System.out.println("RL
imbalance");
c=b.LC;
b.LC=c.RC;
a.RC=c.LC;
c.RC=b;
c.LC=a;
switch(c.bf)
{
case 1:
a.bf=0;
b.bf=-1;
break;
case -1:
a.bf=1;
b.bf=0;
break;
case 0:
a.bf=0;
b.bf=0;
break;
}
c.bf=0;
b=c;
}
}
if(f==null)
root=b;
else
if(a==f.LC)
f.LC=b;
else
if(a==f.RC)
f.RC=b;
}
return
true;
}
return false;
}
public void
display()
{
if(root==null)
System.out.println("EMPTY");
else
{
System.out.println("\nIn Order");
dispin(root);
}
}
public void
dispin(node currentnode)
{
if(currentnode!=null)
{
dispin(currentnode.LC);
System.out.println(currentnode.data+" "+"BF "+currentnode.bf);
dispin(currentnode.RC);
}
}
};
class AVLTreeImp
{
public
static void main(String args[ ])throws IOException
{
int ch=0,cont=0;
avltree a = new avltree();
do
{
System.out.println("AVLTREES 1.
Insert ");
DataInputStream din = new DataInputStream(System.in);
try
{
ch=Integer.parseInt(din.readLine());
}
catch(Exception e){}
if(ch==1)
{
boolean y=true;
y=a.insert();
a.display();
if(y==false)
System.out.println("Data already exists");
}
else
{
System.out.println("Enter the correct
choice");
}
System.out.println("press 1 to continue:");
try
{
cont=Integer.parseInt(din.readLine());
}
catch(Exception e){}
}while(cont==1);
}
}
OUTPUT:
-------
AVLTREES 1. Insert
1
Enter the element:
3
In Order
3 BF 0
press 1 to continue:
1
AVLTREES 1. Insert
1
Enter the element:
2
In Order
2 BF 0
3 BF 1
press 1 to continue:
1
AVLTREES 1. Insert
1
Enter the element:
1
LL imbalance
In Order
1 BF 0
2 BF 0
3 BF 0
press 1 to continue:
1
AVLTREES 1. Insert
1
Enter the element:
4
In Order
1 BF 0
2 BF -1
3 BF -1
4 BF 0
press 1 to continue:
1
AVLTREES 1. Insert
1
Enter the element:
5
RR imbalance
In Order
1 BF 0
2 BF -1
3 BF 0
4 BF 0
5 BF 0
press 1 to continue:
1
AVLTREES 1. Insert
1
Enter the element:
6
RR imbalance
In Order
1 BF 0
2 BF 0
3 BF 0
4 BF 0
5 BF -1
6 BF 0
press 1 to continue:
1
AVLTREES 1. Insert
1
Enter the element:
7
RR imbalance
In Order
1 BF 0
2 BF 0
3 BF 0
4 BF 0
5 BF 0
6 BF 0
7 BF 0
press 1 to continue:
1
AVLTREES 1. Insert
1
Enter the element:
16
In Order
1 BF 0
2 BF 0
3 BF 0
4 BF -1
5 BF 0
6 BF -1
7 BF -1
16 BF 0
press 1 to continue:
1
AVLTREES 1. Insert
1
Enter the element:
15
RL imbalance
In Order
1 BF 0
2 BF 0
3 BF 0
4 BF -1
5 BF 0
6 BF -1
7 BF 0
15 BF 0
16 BF 0
press 1 to continue:
1
AVLTREES 1. Insert
1
Enter the element:
14
RL imbalance
In Order
1 BF 0
2 BF 0
3 BF 0
4 BF -1
5 BF 0
6 BF 1
7 BF 0
14 BF 0
15 BF 0
16 BF 0
press 1 to continue:
1
AVLTREES 1. Insert
1
Enter the element:
13
RR imbalance
In Order
1 BF 0
2 BF 0
3 BF 0
4 BF 0
5 BF 0
6 BF 1
7 BF 0
13 BF 0
14 BF 1
15 BF 1
16 BF 0
press 1 to continue:
1
AVLTREES 1. Insert
1
Enter the element:
12
LL imbalance
In Order
1 BF 0
2 BF 0
3 BF 0
4 BF 0
5 BF 0
6 BF 1
7 BF 0
12 BF 0
13 BF 0
14 BF 0
15 BF 1
16 BF 0
press 1 to continue:
1
AVLTREES 1. Insert
1
Enter the element:
11
LL imbalance
In Order
1 BF 0
2 BF 0
3 BF 0
4 BF 0
5 BF 0
6 BF 1
7 BF 0
11 BF 0
12 BF 1
13 BF 0
14 BF 0
15 BF 0
16 BF 0
press 1 to continue:
1
AVLTREES 1. Insert
1
Enter the element:
10
LL imbalance
In Order
1 BF 0
2 BF 0
3 BF 0
4 BF 0
5 BF 0
6 BF 1
7 BF 0
10 BF 0
11 BF 0
12 BF 0
13 BF 0
14 BF 0
15 BF 0
16 BF 0
press 1 to continue:
1
AVLTREES 1. Insert
1
Enter the element:
8
In Order
1 BF 0
2 BF 0
3 BF 0
4 BF 0
5 BF 0
6 BF 1
7 BF -1
8 BF 0
10 BF 1
11 BF 1
12 BF 0
13 BF 1
14 BF 0
15 BF 0
16 BF 0
press 1 to continue:
1
AVLTREES 1. Insert
1
Enter the element:
9
LR imbalance
In Order
1 BF 0
2 BF 0
3 BF 0
4 BF 0
5 BF 0
6 BF 1
7 BF -1
8 BF 0
9 BF 0
10 BF 0
11 BF 1
12 BF 0
13 BF 1
14 BF 0
15 BF 0
16 BF 0
press 1 to continue:
1
AVLTREES 1. Insert
1
Enter the element:
16
In Order
1 BF 0
2 BF 0
3 BF 0
4 BF 0
5 BF 0
6 BF 1
7 BF -1
8 BF 0
9 BF 0
10 BF 0
11 BF 1
12 BF 0
13 BF 1
14 BF 0
15 BF 0
16 BF 0
Data already exists
press 1 to continue:
12
No comments:
Post a Comment