C Program to Implement AVL Tree

«
»
What is an AVL Tree?

The AVL tree in C is a height-balanced binary search tree which means it is also a binary tree that is balanced by the left and right subtree of a node. The tree is said to be balanced when the balance factor of each node is either -1, 0, or +1.

The Balance factor of a tree can be defined as:

Balanced Factor(X) = height(left Subtree (X)) – height(right Subtree(X))

Example of AVL Tree:
AVL Tree Example

The above binary search tree is satisfying the condition of the balance factor, so it is an AVL tree.

Operations on AVL Tree in C

There are basically three kinds of operations that are performed in the AVL tree:

  1. Insertion of a New Node
  2. Deletion of a Node
  3. Searching a Node in AVL Tree

To perform these operations, we have to do the following four kinds of rotations:

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement

Let’s discuss these operations in detail and understand how these rotations work.

LL Rotation (Left Rotation)

In LL rotation, all the nodes are moved by one position to the left. To understand LL rotation, we have to take into consideration the following insertion operation.

Example: Insert 5, 6, and 9
AVL Tree Left Rotation Example

RR Rotation (Right Rotation)

In RR rotation, all the nodes are moved by one position to the right. To understand RR rotation, we have to take into consideration the following insertion operation.

Example: Insert 5, 4, and 3

AVL Tree Right Rotation Example

LR Rotation (Left Right Rotation)

In LR rotation, at the first step, every node moves to the left and then moves one step to the right from the current position. Let’s understand the LR rotation with the given example.

advertisement

Example: Insert 6, 4, and 5
AVL Tree Left Right Rotation Example

RL Rotation (Right Left Rotation)

In RL rotation, at the first step, every node moves to the right and then moves one step to the left from the current position. Let’s understand the RL rotation with the given example.

Example: Insert 4, 6, and 5
AVL Tree Right Left Rotation Example

Problem Description

Write a C program to perform the operations of the AVL tree and display its traversals.

advertisement
Problem Solution

An AVL (Adelson-Velskii and Landis) tree is a self-height balance tree. These trees are binary search trees in which the height of two siblings are not allowed to differ by more than one. We have used the doubly linked list implementation of the AVL tree in which every node contains the address of the left and right children and the data.

Here, we are implementing the main operations of the AVL tree these are given below:

  • Insert
  • Delete
  • Search
Program/Source Code

