C++ Program to Implement AA Tree

This C++ Program demonstrates operations on AA Trees.

Here is source code of the C++ Program to demonstrate AA 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 AA Tree
  3.  */
  4. #include <iostream>
  5. #include <cstdlib>
  6. #include <cstring>
  7. #include <fstream>
  8. using namespace std;
  9. /*
  10.  * Node Declaration
  11.  */
  12. struct node
  13. {
  14.     int count, level;
  15.     string key;	
  16.     node *right;
  17.     node *left;
  18.     node *parent;
  19.     node *root;
  20. }*root;
  21.  
  22. /*
  23.  * Class Declaration
  24.  */
  25. class AATree
  26. {
  27.     public:
  28.         int lookup(string &);
  29.         void skew(node *);
  30.         bool split(node *);
  31.         void rebal(node *);
  32.         node *insert(node *,node *);
  33.         void print(node *);
  34.         int countnode(node *);
  35.         AATree()
  36. 	{
  37.             root = NULL;
  38.         }
  39. };
  40.  
  41. /*
  42.  * Main: Contains Menu
  43.  */
  44. int main()
  45. {
  46.     AATree at;
  47.     int ch;
  48.     string x;
  49.     ifstream fin ("test.txt");
  50.     while (1)
  51.     {
  52.         cout<<"\n---------------------"<<endl;
  53.         cout<<"\nOperations on AA Tree"<<endl;
  54.         cout<<"\n---------------------"<<endl;
  55.         cout<<"1.Insert String into the Tree"<<endl;
  56.         cout<<"2.Print Tree Data"<<endl;
  57.         cout<<"3.Total Tree Nodes"<<endl;
  58.         cout<<"4.Exit"<<endl;
  59.         cout<<"Enter Your Choice: ";
  60.         cin>>ch;
  61.         switch (ch)
  62.         {
  63.         case 1:
  64.             if (fin.is_open())
  65.     	    {
  66.                 while (fin>>x)
  67.                 {
  68.                     at.lookup(x);
  69.                 }
  70.                 fin.close();
  71.             }
  72. 	    break;
  73.         case 2:
  74.             cout<<"Elemets of AA Tree"<<endl;
  75.             at.print(root);
  76.             break;
  77.         case 3:
  78.             cout<<"Total number of nodes"<<endl;
  79.             cout<<at.countnode(root)<<endl;
  80.             break;
  81.         case 4:
  82.             cout<<"Exiting"<<endl;
  83.             exit(1);
  84.             break;
  85.         default:
  86.             cout<<"Wrong Choice"<<endl;
  87.         }
  88.     }
  89.     return 0;
  90. }
  91. /*
  92.  * Insert String into the Tree
  93.  */
  94. int AATree::lookup(string &key)
  95. {
  96.     node *temp = new node;
  97.     temp->key = key;
  98.     temp->level = 1;
  99.     temp->count = 0;
  100.     temp->left = NULL;
  101.     temp->right = NULL;
  102.     temp->parent = NULL;
  103.     temp = insert(root, temp);
  104.     return temp->count;
  105. }
  106.  
  107. /*
  108.  * Skew Tree
  109.  */
  110.  
  111. void AATree::skew(node *temp)
  112. {
  113.     node *ptr = temp->left;
  114.     if (temp->parent->left == temp)
  115.         temp->parent->left = ptr;
  116.     else
  117.         temp->parent->right = ptr;
  118.     ptr->parent = temp->parent;
  119.     temp->parent = ptr;
  120.     temp->left = ptr->right;
  121.     if (temp->left != NULL)
  122.     	temp->left->parent = temp;
  123.     ptr->right = temp;
  124.     temp->level = (temp->left ? temp->left->level + 1 : 1);
  125. }
  126.  
  127. /*
  128.  * Splitting of AA Tree
  129.  */
  130. bool AATree::split(node *temp)
  131. {
  132.     node* ptr = temp->right;
  133.     if (ptr && ptr->right && (ptr->right->level == temp->level))
  134.     {
  135.         if (temp->parent->left == temp)
  136.             temp->parent->left = ptr;
  137.         else
  138.             temp->parent->right = ptr;
  139.         ptr->parent = temp->parent;
  140.         temp->parent = ptr;
  141.         temp->right = ptr->left;
  142.         if (temp->right != NULL)
  143.             temp->right->parent = temp;
  144.         ptr->left = temp;
  145.         ptr->level = temp->level + 1;
  146.         return true;
  147.     }
  148.     return false;
  149. }
  150.  
  151. /*
  152.  * Rebalancing of AA Tree
  153.  */
  154. void AATree::rebal(node* temp)
  155. {
  156.     temp->left = NULL;
  157.     temp->right = NULL;
  158.     temp->level = 1;
  159.     for (temp = temp->parent; temp != root; temp = temp->parent)
  160.     {
  161.         if (temp->level != (temp->left ? temp->left->level + 1 : 1 ))
  162.         {
  163.             skew(temp);
  164.             if (temp->right == NULL)
  165.                 temp = temp->parent;
  166.             else if (temp->level != temp->right->level)
  167.                 temp = temp->parent;
  168.         }
  169.         if (temp->parent != root)
  170.         {
  171.             if (split(temp->parent) == false)
  172.                 break;
  173.         }
  174.     }
  175. }
  176.  
  177. /*
  178.  * Insert Function to insert string into the tree
  179.  */
  180. node* AATree::insert(node* temp, node* ins)
  181. {
  182.     if (root == NULL)
  183.     {
  184.         ins->count = 1;
  185.         ins->parent = NULL;
  186.         ins->left = NULL;
  187.         ins->right = NULL;
  188.         root = ins;
  189.         return root;
  190.     }
  191.     if (ins->key < temp->key)
  192.     {
  193.         if (temp->left)
  194.             return insert(temp->left, ins);
  195.         temp->left = ins;
  196.         ins->parent = temp;
  197.         ins->count = 1;
  198.         rebal(ins);
  199.         return ins;
  200.     }
  201.     if (ins->key > temp->key)
  202.     {
  203.         if (temp->right)
  204.             return insert(temp->right, ins);
  205.         temp->right = ins;
  206.         ins->parent = temp;
  207.         ins->count = 1;
  208.         rebal(ins);
  209.         return ins;
  210.     }
  211.     temp->count++;
  212.     delete ins;
  213.     return temp;
  214. }
  215.  
  216. /*
  217.  * Display Tree Elements
  218.  */
  219. void AATree::print(node* temp)
  220. {
  221.     if (!temp)
  222.         return;
  223.     print(temp->left);
  224.     cout <<"Value: "<<temp->key << "  Count:" << temp->count;
  225.     cout<<"  Level: "<<temp->level<<endl;
  226.     print(temp->right);
  227. }
  228.  
  229. /*
  230.  * Count number of nodes in AA Tree
  231.  */
  232. int AATree::countnode(node* temp)
  233. {
  234.     if (!temp)
  235.         return 0;
  236.     int count = 1;
  237.     count = count + countnode(temp->left);
  238.     count = count + countnode(temp->right);
  239.     return count;
  240. }

