C++ Program to Perform AVL Tree Operations

This is a C++ Program to print the kind of rotation that is performed when an element is inserted or deleted from tree. In discrete mathematics, tree rotation is an operation on a binary tree that changes the structure without interfering with the order of the elements. A tree rotation moves one node up in the tree and one node down. It is used to change the shape of the tree, and in particular to decrease its height by moving smaller subtrees down and larger subtrees up, resulting in improved performance of many tree operations. There exists an inconsistency in different descriptions as to the definition of the direction of rotations. Some say that the direction of a rotation depends on the side which the tree nodes are shifted upon whilst others say that it depends on which child takes the root’s place (opposite of the former). This article takes the approach of the side where the nodes get shifted to.

Here is source code of the C++ Program to Print the Kind of Rotation the AVL Tree is Undergoing When you Add an Element or Delete an Element. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<sstream>
  4. #include<algorithm>
  5. #define pow2(n) (1 << (n))
  6. using namespace std;
  7. /*
  8.  * Node Declaration
  9.  */
  10. struct avl_node
  11. {
  12.         int data;
  13.         struct avl_node *left;
  14.         struct avl_node *right;
  15. }*root;
  16. /*
  17.  * Class Declaration
  18.  */
  19. class avlTree
  20. {
  21.     public:
  22.         int height(avl_node *);
  23.         int diff(avl_node *);
  24.         avl_node *rr_rotation(avl_node *);
  25.         avl_node *ll_rotation(avl_node *);
  26.         avl_node *lr_rotation(avl_node *);
  27.         avl_node *rl_rotation(avl_node *);
  28.         avl_node* balance(avl_node *);
  29.         avl_node* insert(avl_node *, int);
  30.         void display(avl_node *, int);
  31.         void inorder(avl_node *);
  32.         void preorder(avl_node *);
  33.         void postorder(avl_node *);
  34.         avlTree()
  35.         {
  36.             root = NULL;
  37.         }
  38. };
  39. /*
  40.  * Main Contains Menu
  41.  */
  42. int main()
  43. {
  44.     int choice, item;
  45.     avlTree avl;
  46.     while (1)
  47.     {
  48.         cout << "\n---------------------" << endl;
  49.         cout << "AVL Tree Implementation" << endl;
  50.         cout << "\n---------------------" << endl;
  51.         cout << "1.Insert Element into the tree" << endl;
  52.         cout << "2.Display Balanced AVL Tree" << endl;
  53.         cout << "3.InOrder traversal" << endl;
  54.         cout << "4.PreOrder traversal" << endl;
  55.         cout << "5.PostOrder traversal" << endl;
  56.         cout << "6.Exit" << endl;
  57.         cout << "Enter your Choice: ";
  58.         cin >> choice;
  59.         switch (choice)
  60.         {
  61.             case 1:
  62.                 cout << "Enter value to be inserted: ";
  63.                 cin >> item;
  64.                 root = avl.insert(root, item);
  65.                 break;
  66.             case 2:
  67.                 if (root == NULL)
  68.                 {
  69.                     cout << "Tree is Empty" << endl;
  70.                     continue;
  71.                 }
  72.                 cout << "Balanced AVL Tree:" << endl;
  73.                 avl.display(root, 1);
  74.                 break;
  75.             case 3:
  76.                 cout << "Inorder Traversal:" << endl;
  77.                 avl.inorder(root);
  78.                 cout << endl;
  79.                 break;
  80.             case 4:
  81.                 cout << "Preorder Traversal:" << endl;
  82.                 avl.preorder(root);
  83.                 cout << endl;
  84.                 break;
  85.             case 5:
  86.                 cout << "Postorder Traversal:" << endl;
  87.                 avl.postorder(root);
  88.                 cout << endl;
  89.                 break;
  90.             case 6:
  91.                 exit(1);
  92.                 break;
  93.             default:
  94.                 cout << "Wrong Choice" << endl;
  95.         }
  96.     }
  97.     return 0;
  98. }
  99. /*
  100.  * Height of AVL Tree
  101.  */
  102. int avlTree::height(avl_node *temp)
  103. {
  104.     int h = 0;
  105.     if (temp != NULL)
  106.     {
  107.         int l_height = height(temp->left);
  108.         int r_height = height(temp->right);
  109.         int max_height = max(l_height, r_height);
  110.         h = max_height + 1;
  111.     }
  112.     return h;
  113. }
  114. /*
  115.  * Height Difference
  116.  */
  117. int avlTree::diff(avl_node *temp)
  118. {
  119.     int l_height = height(temp->left);
  120.     int r_height = height(temp->right);
  121.     int b_factor = l_height - r_height;
  122.     return b_factor;
  123. }
  124. /*
  125.  * Right- Right Rotation
  126.  */
  127. avl_node *avlTree::rr_rotation(avl_node *parent)
  128. {
  129.     avl_node *temp;
  130.     temp = parent->right;
  131.     parent->right = temp->left;
  132.     temp->left = parent;
  133.     cout<<"Right-Right Rotation";
  134.     return temp;
  135. }
  136. /*
  137.  * Left- Left Rotation
  138.  */
  139. avl_node *avlTree::ll_rotation(avl_node *parent)
  140. {
  141.     avl_node *temp;
  142.     temp = parent->left;
  143.     parent->left = temp->right;
  144.     temp->right = parent;
  145.     cout<<"Left-Left Rotation";
  146.     return temp;
  147. }
  148. /*
  149.  * Left - Right Rotation
  150.  */
  151. avl_node *avlTree::lr_rotation(avl_node *parent)
  152. {
  153.     avl_node *temp;
  154.     temp = parent->left;
  155.     parent->left = rr_rotation(temp);
  156.     cout<<"Left-Right Rotation";
  157.     return ll_rotation(parent);
  158. }
  159. /*
  160.  * Right- Left Rotation
  161.  */
  162. avl_node *avlTree::rl_rotation(avl_node *parent)
  163. {
  164.     avl_node *temp;
  165.     temp = parent->right;
  166.     parent->right = ll_rotation(temp);
  167.     cout<<"Right-Left Rotation";
  168.     return rr_rotation(parent);
  169. }
  170. /*
  171.  * Balancing AVL Tree
  172.  */
  173. avl_node *avlTree::balance(avl_node *temp)
  174. {
  175.     int bal_factor = diff(temp);
  176.     if (bal_factor > 1)
  177.     {
  178.         if (diff(temp->left) > 0)
  179.         {
  180.             temp = ll_rotation(temp);
  181.         }
  182.         else
  183.         {
  184.             temp = lr_rotation(temp);
  185.         }
  186.     }
  187.     else if (bal_factor < -1)
  188.     {
  189.         if (diff(temp->right) > 0)
  190.         {
  191.             temp = rl_rotation(temp);
  192.         }
  193.         else
  194.         {
  195.             temp = rr_rotation(temp);
  196.         }
  197.     }
  198.     return temp;
  199. }
  200. /*
  201.  * Insert Element into the tree
  202.  */
  203. avl_node *avlTree::insert(avl_node *root, int value)
  204. {
  205.     if (root == NULL)
  206.     {
  207.         root = new avl_node;
  208.         root->data = value;
  209.         root->left = NULL;
  210.         root->right = NULL;
  211.         return root;
  212.     }
  213.     else if (value < root->data)
  214.     {
  215.         root->left = insert(root->left, value);
  216.         root = balance(root);
  217.     }
  218.     else if (value >= root->data)
  219.     {
  220.         root->right = insert(root->right, value);
  221.         root = balance(root);
  222.     }
  223.     return root;
  224. }
  225. /*
  226.  * Display AVL Tree
  227.  */
  228. void avlTree::display(avl_node *ptr, int level)
  229. {
  230.     int i;
  231.     if (ptr != NULL)
  232.     {
  233.         display(ptr->right, level + 1);
  234.         printf("\n");
  235.         if (ptr == root)
  236.             cout << "Root -> ";
  237.         for (i = 0; i < level && ptr != root; i++)
  238.             cout << "        ";
  239.         cout << ptr->data;
  240.         display(ptr->left, level + 1);
  241.     }
  242. }
  243. /*
  244.  * Inorder Traversal of AVL Tree
  245.  */
  246. void avlTree::inorder(avl_node *tree)
  247. {
  248.     if (tree == NULL)
  249.         return;
  250.     inorder(tree->left);
  251.     cout << tree->data << "  ";
  252.     inorder(tree->right);
  253. }
  254. /*
  255.  * Preorder Traversal of AVL Tree
  256.  */
  257. void avlTree::preorder(avl_node *tree)
  258. {
  259.     if (tree == NULL)
  260.         return;
  261.     cout << tree->data << "  ";
  262.     preorder(tree->left);
  263.     preorder(tree->right);
  264. }/*
  265.  * Postorder Traversal of AVL Tree
  266.  */
  267. void avlTree::postorder(avl_node *tree)
  268. {
  269.     if (tree == NULL)
  270.         return;
  271.     postorder(tree ->left);
  272.     postorder(tree ->right);
  273.     cout << tree->data << "  ";
  274. }

Output:

$ g++ TypeOfRotation.cpp
$ a.out
 
 
---------------------
AVL Tree Implementation
 
---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 1
Enter value to be inserted: 23
 
---------------------
AVL Tree Implementation
 
---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 3
Inorder Traversal:
23  
 
---------------------
AVL Tree Implementation
 
---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 1
Enter value to be inserted: 45
 
---------------------
AVL Tree Implementation
 
---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 2
Balanced AVL Tree:
 
                45
Root -> 23
---------------------
AVL Tree Implementation
 
---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 3
Inorder Traversal:
23  45  
 
---------------------
AVL Tree Implementation
 
---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 4
Preorder Traversal:
23  45  
 
---------------------
AVL Tree Implementation
 
---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 5
Postorder Traversal:
45  23  
 
---------------------
AVL Tree Implementation
 
---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 1
Enter value to be inserted: 37
Left-Left RotationRight-Left RotationRight-Right Rotation
---------------------
AVL Tree Implementation
 
---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter your Choice: 
------------------
(program exited with code: 0)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
advertisement

Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.

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 & discussions at Telegram SanfoundryClasses.