Here is source code of the C Program to Implement AVL Tree. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * AVL Tree Program in C
  3.  */
  4.  
  5. #include<stdio.h>
  6. #include<stdlib.h>
  7.  
  8. // structure of the tree node
  9. struct node
  10. {
  11.     int data;
  12.     struct node* left;
  13.     struct node* right;
  14.     int ht;
  15. };
  16.  
  17. // global initialization of root node
  18. struct node* root = NULL;
  19.  
  20. // function prototyping
  21. struct node* create(int);
  22. struct node* insert(struct node*, int);
  23. struct node* delete(struct node*, int);
  24. struct node* search(struct node*, int);
  25. struct node* rotate_left(struct node*);
  26. struct node* rotate_right(struct node*);
  27. int balance_factor(struct node*);
  28. int height(struct node*);
  29. void inorder(struct node*);
  30. void preorder(struct node*);
  31. void postorder(struct node*);
  32.  
  33. int main()
  34. {
  35.     int user_choice, data;
  36.     char user_continue = 'y';
  37.     struct node* result = NULL;
  38.  
  39.     while (user_continue == 'y' || user_continue == 'Y')
  40.     {
  41.         printf("\n\n------- AVL TREE --------\n");
  42.         printf("\n1. Insert");
  43.         printf("\n2. Delete");
  44.         printf("\n3. Search");
  45.         printf("\n4. Inorder");
  46.         printf("\n5. Preorder");
  47.         printf("\n6. Postorder");
  48.         printf("\n7. EXIT");
  49.  
  50.         printf("\n\nEnter Your Choice: ");
  51.         scanf("%d", &user_choice);
  52.  
  53.         switch(user_choice)
  54.         {
  55.             case 1:
  56.                 printf("\nEnter data: ");
  57.                 scanf("%d", &data);
  58.                 root = insert(root, data);
  59.                 break;
  60.  
  61.             case 2:
  62.                 printf("\nEnter data: ");
  63.                 scanf("%d", &data);
  64.                 root = delete(root, data);
  65.                 break;
  66.  
  67.             case 3:
  68.                 printf("\nEnter data: ");
  69.                 scanf("%d", &data);
  70.                 result = search(root, data);
  71.                 if (result == NULL)
  72.                 {
  73.                     printf("\nNode not found!");
  74.                 }
  75.                 else
  76.                 {
  77.                     printf("\n Node found");
  78.                 }
  79.                 break;
  80.             case 4:
  81.                 inorder(root);
  82.                 break;
  83.  
  84.             case 5:
  85.                 preorder(root);
  86.                 break;
  87.  
  88.             case 6:
  89.                 postorder(root);
  90.                 break;
  91.  
  92.             case 7:
  93.                 printf("\n\tProgram Terminated\n");
  94.                 return 1;
  95.  
  96.             default:
  97.                 printf("\n\tInvalid Choice\n");
  98.         }
  99.  
  100.         printf("\n\nDo you want to continue? ");
  101.         scanf(" %c", &user_continue);
  102.     }
  103.  
  104.     return 0;
  105. }
  106.  
  107. // creates a new tree node
  108. struct node* create(int data)
  109. {
  110.     struct node* new_node = (struct node*) malloc (sizeof(struct node));
  111.  
  112.     // if a memory error has occurred
  113.     if (new_node == NULL)
  114.     {
  115.         printf("\nMemory can't be allocated\n");
  116.         return NULL;
  117.     }
  118.     new_node->data = data;
  119.     new_node->left = NULL;
  120.     new_node->right = NULL;
  121.     return new_node;
  122. }
  123.  
  124. // rotates to the left
  125. struct node* rotate_left(struct node* root)
  126. {
  127.     struct node* right_child = root->right;
  128.     root->right = right_child->left;
  129.     right_child->left = root;
  130.  
  131.     // update the heights of the nodes
  132.     root->ht = height(root);
  133.     right_child->ht = height(right_child);
  134.  
  135.     // return the new node after rotation
  136.     return right_child;
  137. }
  138.  
  139. // rotates to the right
  140. struct node* rotate_right(struct node* root)
  141. {
  142.     struct node* left_child = root->left;
  143.     root->left = left_child->right;
  144.     left_child->right = root;
  145.  
  146.     // update the heights of the nodes
  147.     root->ht = height(root);
  148.     left_child->ht = height(left_child);
  149.  
  150.     // return the new node after rotation
  151.     return left_child;
  152. }
  153.  
  154. // calculates the balance factor of a node
  155. int balance_factor(struct node* root)
  156. {
  157.     int lh, rh;
  158.     if (root == NULL)
  159.         return 0;
  160.     if (root->left == NULL)
  161.         lh = 0;
  162.     else
  163.         lh = 1 + root->left->ht;
  164.     if (root->right == NULL)
  165.         rh = 0;
  166.     else
  167.         rh = 1 + root->right->ht;
  168.     return lh - rh;
  169. }
  170.  
  171. // calculate the height of the node
  172. int height(struct node* root)
  173. {
  174.     int lh, rh;
  175.     if (root == NULL)
  176.     {
  177.         return 0;
  178.     }
  179.     if (root->left == NULL)
  180.         lh = 0;
  181.     else
  182.         lh = 1 + root->left->ht;
  183.     if (root->right == NULL)
  184.         rh = 0;
  185.     else
  186.         rh = 1 + root->right->ht;
  187.  
  188.     if (lh > rh)
  189.         return (lh);
  190.     return (rh);
  191. }
  192.  
  193. // inserts a new node in the AVL tree
  194. struct node* insert(struct node* root, int data)
  195. {
  196.     if (root == NULL)
  197.     {
  198.         struct node* new_node = create(data);
  199.         if (new_node == NULL)
  200.         {
  201.             return NULL;
  202.         }
  203.         root = new_node;
  204.     }
  205.     else if (data > root->data)
  206.     {
  207.         // insert the new node to the right
  208.         root->right = insert(root->right, data);
  209.  
  210.         // tree is unbalanced, then rotate it
  211.         if (balance_factor(root) == -2)
  212.         {
  213.             if (data > root->right->data)
  214.             {
  215.                 root = rotate_left(root);
  216.             }
  217.             else
  218.             {
  219.                 root->right = rotate_right(root->right);
  220.                 root = rotate_left(root);
  221.             }
  222.         }
  223.     }
  224.     else
  225.     {
  226.         // insert the new node to the left
  227.         root->left = insert(root->left, data);
  228.  
  229.         // tree is unbalanced, then rotate it
  230.         if (balance_factor(root) == 2)
  231.         {
  232.             if (data < root->left->data)
  233.             {
  234.                 root = rotate_right(root);
  235.             }
  236.             else
  237.             {
  238.                 root->left = rotate_left(root->left);
  239.                 root = rotate_right(root);
  240.             }
  241.         }
  242.     }
  243.     // update the heights of the nodes
  244.     root->ht = height(root);
  245.     return root;
  246. }
  247.  
  248. // deletes a node from the AVL tree
  249. struct node * delete(struct node *root, int x)
  250. {
  251.     struct node * temp = NULL;
  252.  
  253.     if (root == NULL)
  254.     {
  255.         return NULL;
  256.     } 
  257.  
  258.     if (x > root->data)
  259.     {
  260.         root->right = delete(root->right, x);
  261.         if (balance_factor(root) == 2)
  262.         {
  263.             if (balance_factor(root->left) >= 0)
  264.             {
  265.                 root = rotate_right(root);
  266.             }
  267.             else
  268.             {
  269.                 root->left = rotate_left(root->left);
  270.                 root = rotate_right(root);
  271.             }
  272.         }
  273.     }
  274.     else if (x < root->data)
  275.     {
  276.         root->left = delete(root->left, x);
  277.         if (balance_factor(root) == -2)
  278.         {
  279.             if (balance_factor(root->right) <= 0)
  280.             {
  281.                 root = rotate_left(root);
  282.             }
  283.             else
  284.             {
  285.                 root->right = rotate_right(root->right);
  286.                 root = rotate_left(root);
  287.             }
  288.         }
  289.     }
  290.     else
  291.     {
  292.         if (root->right != NULL)
  293.         { 
  294.             temp = root->right;
  295.             while (temp->left != NULL)
  296.                 temp = temp->left;
  297.  
  298.             root->data = temp->data;
  299.             root->right = delete(root->right, temp->data);
  300.             if (balance_factor(root) == 2)
  301.             {
  302.                 if (balance_factor(root->left) >= 0)
  303.                 {
  304.                     root = rotate_right(root);
  305.                 }
  306.                 else
  307.                 {
  308.                     root->left = rotate_left(root->left);
  309.                     root = rotate_right(root);
  310.                 }
  311.             }
  312.         }
  313.         else
  314.         {
  315.             return (root->left);
  316.         }
  317.     }
  318.     root->ht = height(root);
  319.     return (root);
  320. }
  321.  
  322. // search a node in the AVL tree
  323. struct node* search(struct node* root, int key)
  324. {
  325.     if (root == NULL)
  326.     {
  327.         return NULL;
  328.     }
  329.  
  330.     if(root->data == key)
  331.     {
  332.         return root;
  333.     }
  334.  
  335.     if(key > root->data)
  336.     {
  337.         search(root->right, key);
  338.     }
  339.     else
  340.     {
  341.         search(root->left, key);
  342.     } 
  343. }
  344.  
  345. // inorder traversal of the tree
  346. void inorder(struct node* root)
  347. {
  348.     if (root == NULL)
  349.     {
  350.         return;
  351.     }
  352.  
  353.     inorder(root->left);
  354.     printf("%d ", root->data);
  355.     inorder(root->right);
  356. }
  357.  
  358. // preorder traversal of the tree
  359. void preorder(struct node* root)
  360. {
  361.     if (root == NULL)
  362.     {
  363.         return;
  364.     }
  365.  
  366.     printf("%d ", root->data);
  367.     preorder(root->left);
  368.     preorder(root->right);
  369. }
  370.  
  371. // postorder traversal of the tree
  372. void postorder(struct node* root)
  373. {
  374.     if (root == NULL)
  375.     {
  376.         return;
  377.     }
  378.  
  379.     postorder(root->left);
  380.     postorder(root->right);
  381.     printf("%d ", root->data);
  382. }