$ g++ aatrees.cpp
$ a.out
test.txt
"1 2 3 4 5 11 22 33 44 55 101 202 303 404 505 1111 2222 3333 4444 5555" 
 
---------------------
 
Operations on AA Tree
 
---------------------
1.Insert String into the Tree
2.Print Tree Data
3.Total Tree Nodes
4.Exit
Enter Your Choice: 1
 
---------------------
 
Operations on AA Tree
 
---------------------
1.Insert String into the Tree
2.Print Tree Data
3.Total Tree Nodes
4.Exit
Enter Your Choice: 2
Elemets of AA Tree
Value: 1  Count:1  Level: 1
Value: 101  Count:1  Level: 1
Value: 11  Count:1  Level: 2
Value: 1111  Count:1  Level: 1
Value: 2  Count:1  Level: 3
Value: 202  Count:1  Level: 1
Value: 22  Count:1  Level: 2
Value: 2222  Count:1  Level: 1
Value: 3  Count:1  Level: 4
Value: 303  Count:1  Level: 1
Value: 33  Count:1  Level: 2
Value: 3333  Count:1  Level: 1
Value: 4  Count:1  Level: 3
Value: 404  Count:1  Level: 1
Value: 44  Count:1  Level: 2
Value: 4444  Count:1  Level: 1
Value: 5  Count:1  Level: 3
Value: 505  Count:1  Level: 1
Value: 55  Count:1  Level: 2
Value: 5555  Count:1  Level: 1
 
---------------------
 
Operations on AA Tree
 
---------------------
1.Insert String into the Tree
2.Print Tree Data
3.Total Tree Nodes
4.Exit
Enter Your Choice: 3
Total number of nodes
20
 
---------------------
 
Operations on AA Tree
 
---------------------
1.Insert String into the Tree
2.Print Tree Data
3.Total Tree Nodes
4.Exit
Enter Your Choice: 4
Exiting
 
 
------------------
(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.