C++ Program to Implement AVL Tree

This C++ Program demonstrates operations on AVL Trees.

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

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

$ g++ avl_tree.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: 1)
Press return to continue

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

advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

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.