Program Explanation

The AVL tree is an extension to the binary search tree in which it is required to balance the height difference between the left and right subtree of a node. We can balance the height of the tree by rotations. Let’s understand the main operations of the AVL Tree with the examples and also discuss their time and space complexities.

Insert a Node in AVL Tree

On Inserting a new node into the AVL Tree it is necessary to maintain the balance factor of the tree. To insert a new node into the AVL tree, we have to follow the given steps:

  1. Insert a new element in the tree with the same binary search tree logic.
  2. Check the balance factor for each node.
  3. If the balanced factor is not -1 or 0 or +1 of any node then do the proper rotations else terminate.

Example: We are constructing the AVL Tree by inserting the following values.

10 15 20 9 5 16 17 8 6

Step 1: Insert a new node 10
Inserting a New Node in AVL Tree

Step 2: Insert a new node 15
Inserting a New Node 15 in AVL Tree

Step 3: Insert a new node 20
Inserting a New Node 20 in AVL Tree

Step 4: Insert a new node 9
Inserting a New Node 9 in AVL Tree

Step 5: Insert a new node 5
Inserting a New Node 5 in AVL Tree

Step 6: Insert a new node 16
Inserting a New Node 16 in AVL Tree

Step 7: Insert a new node 17
Inserting a New Node 17 in AVL Tree

