C++ Program to Perform Left and Right Rotation on AVL Tree

This is a C++ Program to perform Left Rotation in Binary Search Trees. 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 Perform Left Rotation on a Binary Search Tree. 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.     return temp;
  134. }
  135. /*
  136.  * Left- Left Rotation
  137.  */
  138. avl_node *avlTree::ll_rotation(avl_node *parent)
  139. {
  140.     avl_node *temp;
  141.     temp = parent->left;
  142.     parent->left = temp->right;
  143.     temp->right = parent;
  144.     return temp;
  145. }
  146. /*
  147.  * Left - Right Rotation
  148.  */
  149. avl_node *avlTree::lr_rotation(avl_node *parent)
  150. {
  151.     avl_node *temp;
  152.     temp = parent->left;
  153.     parent->left = rr_rotation(temp);
  154.     return ll_rotation(parent);
  155. }
  156. /*
  157.  * Right- Left Rotation
  158.  */
  159. avl_node *avlTree::rl_rotation(avl_node *parent)
  160. {
  161.     avl_node *temp;
  162.     temp = parent->right;
  163.     parent->right = ll_rotation(temp);
  164.     return rr_rotation(parent);
  165. }
  166. /*
  167.  * Balancing AVL Tree
  168.  */
  169. avl_node *avlTree::balance(avl_node *temp)
  170. {
  171.     int bal_factor = diff(temp);
  172.     if (bal_factor > 1)
  173.     {
  174.         if (diff(temp->left) > 0)
  175.             temp = ll_rotation(temp);
  176.         else
  177.             temp = lr_rotation(temp);
  178.     }
  179.     else if (bal_factor < -1)
  180.     {
  181.         if (diff(temp->right) > 0)
  182.             temp = rl_rotation(temp);
  183.         else
  184.             temp = rr_rotation(temp);
  185.     }
  186.     return temp;
  187. }
  188. /*
  189.  * Insert Element into the tree
  190.  */
  191. avl_node *avlTree::insert(avl_node *root, int value)
  192. {
  193.     if (root == NULL)
  194.     {
  195.         root = new avl_node;
  196.         root->data = value;
  197.         root->left = NULL;
  198.         root->right = NULL;
  199.         return root;
  200.     }
  201.     else if (value < root->data)
  202.     {
  203.         root->left = insert(root->left, value);
  204.         root = balance(root);
  205.     }
  206.     else if (value >= root->data)
  207.     {
  208.         root->right = insert(root->right, value);
  209.         root = balance(root);
  210.     }
  211.     return root;
  212. }
  213. /*
  214.  * Display AVL Tree
  215.  */
  216. void avlTree::display(avl_node *ptr, int level)
  217. {
  218.     int i;
  219.     if (ptr != NULL)
  220.     {
  221.         display(ptr->right, level + 1);
  222.         printf("\n");
  223.         if (ptr == root)
  224.             cout << "Root -> ";
  225.         for (i = 0; i < level && ptr != root; i++)
  226.             cout << "        ";
  227.         cout << ptr->data;
  228.         display(ptr->left, level + 1);
  229.     }
  230. }
  231. /*
  232.  * Inorder Traversal of AVL Tree
  233.  */
  234. void avlTree::inorder(avl_node *tree)
  235. {
  236.     if (tree == NULL)
  237.         return;
  238.     inorder(tree->left);
  239.     cout << tree->data << "  ";
  240.     inorder(tree->right);
  241. }
  242. /*
  243.  * Preorder Traversal of AVL Tree
  244.  */
  245. void avlTree::preorder(avl_node *tree)
  246. {
  247.     if (tree == NULL)
  248.         return;
  249.     cout << tree->data << "  ";
  250.     preorder(tree->left);
  251.     preorder(tree->right);
  252. }/*
  253.  * Postorder Traversal of AVL Tree
  254.  */
  255. void avlTree::postorder(avl_node *tree)
  256. {
  257.     if (tree == NULL)
  258.         return;
  259.     postorder(tree ->left);
  260.     postorder(tree ->right);
  261.     cout << tree->data << "  ";
  262. }

Output:

$ g++ ALVLeftRotation.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: 2
Tree is Empty
 
---------------------
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: 8
 
---------------------
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:
 
Root -> 8
---------------------
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: 5
 
---------------------
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:
 
Root -> 8
                5
---------------------
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: 4
 
---------------------
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:
 
                8
Root -> 5
                4
---------------------
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: 11
 
---------------------
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:
 
                        11
                8
Root -> 5
                4
---------------------
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: 15
 
---------------------
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:
 
                        15
                11
                        8
Root -> 5
                4
---------------------
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: 3
 
---------------------
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:
 
                        15
                11
                        8
Root -> 5
                4
                        3
---------------------
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: 6
 
---------------------
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:
 
                        15
                11
                        8
                                6
Root -> 5
                4
                        3
---------------------
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: 2
 
---------------------
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:
 
                        15
                11
                        8
                                6
Root -> 5
                        4
                3
                        2
---------------------
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:
5  3  2  4  11  8  6  15  
 
---------------------
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:
2  4  3  6  8  15  11  5  
 
---------------------
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:
2  3  4  5  6  8  11  15  
 
---------------------
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:
 
                        15
                11
                        8
                                6
Root -> 5
                        4
                3
                        2
---------------------
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: 6
 
------------------
(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.

If you find any mistake above, kindly email to [email protected]

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.