C++ Program to Implement AA Trees

«
»
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. }

advertisement
$ 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
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
advertisement
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