Practical No.
9 Group D
Aim: To illustrate the AVL tree (Balanced binary search tree).
Problem Statement :
D-19 A Dictionary stores keywords and its meanings. Provide facility for adding new keywords, deleting
keywords, updating values of any entry. Provide facility to display whole data sorted in ascending/
Descending order. Also find how many maximum comparisons may require for finding any keyword. Use
Height balance tree and find the complexity for finding a keyword
Learning Objectives:
1. To understand concept of height balanced tree data structure.
2. To understand procedure to create height balanced tree.
Learning Outcome:
• Define class for AVL using Object Oriented features.
• Analyze working of various operations on AVL Tree .
Theory:
An empty tree is height balanced tree if T is a nonempty binary tree with TL and TR as
its left and right sub trees. The T is height balance if and only if Its balance factor is 0, 1, -1.
AVL (Adelson- Velskii and Landis) Tree: A balance binary search tree. The best search time,
that is O (log N) search times. An AVL tree is defined to be a well-balanced binary search tree in
which each of its nodes has the AVL property. The AVL property is that the heights of the left and
right sub-trees of a node are either equal or if they differ only by 1.
What if the input to binary search tree comes in a sorted (ascending or descending)
manner? It will then look like this −
It is observed that BST's worst-case performance is closest to linear search algorithms, that
is Ο(n). In real-time data, we cannot predict data pattern and their frequencies. So, a need arises to
balance out the existing BST.
Named after their inventor Adelson, Velski & Landis, AVL trees are height balancing
binary search tree. AVL tree checks the height of the left and the right sub-trees and assures that
the difference is not more than 1. This difference is called the Balance Factor.
Here we see that the first tree is balanced and the next two trees are not balanced −
In the second tree, the left subtree of C has height 2 and the right subtree has height 0, so
the difference is 2. In the third tree, the right subtree of A has height 2 and the left is missing, so it
is 0, and the difference is 2 again. AVL tree permits difference (balance factor) to be only 1.
BalanceFactor = height(left-sutree) − height(right-sutree)
If the difference in the height of left and right sub-trees is more than 1, the tree is balanced using
some rotation techniques.
AVL Rotations
To balance itself, an AVL tree may perform the following four kinds of rotations −
• Left rotation
• Right rotation
• Left-Right rotation
• Right-Left rotation
The first two rotations are single rotations and the next two rotations are double rotations. To
have an unbalanced tree, we at least need a tree of height 2. With this simple tree, let's understand
them one by one.
Left Rotation
If a tree becomes unbalanced, when a node is inserted into the right subtree of the right
subtree, then we perform a single left rotation −
In our example, node A has become unbalanced as a node is inserted in the right subtree
of A's right subtree. We perform the left rotation by making A the left-subtree of B.
Right Rotation
AVL tree may become unbalanced, if a node is inserted in the left subtree of the left
subtree. The tree then needs a right rotation.
As depicted, the unbalanced node becomes the right child of its left child by performing a right
rotation.
Left-Right Rotation
Double rotations are slightly complex version of already explained versions of rotations.
To understand them better, we should take note of each action performed while rotation. Let's first
check how to perform Left-Right rotation. A left-right rotation is a combination of left rotation
followed by right rotation.
State Action
A node has been inserted into the right subtree of the left subtree.
This makes C an unbalanced node. These scenarios cause AVL tree
to perform left-right rotation.
We first perform the left rotation on the left subtree of C. This
makes A, the left subtree of B.
Node C is still unbalanced, however now, it is because of the left-
subtree of the left-subtree.
We shall now right-rotate the tree, making B the new root node of
this subtree. C now becomes the right subtree of its own left subtree.
The tree is now balanced.
Right-Left Rotation
The second type of double rotation is Right-Left Rotation. It is a combination of right
rotation followed by left rotation.
State Action
A node has been inserted into the left subtree of the right subtree.
This makes A, an unbalanced node with balance factor 2.
First, we perform the right rotation along C node, making C the right
subtree of its own left subtree B. Now, B becomes the right subtree
of A.
Node A is still unbalanced because of the right subtree of its right
subtree and requires a left rotation.
A left rotation is performed by making B the new root node of the
subtree. A becomes the left subtree of its right subtree B.
The tree is now balanced.
Algorithm:
Insert:-
1. If P is NULL, then
I. P = new node
II. P ->element = x
III. P ->left = NULL
IV. P ->right = NULL
V. P ->height = 0
2. else if x>1 => x<P ->element
a.) insert(x, P ->left)
b.) if height of P->left -height of P ->right =2
1. insert(x, P ->left)
2. if height(P ->left) -height(P ->right) =2
if x<P ->left ->element
P =singlerotateleft(P)
else
P =doublerotateleft(P)
3. else
if x<P ->element
a.) insert(x, P -> right)
b.) if height (P -> right) -height (P ->left) =2
if(x<P ->right) ->element
P =singlerotateright(P)
else
P =doublerotateright(P)
4. else
Print already exits
5. int m, n, d.
6. m = AVL height (P->left)
7. n = AVL height (P->right)
8. d = max(m, n)
9. P->height = d+1
10. Stop
RotateWithLeftChild( AvlNode k2 )
➢ AvlNode k1 = k2.left;
➢ k2.left = k1.right;
➢ k1.right = k2;
➢ k2.height = max( height( k2.left ), height( k2.right ) ) + 1;
➢ k1.height = max( height( k1.left ), k2.height ) + 1;
➢ return k1;
RotateWithRightChild( AvlNode k1 )
➢ AvlNode k2 = k1.right;
➢ k1.right = k2.left;
➢ k2.left = k1;
➢ k1.height = max( height( k1.left ), height( k1.right ) ) + 1;
➢ k2.height = max( height( k2.right ), k1.height ) + 1;
➢ return k2;
doubleWithLeftChild( AvlNode k3)
➢ k3.left = rotateWithRightChild( k3.left );
➢ return rotateWithLeftChild( k3 );
doubleWithRightChild( AvlNode k1 )
➢ k1.right = rotateWithLeftChild( k1.right );
➢ return rotateWithRightChild( k1 );
Software required: g++ / gcc compiler- / 64 bit fedora.
Input:
1. No.of Element.
2. key values
3. Key Probability
Outcome
• Learn height balanced binary tree in data structure.
• Understand & implement rotations required to balance the tree.
Conclusion : This program gives us the knowledge height balanced binary tree.
Questions:
1. What is AVL tree?
2. In an AVL tree, at what condition the balancing is to be done
3. When would one want to use a balance binary search tree (AVL) rather than an array data
structure.
Program Code:
#include<iostream>
#include<cstring>
#include<cstdlib>
#define MAX 50
#define SIZE 20
using namespace std;
struct AVLnode
{
public:
char cWord[SIZE],cMeaning[MAX];
AVLnode *left,*right;
int iB_fac,iHt;
};
class AVLtree
{
public:
AVLnode *root;
AVLtree()
{
root=NULL;
}
int height(AVLnode*);
int bf(AVLnode*);
AVLnode* insert(AVLnode*,char[SIZE],char[MAX]);
AVLnode* rotate_left(AVLnode*);
AVLnode* rotate_right(AVLnode*);
AVLnode* LL(AVLnode*);
AVLnode* RR(AVLnode*);
AVLnode* LR(AVLnode*);
AVLnode* RL(AVLnode*);
AVLnode* delet(AVLnode*,char x[SIZE]);
void inorder(AVLnode*);
};
AVLnode *AVLtree::delet(AVLnode *curr,char x[SIZE])
{
AVLnode *temp;
if(curr==NULL)
return(0);
else
if(strcmp(x,curr->cWord)>0)
{
curr->right=delet(curr->right,x);
if(bf(curr)==2)
if(bf(curr->left)>=0)
curr=LL(curr);
else
curr=LR(curr);
}
else
if(strcmp(x,curr->cWord)<0)
{
curr->left=delet(curr->left,x);
if(bf(curr)==-2)
if(bf(curr->right)<=0)
curr=RR(curr);
else
curr=RL(curr);
}
else
{
if(curr->right!=NULL)
{
temp=curr->right;
while(temp->left!=NULL)
temp=temp->left;
strcpy(curr->cWord,temp->cWord);
curr->right=delet(curr->right,temp->cWord);
if(bf(curr)==2)
if(bf(curr->left)>=0)
curr=LL(curr);
else
curr=LR(curr);
}
else
return(curr->left);
}
curr->iHt=height(curr);
return(curr);
}
AVLnode* AVLtree :: insert(AVLnode*root,char newword[SIZE],char newmeaning[MAX])
{
if(root==NULL)
{
root=new AVLnode;
root->left=root->right=NULL;
strcpy(root->cWord,newword);
strcpy(root->cMeaning,newmeaning);
}
else if(strcmp(root->cWord,newword)!=0)
{
if(strcmp(root->cWord,newword)>0)
{
root->left=insert(root->left,newword,newmeaning);
if(bf(root)==2)
{
if (strcmp(root->left->cWord,newword)>0)
root=LL(root);
else
root=LR(root);
}
}
else if(strcmp(root->cWord,newword)<0)
{
root->right=insert(root->right,newword,newmeaning);
if(bf(root)==-2)
{
if(strcmp(root->right->cWord,newword)>0)
root=RR(root);
else
root=RL(root);
}
}
}
else
cout<<"\nRedundant AVLnode";
root->iHt=height(root);
return root;
}
int AVLtree :: height(AVLnode* curr)
{
int lh,rh;
if(curr==NULL)
return 0;
if(curr->right==NULL && curr->left==NULL)
return 0;
else
{
lh=lh+height(curr->left);
rh=rh+height(curr->right);
if(lh>rh)
return lh+1;
return rh+1;
}
}
int AVLtree :: bf(AVLnode* curr)
{
int lh,rh;
if(curr==NULL)
return 0;
else
{
if(curr->left==NULL)
lh=0;
else
lh=1+curr->left->iHt;
if(curr->right==NULL)
rh=0;
else
rh=1+curr->right->iHt;
return(lh-rh);
}
}
AVLnode* AVLtree :: rotate_right(AVLnode* curr)
{
AVLnode* temp;
temp=curr->left;
curr->left=temp->right;
temp->left=curr;
curr->iHt=height(curr);
temp->iHt=height(temp);
return temp;
}
AVLnode* AVLtree :: rotate_left(AVLnode* curr)
{
AVLnode* temp;
temp=curr->right;
curr->right=temp->left;
temp->left=curr;
curr->iHt=height(curr);
temp->iHt=height(temp);
return temp;
}
AVLnode* AVLtree :: RR(AVLnode* curr)
{
curr=rotate_left(curr);
return curr;
}
AVLnode* AVLtree :: LL(AVLnode* curr)
{
curr=rotate_right(curr);
return curr;
}
AVLnode* AVLtree :: RL(AVLnode* curr)
{
curr->right=rotate_right(curr->right);
curr=rotate_left(curr);
return curr;
}
AVLnode* AVLtree::LR(AVLnode* curr)
{
curr->left=rotate_left(curr->left);
curr=rotate_right(curr);
return curr;
}
void AVLtree :: inorder(AVLnode* curr)
{
if(curr!=NULL)
{
inorder(curr->left);
cout<<"\n\t"<<curr->cWord<<"\t"<<curr->cMeaning;
inorder(curr->right);
}
}
int main()
{
int iCh;
AVLtree a;
AVLnode *curr=NULL;
char cWd[SIZE],cMean[MAX];
cout<<"\n--------------------------------------";
cout<<"\n\tAVL TREE IMPLEMENTATION";
cout<<"\n--------------------------------------";
do
{ cout<<"\n--------------------------------";
cout<<"\n\t\tMENU";
cout<<"\n--------------------------------";
cout<<"\n1.Insert\n2.Inorder\n3.Delete\n4.Exit";
cout<<"\n--------------------------------";
cout<<"\nEnter your choice :";
cin>>iCh;
switch(iCh)
{
case 1: cout<<"\nEnter Word : ";
cin>>cWd;
/*for(int i;cMean[i]!='\0';i++)
{
if(cMean[i]>='A'&& cMean[i]<='Z')
{
cMean[i]=cMean[i]+32;
}
}
cout<<cMean;*/
cout<<"\nEnter Meaning : ";
cin.ignore();
cin.getline(cMean,MAX);
a.root=a.insert(a.root,cWd,cMean);
break;
case 2: cout<<"\n\tWORD\tMEANING";
a.inorder(a.root);
break;
case 3: cout<<"\nEnter the word to be deleted : ";
cin>>cWd;
curr=a.delet(a.root,cWd);
if(curr==NULL)
cout<<"\nWord deleted Successfully!";
else
cout<<"\nWord not present!";
curr=NULL;
break;
case 4: exit(0);
}
}while(iCh!=4);
return 0;
}
