S.Y. B. Tech.

Academic Year 2024_25 Semester: IV

Project Based Learning – II (CSE2PM09A / AID2PM07A)
LABORATORY WRITE UP
Experiment Number: 04
TITLE: AVL Trees
PROBLEM STATEMENT:
Write a program to implement AVL tree for Dictionary. A Dictionary stores
keywords & its meaning. Provide facility for adding new keywords, deleting
keywords, updating values of any entry. Provide a facility to display whole data
sorted in ascending/ Descending order. Also find how many maximum
comparisons may require for finding any keyword. Use a Height balanced tree
and find the complexity for finding a keyword.
 class avlTree
{ avl_node *root;
Node Structure for AVL public:
int height(avl_node *);
Tree int diff(avl_node *);
avl_node *rr_rotation(avl_node *);
class avl_node avl_node *ll_rotation(avl_node *);
avl_node *lr_rotation(avl_node *);
{ avl_node *rl_rotation(avl_node *);
int value; avl_node* balance(avl_node *);
avl_node* insert();
avl_node *left, *right; avl_node* insert(avl_node *, avl_node *);
void display(avl_node *, int);
public: void inorder(avl_node *);
void preorder(avl_node *);
friend class avlTree; void postorder(avl_node *);
}; avlTree()
{
root = NULL;
}
};
 LL Rotation
parent
avl_node* avlTree:: LL_rotation (avl_node *parent)
temp
{
avl_node * temp = parent->left;
parent->left = temp->right;
temp->right = parent;
return temp; return address

}
 RR Rotation
avl_node* avlTree:: RR_rotation (avl_node *parent)
{
avl_node* temp = parent->right; parent

parent->right = temp->left; temp

temp->left = parent;
return temp;
} return address
 parent
LR Rotation temp

return address
avl_node* avlTree:: LR_rotation (avl_node *parent)
{
avl_node *temp = parent->left;
parent->left = RR_rotation (temp); //calling RR rotation
return LL_rotation (parent);
// return root after LL rotation
}
 parent

RL Rotation temp

return address

avl_node* avlTree:: RL_rotation (avl_node *parent)

{
avl_node *temp = parent->right;
parent->right = LL_rotation (temp); // calling LL rotation
return RR_rotation (parent);
// return root after RR rotation
}
int avlTree::diff(avl_node *temp)
{ int avlTree::height(avl_node *temp)
int l_height = height (temp->left); {
int r_height = height (temp->right);
int h = 0;
int b_factor= l_height - r_height;
return b_factor; if (temp != NULL)
} {
int l_height = height (temp->left);
-1
2 int r_height = height (temp->right);
int max_height = max (l_height, r_height);
0 0
h = max_height + 1;
1 7
}
return h;
0
8 0 }
5
avl_node* avlTree:: balance(avl_node *temp)
{
int bal_factor = diff (temp);
if (bal_factor > 1)
{
if (diff (temp->left) > 0)
temp = LL_rotation (temp);
else
temp = LR_rotation (temp);
}
else if (bal_factor < -1)
{
if (diff (temp->right) > 0)
temp = RL_rotation (temp);
else
temp = RR_rotation (temp);
}
return temp;
}
void avlTree::insert()
{
char ch;
do
{
avl_node *temp;
cout<<“Enter word and it’s meaning”;
cin>>temp->word>>temp->meaning;
root=insert(root, temp);
cout<<“Enter your choice”;
cin>>ch;
}while(ch == ‘Y’);
}
avl_node* avlTree:: insert( avl_node *root, avl_node *temp)
{
if (root == NULL)
Insert 9
{
root = new avl_node; -2
root->word= temp->word; 2
root->meaning= temp->meaning;
root->left = NULL; 0 -1
root->right = NULL;
1 7
return root;
}
else if (temp->word< root->data)
{ 0
root->left = insert(root->left, temp); 5 8 -1
root = balance (root);
}
else if (temp->word >= root->data) 9 0
{
root->right = insert(root->right, temp);
root = balance (root);
}
return root;
}
Algorithm display (node *ptr, int level) // consider level =1
{
if (ptr!=NULL)
{ display(ptr->right, level + 1);
printf("\n");
if (ptr == root)
cout<<"Root -> ";
for (i = 0; i < level && ptr != root; i++)
cout<<" ";
cout<<ptr->data;
display(ptr->left, level + 1);
}
}