logo
  • Home
  • Test & Rank
  • About
  • Training
  • Programming
  • CS
  • IT
  • IS
  • ECE
  • EEE
  • EE
  • Civil
  • Mechanical
  • Chemical
  • Metallurgy
  • Instrumentation
  • Aeronautical
  • Aerospace
  • Biotechnology
  • Mining
  • Marine
  • Agriculture
  • MCA
  • BCA
  • Internship
  • Jobs
  • Contact

Questions & Answers

C Interview Questions
C++ Questions
Linux MCQs
C# Quiz
Java MCQs
JavaScript MCQs
SAN Questions
PHP Questions
Python Quiz

Computer Science Questions

Operating System Quiz
Computer Architecture MCQs
Software Architecture MCQs
Software Engineering MCQs
Artificial Intelligence MCQs
LISP Programming MCQs
Database Management MCQs
Computer Network MCQs
Microprocessor MCQs

C Programming Examples

Simple C Programs
C - Arrays
C - Matrix
C - Strings
C - Bitwise Operations
C - Linked Lists
C - Stacks & Queues
C - Searching & Sorting
C - Trees
C - Strings
C - File Handling
C - Mathematical Functions
C - Puzzles & Games
C Programs - Recursion
C Programs - No Recursion

Java Algorithms

Java - Numerical Problems
Java - Combinatorial Problems
Java - Graph Problems
Java - Hard Graph Problems
Java - Computation Geometry
Java - Sets & Strings
Java - Data-Structures
Java - Collection API Problems

C++ Algorithms

C++ - Numerical Problems
C++ - Combinatorial Problems
C++ - Graph Problems
C++ - Hard Graph Problems
C++ - Computation Geometry
C++ - Sets & Strings
C++ - Data-Structures
C++ - STL Library

C Algorithms

C - Numerical Problems
C - Combinatorial Problems
C - Graph Problems
C - Hard Graph Problems
C - Computation Geometry
C - Sets & Strings
C - Data-Structures

« Prev Page
Next Page »

C++ Program to Implement AVL Trees

Posted on August 28, 2013 by Manish
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. }

advertisement
$ 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
If you wish to look at all C++ Programming examples, go to C++ Programs.
« Prev Page - C++ Program to Implement Hash Tables Chaining with List Heads
» Next Page - C++ Program to Implement Binary Search Tree

« C++ Program to Implement Hash Tables Chaining with List Heads
C++ Program to Implement Doubly Ended Queue »

Deep Dive @ Sanfoundry:

  1. C Programming Examples on Stacks & Queues
  2. C Programming Examples on Hard Graph Problems & Algorithms
  3. C Programming Examples on Graph Problems & Algorithms
  4. C Programming Examples on Linked List
  5. C Programming Examples without using Recursion
  6. C# Programming Examples on Data Structures
  7. C# Programming Examples on Functions
  8. C# Programming Examples on Interfaces
  9. C Programming Examples on Data-Structures
  10. C Programming Examples on Trees
Manish Bhojasia
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Facebook | Twitter

Best Careers

Developer Tracks
SAN Developer
Linux Kernel Developer
Linux Driver Developer
Linux Network Developer

Live Training Photos
Mentoring
Software Productivity
GDB Assignment
Sanfoundry is No. 1 choice for Deep Hands-ON Trainings in SAN, Linux & C, Kernel Programming. Our Founder has trained employees of almost all Top Companies in India such as VMware, Citrix, Oracle, Motorola, Ericsson, Aricent, HP, Intuit, Microsoft, Cisco, SAP Labs, Siemens, Symantec, Redhat, Chelsio, Cavium, ST-Micro, Samsung, LG-Soft, Wipro, TCS, HCL, IBM, Accenture, HSBC, Mphasis, Tata-Elxsi, Tata VSNL, Mindtree, Cognizant and Startups.

Best Trainings

SAN I - Technology
SAN II - Admin
Linux Fundamentals
Advanced C Training
Linux-C Debugging
System Programming
Network Programming
Linux Threads
Kernel Programming
Kernel Debugging
Linux Device Drivers

Best Reference Books

Computer Science Books
Algorithm & Programming Books
Electronics Engineering Books
Electrical Engineering Books
Chemical Engineering Books
Civil Engineering Books
Mechanical Engineering Books
Industrial Engineering Books
Instrumentation Engg Books
Metallurgical Engineering Books
All Stream Best Books

Questions and Answers

1000 C Questions & Answers
1000 C++ Questions & Answers
1000 C# Questions & Answers
1000 Java Questions & Answers
1000 Linux Questions & Answers
1000 Python Questions
1000 PHP Questions & Answers
1000 Hadoop Questions
Cloud Computing Questions
Computer Science Questions
All Stream Questions & Answers

India Internships

Computer Science Internships
Instrumentation Internships
Electronics Internships
Electrical Internships
Mechanical Internships
Industrial Internships
Systems Internships
Chemical Internships
Civil Internships
IT Internships
All Stream Internships

About Sanfoundry

About Us
Copyright
Terms
Privacy Policy
Jobs
Bangalore Training
Online Training
Developers Track
Mentoring Sessions
Contact Us
Sitemap
© 2011 Sanfoundry. All Rights Reserved.