Step 8: Insert a new node 8
Inserting a New Node 8 in AVL Tree

Step 9: Insert a new node 6
Inserting a New Node 6 in AVL Tree

Time Complexity: O(log n)
Time complexity of an AVL tree is O(log n). Inserting any node in the AVL tree takes logarithmic time because each call skips half the tree to determine the correct position to insert a node.

Space Complexity: O(n)
The space complexity of an avl tree is O(n), because the function calling stack eventually exceeds the number of nodes in the tree.

Run Time Testcases

In this case, we are inserting the nodes into AVL tree and finding traversals.

------- AVL TREE --------
 
1. Insert
2. Delete
3. Search
4. Inorder
5. Preorder
6. Postorder
7. EXIT
 
Enter Your Choice: 1     
 
Enter data: 34
 
 
Do you want to continue? y
------- AVL TREE --------
 
1. Insert
2. Delete
3. Search
4. Inorder
5. Preorder
6. Postorder
7. EXIT
 
Enter Your Choice: 1     
 
Enter data: 78
 
 
Do you want to continue? y
------- AVL TREE --------
 
1. Insert
2. Delete
3. Search
4. Inorder
5. Preorder
6. Postorder
7. EXIT
 
Enter Your Choice: 1
 
Enter data: 99
 
Do you want to continue? y
------- AVL TREE --------
 
1. Insert
2. Delete
3. Search
4. Inorder
5. Preorder
6. Postorder
7. EXIT
 
Enter Your Choice: 4
34 78 99 
 
Do you want to continue? y
------- AVL TREE --------
 
1. Insert
2. Delete
3. Search
4. Inorder
5. Preorder
6. Postorder
7. EXIT
 
Enter Your Choice: 5
78 34 99 
 
Do you want to continue? y
------- AVL TREE --------
 
1. Insert
2. Delete
3. Search
4. Inorder
5. Preorder
6. Postorder
7. EXIT
 
Enter Your Choice: 6
34 99 78 
 
Do you want to continue? n

Delete a Node from AVL Tree

Deletion of a node is similar to that of deleting a node in the binary search tree. In AVL Tree, after deleting the node we have to maintain the balanced factor again. We need to follow the given steps to delete a node in AVL Tree:

  1. Search the element in the tree
  2. Delete the node
  3. There are two cases that are possible after deletion
    • Deleting from the right subtree
    • Deleting from the left subtree


Case 1: Deleting a Node from the Right Subtree
There are three subcases that are discussed below:

a) Perform LL rotation when after deletion of a node the balance factor of a node changes to +2 and the balance factor of its left child is +1.
Deleting a node in AVL tree from the right subtree

