Select Page

AVL Tree

AVL Tree is referred to as self-balanced or height-balanced binary search tree where the difference between heights of its left subtree and right subtree (Balance Factor) can’t more than one for all nodes covered by a tree.

Example:

We can say a tree is balanced if the balance factor of each node of a tree is in between -1 to 1; otherwise, a tree is considered as unbalanced and need to balance.

Balance Factor (node) = height (left (node)) – height (right (node))

• If the balance factor is 1 of any node of the tree, then we can say the height of the left subtree is higher than the height of the right subtree of the node in the AVL tree.
• If the balance factor is 0 of any node of the tree, then we can say the height of the left subtree is equal to the height of the right subtree of the node in the AVL tree.
• If the balance factor is -1 of any node of the tree, then we can say the height of the left subtree is lower than the height of the right subtree of the node in the AVL tree.

Need for AVL Trees

If we talk about operations of binary search tree take O (log n) time. The time complexity of these operations could be O(n) if the binary search tree skewed (if the input to the binary search tree comes in an ascending or descending manner) and if we make sure the height of the binary search tree is balanced so we can guarantee that all these operations will take O(log n) time.

AVL Tree Operations

As we discussed, the AVL tree is a special type of binary search tree, so the operations of the AVL tree are the same as the binary search tree without violation of AVL property.

• Insertion: –

In this, we add a new node to the AVL tree. Sometimes it may lead to violating the property of AVL, so we need to re-balance the tree by applying the rotation on it.

• Deletion: –

In this, we delete a node from the AVL tree. It may disturb the balance of the AVL tree, so the tree needs to be re-balanced.

Rotations of AVL Tree:

There are four types of rotations of AVL, which are given below:

• Right Rotation on AVL Tree: –

When the AVL tree is unbalanced because a node is inserted into the left subtree of the Z in the AVL tree, then we have to perform the right rotation on AVL; it is a clockwise rotation.

• Left Rotation on AVL Tree: –

When the AVL tree is unbalanced because a node is inserted into the right subtree of Z in the AVL tree, then we have to perform left rotation on AVL; it is an anti-clockwise rotation.

• Left – Right Rotation on AVL Tree

Doubled rotation is a bit difficult version of AVL rotation. In Left – Right rotation, we perform the left rotation first, then the right rotation after it.

• Right – Left Rotation on AVL Tree: –

It is another type of double rotation version. In the right – Left rotation, we perform the right rotation first, then the left rotation after it.

Implementation of AVL Tree in C Language: –

#include<stdio.h>

typedef struct node

{

int data;

struct node *left, *right;

int ht;

}node;

node *insert(node *, int);

node *Delete(node *, int);

void preorder(node *);

void inorder(node *);

int height( node *);

node *rotate_right(node *);

node *rotate_left(node *);

node *right_rotation(node *);

node *left_rotation(node *);

node *left_right_rotation(node *);

node *right_left_rotation(node *);

int balance_factor(node *);

int main()

{

node *root = NULL;

int x, n, i, op;

do

{

printf(“\n1)Create: “);

printf(“\n2)Insert: “);

printf(“\n3)Delete: “);

printf(“\n4)Print: “);

printf(“\n5)Quit: “);

scanf(“%d”, &op);

switch (op)

{

case 1: printf(“\nEnter no. of elements: “);

scanf(“%d”, &n);

printf(“\nEnter tree data: “);

root = NULL;

for(i = 0; i<n; i++)

{

scanf(“%d”, &x);

root = insert(root, x);

}

break;

case 2: printf(“\nEnter a data: “);

scanf(“%d”, &x);

root = insert(root, x);

break;

case 3: printf(“\nEnter a data: “);

scanf(“%d”, &x);

root = Delete(root, x);

break;

case 4: printf(“\nPreorder sequence: \n”);

preorder( root );

printf(“\n\nInorder sequence: \n”);

inorder( root );

printf(“\n”);

break;

}

}while(op != 5);

return 0;

}

node * insert(node *temp, int x)

{

if(temp == NULL)

{

temp = (node*) malloc (sizeof(node));

temp->data = x;

temp->left = NULL;

temp->right = NULL;

}

else

if(x > temp-> data)                 // insert in right sub tree

{

temp->right = insert(temp->right, x);

if(balance_factor(temp) == -2)

if(x>temp->right->data)

temp = right_rotation(temp);

else

temp = right_left_rotation(temp);

}

else

if(x < temp->data)

{

temp->left = insert(temp->left, x);

if(balance_factor(temp) == 2)

if(x < temp->left->data)

temp = left_rotation(temp);

else

temp = left_right_rotation(temp);

}

temp->ht = height(temp);

return(temp);

}

node * Delete(node *temp, int x)

{

node *p;

if(temp == NULL)

{

return NULL;

}

else

if(x > temp->data)                  // insert in right sub tree

{

temp->right = Delete(temp->right, x);

if(balance_factor(temp) == 2)

if(balance_factor(temp->left) >= 0)

temp = left_rotation(temp);

else

temp = left_right_rotation(temp);

}

else

if(x < temp->data)

{

temp->left = Delete(temp->left,x);

if(balance_factor(temp) == -2)        //Rebalance tree

if(balance_factor(temp->right)<=0)

temp = right_rotation(temp);

else

temp = right_left_rotation(temp);

}

else

{

// data to be deleted is found

if(temp->right != NULL)

{        //delete its inorder succesor

p = temp->right;

while(p->left != NULL)

p = p->left;

temp->data = p->data;

temp->right = Delete(temp->right, p->data);

if(balance_factor(temp) == 2) //Rebalance tree

if(balance_factor(temp->left) >= 0)

temp = left_rotation(temp);

else

temp = left_right_rotation(temp);

}

else

return(temp->left);

}

temp->ht = height(temp);

return(temp);

}

int height(node * temp)

{

int lh,rh;

if(temp == NULL)

return(0);

if(temp->left == NULL)

lh = 0;

else

lh = 1+ temp->left->ht;

if(temp->right == NULL)

rh = 0;

else

rh = 1+ temp->right->ht;

if(lh > rh)

return(lh);

return(rh);

}

node * rotate_right(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 * rotate_left(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 * right_rotation(node *temp)

{

temp = rotate_left(temp);

return(temp);

}

node * left_rotation(node *temp)

{

temp = rotate_right(temp);

return(temp);

}

node * left_right_rotation(node *temp)

{

temp->left = rotate_left(temp->left);

temp = rotate_right(temp);

return(temp);

}

node * right_left_rotation(node *temp)

{

temp->right = rotate_right(temp->right);

temp = rotate_left(temp);

return(temp);

}

int balance_factor(node *temp)

{

int lh,rh;

if(temp == NULL)

return(0);

if(temp->left == NULL)

lh = 0;

else

lh = 1+temp->left->ht;

if(temp->right == NULL)

rh = 0;

else

rh = 1+temp->right->ht;

return(lh – rh);

}

void preorder(node *temp)

{

if(temp != NULL)

{

printf(“%d(Bf = %d)”, temp->data,balance_factor(temp));

preorder(temp->left);

preorder(temp->right);

}

}

void inorder(node *temp)

{

if(temp != NULL)

{

inorder(temp->left);

printf(“%d(Bf = %d)”,temp->data, balance_factor(temp));

inorder(temp->right);

}

}

Output: –

Time Complexity of AVL Tree

The rotations of the AVL tree take constant time. It is a self-balanced tree, so the time complexity of all the operations (e.g., insertion, deletion and searching) is O (log n).

Applications of AVL Tree

• It is used for indexing large records in the database.
• Also, it is used for efficient searching or finding the record from the database efficiently.