AVL tree is self balancing tree in which for all nodes, the difference of height between the left subtree and the right subtree is less than or equal to 1. In this article, an avl tree is created and the difference of height is printed for each node.
Insertion and Creation of an AVL Tree
A new node can be inserted in an AVL tree by determining the correct position of the node. But insertion of a new node into the tree may affect the height of the tree and the tree might become unbalanced.
If the new nodes are inserted as child nodes on a non- leaf node there will be no alteration since there will be no effect on the balancing as there is no increase in the height of the tree.
If the new nodes are inserted as child nodes on a leaf node, the balancing of the tree might get distorted. This depends on whether the node is added to the left subtree or the right subtree.
Thus to re-balance the tree in order to conserve it’s characteristics we use Rotation Mechanism. There are four types of rotations which help maintain the balancing of the tree as specified above.
If, due to insertion,the b_fact of multiple nodes is disturbed, balancing occurs on the first ancestor of the node that has been inserted.
Note: During the process of insertion it is important to check the balancing factor of each node at each step, until the process end.
Let us understand with the help of an example. Consider we have following elements given to us: [ 15 , 18 , 12 , 8 , 54 , 5 , 14 , 13 , 9 , 60].
#include<bits/stdc++.h>
using namespace std;
struct node
{
int element;
struct node *left,*right;
int ht;
};
node *insert(node *,int);
void preorder(node *);
void inorder(node *);
int height( node *);
node *rotateright(node *);
node *rotateleft(node *);
node *RR(node *);
node *LL(node *);
node *LR(node *);
node *RL(node *);
int balanceFactor(node *);
int main()
{
node *root=NULL;
int x,n,i,option;
do {
cout << “1. Create AVL Tree\n“;
cout << “2. End Program\n“;
cout << “Enter your choice “;
cin >> option;
switch(option)
{
case 1: cout << “\nEnter no. of elements : “;
cin >> n;
root = NULL;
for( i = 0; i < n;i++) {
cout << “Enter element of tree “;
cin >> x;
root = insert(root,x);
}
cout << “\nPreorder sequence:\n“;
preorder(root);
cout << “\n\nInorder sequence:\n“;
inorder(root);
break;
}
}while(option!=2);
return 0;
}
node * insert(node *T,int x)
{
if(T == NULL){
T = (node*)malloc(sizeof(node));
T -> element = x;
T -> left = NULL;
T -> right = NULL;
}
else
if(x > T->element)
{
T -> right = insert(T -> right,x);
if(balanceFactor(T) == –2)
if( x > T -> right -> element)
T = RR(T);
else
T = RL(T);
}
else
if(xelement)
{
T -> left = insert(T -> left,x);
if(balanceFactor(T)==2)
if(x < T-> left -> element)
T=LL(T);
else
T=LR(T);
}
T -> ht = height(T);
return(T);
}
int height(node *T)
{
int lh,rh;
if(T == NULL)
return(0);
if( T -> left == NULL)
lh = 0;
else
lh = 1 + T -> left -> ht;
if(T -> right == NULL)
rh = 0;
else
rh=1+T->right->ht;
if(lh > rh)
return(lh);
return(rh);
}
node * rotateright(node *x)
{
node *y;
y = x -> left;
x -> left = y -> right;
y -> right = x;
x -> ht = height(x);
y -> ht = height(y);
return(y);
}
node * rotateleft(node *x)
{
node *y;
y = x -> right;
x -> right = y -> left;
y -> left = x;
x -> ht = height(x);
y -> ht = height(y);
return(y);
}
node * RR(node *T)
{
T = rotateleft(T);
return(T);
}
node * LL(node *T)
{
T = rotateright(T);
return(T);
}
node * LR(node *T)
{
T -> left = rotateleft(T->left);
T = rotateright(T);
return(T);
}
node * RL(node *T)
{
T -> right = rotateright(T->right);
T = rotateleft(T);
return(T);
}
int balanceFactor(node *T)
{
int lh,rh;
if( T == NULL)
return(0);
if(T -> left == NULL)
lh = 0;
else
lh = 1 + T->left->ht;
if(T -> right == NULL)
rh = 0;
else
rh = 1 + T -> right -> ht;
return(lh-rh);
}
void preorder(node *T)
{
if( T != NULL)
{
cout << “Balance factor “ << T -> element << ” “ << balanceFactor(T) << endl;
preorder(T->left);
preorder(T->right);
}
}
void inorder(node *T)
{
if( T != NULL)
{
inorder(T->left);
cout << “Balance Factor “< element<<” “ << balanceFactor(T) << endl;
inorder(T->right);
}
}
Output:
1. Create AVL Tree
2. End Program
Enter your choice 1
Enter no. of elements : 10
Enter element of tree 15
Enter element of tree 18
Enter element of tree 12
Enter element of tree 8
Enter element of tree 54
Enter element of tree 5
Enter element of tree 14
Enter element of tree 13
Enter element of tree 9
Enter element of tree 60
Preorder sequence:
Balance factor 15 1
Balance factor 12 0
Balance factor 8 0
Balance factor 5 0
Balance factor 9 0
Balance factor 13 -1
Balance factor 14 0
Balance factor 54 0
Balance factor 18 0
Balance factor 60 0
Inorder sequence:
Balance Factor 5 0
Balance Factor 8 0
Balance Factor 9 0
Balance Factor 12 0
Balance Factor 13 -1
Balance Factor 14 0
Balance Factor 15 1
Balance Factor 18 0
Balance Factor 54 0
Balance Factor 60 0
1. Create AVL Tree
2. End Program
Enter your choice 2
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Login/Signup to comment