b) Perform LL rotation when after deletion of a node the balance factor of a node changes to +2 and the balance factor of its left child is 0.
Deleting a node in AVL tree from the right subtree and perform LL rotation

c) Perform LR rotation when after deletion of a node the balance factor of a node changes to +2 and the balance factor of its left child is -1.
Deleting a node in AVL tree from the right subtree and perform LR rotation


Case 2: Deleting a Node from the Left Subtree
There are three subcases that are discussed below:

a) Perform RR rotation when after deletion of a node the balance factor of a node changes to -2 and the balance factor of its left child is -1.
Deleting a node in AVL tree from the left subtree

b) Perform RR rotation when after deletion of a node the balance factor of a node changes to -2 and the balance factor of its left child is 0.
Deleting a node in AVL tree from the left subtree and perform RR rotation

c) Perform RL rotation when after deletion of a node the balance factor of a node changes to -2 and the balance factor of its left child is 1.
Deleting a node in AVL tree from the left subtree and perform RL rotation

Time Complexity: O(log n)
To delete a node from the AVL tree, it takes logarithmic time to find and delete the given node i.e O(log n).

Space Complexity: O(n)
It takes n function calls for deletion and rebuilding the node from the AVL tree.

Run Time Testcases

In this case, we are deleting the nodes from the AVL tree.

------- AVL TREE --------
 
1. Insert
2. Delete
3. Search
4. Inorder
5. Preorder
6. Postorder
7. EXIT
 
Enter Your Choice: 1     
Enter data: 34
 
Enter Your Choice: 1     
Enter data: 78
 
Enter Your Choice: 1
Enter data: 99
 
Do you want to continue? y
------- AVL TREE --------
 
1. Insert
2. Delete
3. Search
4. Inorder
5. Preorder
6. Postorder
7. EXIT
 
Enter Your Choice: 4
34 78 99 
 
Do you want to continue? y
------- AVL TREE --------
 
1. Insert
2. Delete
3. Search
4. Inorder
5. Preorder
6. Postorder
7. EXIT
 
Enter Your Choice: 2
Enter data: 78
 
Do you want to continue? y
------- AVL TREE --------
 
1. Insert
2. Delete
3. Search
4. Inorder
5. Preorder
6. Postorder
7. EXIT
 
Enter Your Choice: 4
34 99

Searching a Node in AVL Tree

Searching a node in an AVL tree is a similar process that we do in a binary search Tree. Follow the given steps to search a node in AVL Tree.

  1. Start comparing the key with the root node of the tree.
  2. If the key is greater than the node value then move to the right subtree.
  3. If the key is less than the node value then move to the left subtree.
  4. Repeat the process until the key is not found.

Time Complexity: O(log n)
It takes logarithmic time to search any node in the AVL tree.

Space Complexity: O(h)
There are h function calls required to find the node in the AVL tree, where h is the height of the AVL tree.

Run Time Testcases

In this case, we are searching the node in the AVL tree.

------- AVL TREE --------
 
1. Insert
2. Delete
3. Search
4. Inorder
5. Preorder
6. Postorder
7. EXIT
 
Enter Your Choice: 1     
Enter data: 34
 
Enter Your Choice: 1     
Enter data: 78
 
Enter Your Choice: 1
Enter data: 99
 
Do you want to continue? y
------- AVL TREE --------
 
1. Insert
2. Delete
3. Search
4. Inorder
5. Preorder
6. Postorder
7. EXIT
 
Enter Your Choice: 4
34 78 99 
 
Do you want to continue? y
------- AVL TREE --------
 
1. Insert
2. Delete
3. Search
4. Inorder
5. Preorder
6. Postorder
7. EXIT
 
Enter Your Choice: 3
Enter data: 99
Node found
 
Do you want to continue? y
------- AVL TREE --------
 
1. Insert
2. Delete
3. Search
4. Inorder
5. Preorder
6. Postorder
7. EXIT
 
Enter Your Choice: 3
Enter data: 66
Node not found!
 
Do you want to continue? n

To practice programs on every topic in C, please visit “Programming Examples in C”, “Data Structures in C” and “Algorithms in C”.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.