C++ Program to Implement ScapeGoat Tree

«
»
This C++ Program demonstrates the implementation of Space Goat Tree.

Here is source code of the C++ Program to demonstrate the implementation of Space Goat Tree. 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 ScapeGoat Tree
  3.  */
  4. #include <iostream>
  5. #include <cstdlib>
  6. #include <cmath>
  7. using namespace std;
  8. /*
  9.  * Class SGTNode
  10.  */
  11.  
  12. class SGTNode
  13. {
  14.     public:
  15.         SGTNode *right, *left, *parent;
  16.         int value;
  17.         SGTNode()
  18.         {
  19.             value = 0;
  20.             right = NULL;
  21.             left = NULL;
  22.             parent = NULL;
  23.         }
  24.         SGTNode(int val)
  25.         {
  26.             value = val;
  27.             right = NULL;
  28.             left = NULL;
  29.             parent = NULL;
  30.         }
  31. };
  32.  
  33.  
  34. /*
  35.  *   Class ScapeGoatTree
  36.  */
  37.  
  38. class ScapeGoatTree
  39. {
  40.     private:
  41.         SGTNode *root;
  42.         int n, q;
  43.     public:
  44.         ScapeGoatTree()
  45.         {
  46.             root = NULL;
  47.             n = 0;
  48.         }
  49.  
  50.         /* Function to check if tree is empty */
  51.         bool isEmpty()
  52.         {
  53.             return root == NULL;
  54.         }
  55.  
  56.         /* Function to clear  tree */
  57.         void makeEmpty()
  58.         {
  59.             root = NULL;
  60.             n = 0;
  61.         }
  62.  
  63.         /* Function to count number of nodes recursively */
  64.         int size(SGTNode *r)
  65.         {
  66.             if (r == NULL)
  67.                 return 0;
  68.             else
  69.             {
  70.                 int l = 1;
  71.                 l += size(r->left);
  72.                 l += size(r->right);
  73.                 return l;
  74.             }
  75.         }
  76.  
  77.         /* Functions to search for an element */
  78.         bool search(int val)
  79.         {
  80.             return search(root, val);
  81.         }
  82.  
  83.         /* Function to search for an element recursively */
  84.         bool search(SGTNode *r, int val)
  85.         {
  86.             bool found = false;
  87.             while ((r != NULL) && !found)
  88.             {
  89.                 int rval = r->value;
  90.                 if (val < rval)
  91.                     r = r->left;
  92.                 else if (val > rval)
  93.                     r = r->right;
  94.                 else
  95.                 {
  96.                     found = true;
  97.                     break;
  98.                 }
  99.                 found = search(r, val);
  100.             }
  101.             return found;
  102.         }
  103.  
  104.         /* Function to return current size of tree */
  105.         int size()
  106.         {
  107.             return n;
  108.         }
  109.  
  110.         /* Function for inorder traversal */
  111.         void inorder()
  112.         {
  113.             inorder(root);
  114.         }
  115.         void inorder(SGTNode *r)
  116.         {
  117.             if (r != NULL)
  118.             {
  119.                 inorder(r->left);
  120.                 cout<<r->value<<"   ";
  121.                 inorder(r->right);
  122.             }
  123.             else
  124.                 return;
  125.         }
  126.  
  127.         /* Function for preorder traversal */
  128.         void preorder()
  129.         {
  130.             preorder(root);
  131.         }
  132.         void preorder(SGTNode *r)
  133.         {
  134.             if (r != NULL)
  135.             {
  136.                 cout<<r->value<<"   ";
  137.                 preorder(r->left);
  138.                 preorder(r->right);
  139.             }
  140.             else
  141.                 return;
  142.         }
  143.  
  144.         /* Function for postorder traversal */
  145.         void postorder()
  146.         {
  147.             postorder(root);
  148.         }
  149.         void postorder(SGTNode *r)
  150.         {
  151.             if (r != NULL)
  152.             {
  153.                 postorder(r->left);
  154.                 postorder(r->right);
  155.                 cout<<r->value<<"   ";
  156.             }
  157.             else
  158.                 return;
  159.         }
  160.  
  161.         static int const log32(int q)
  162.         {
  163.             double const log23 = 2.4663034623764317;
  164.             return (int)ceil(log23 * log(q));
  165.         }
  166.  
  167.         /* Function to insert an element */
  168.         bool add(int x)
  169.         {
  170.             /* first do basic insertion keeping track of depth */
  171.             SGTNode *u = new SGTNode(x);
  172.             int d = addWithDepth(u);
  173.             if (d > log32(q))
  174.             {
  175.                 /* depth exceeded, find scapegoat */
  176.                 SGTNode *w = u->parent;
  177.                 while (3 * size(w) <= 2 * size(w->parent))
  178.                     w = w->parent;
  179.                 rebuild(w->parent);
  180.             }
  181.             return d >= 0;
  182.         }
  183.  
  184.         /* Function to rebuild tree from node u */
  185.         void rebuild(SGTNode *u)
  186.         {
  187.             int ns = size(u);
  188.             SGTNode *p = u->parent;
  189.             SGTNode **a = new SGTNode* [ns];
  190.             packIntoArray(u, a, 0);
  191.             if (p == NULL)
  192.             {
  193.                 root = buildBalanced(a, 0, ns);
  194.                 root->parent = NULL;
  195.             }
  196.             else if (p->right == u)
  197.             {
  198.                 p->right = buildBalanced(a, 0, ns);
  199.                 p->right->parent = p;
  200.             }
  201.             else
  202.             {
  203.                 p->left = buildBalanced(a, 0, ns);
  204.                 p->left->parent = p;
  205.             }
  206.         }
  207.  
  208.         /* Function to packIntoArray */
  209.         int packIntoArray(SGTNode *u, SGTNode *a[], int i)
  210.         {
  211.             if (u == NULL)
  212.             {
  213.                 return i;
  214.             }
  215.             i = packIntoArray(u->left, a, i);
  216.             a[i++] = u;
  217.             return packIntoArray(u->right, a, i);
  218.         }
  219.  
  220.         /* Function to build balanced nodes */
  221.         SGTNode *buildBalanced(SGTNode **a, int i, int ns)
  222.         {
  223.             if (ns == 0)
  224.                 return NULL;
  225.             int m = ns / 2;
  226.             a[i + m]->left = buildBalanced(a, i, m);
  227.             if (a[i + m]->left != NULL)
  228.                 a[i + m]->left->parent = a[i + m];
  229.             a[i + m]->right = buildBalanced(a, i + m + 1, ns - m - 1);\
  230.             if (a[i + m]->right != NULL)
  231.                 a[i + m]->right->parent = a[i + m];
  232.             return a[i + m];
  233.         }
  234.  
  235.         /* Function add with depth */
  236.         int addWithDepth(SGTNode *u)
  237.         {
  238.             SGTNode *w = root;
  239.             if (w == NULL)
  240.             {
  241.                 root = u;
  242.                 n++;
  243.                 q++;
  244.                 return 0;
  245.             }
  246.             bool done = false;
  247.             int d = 0;
  248.             do
  249.             {
  250.                 if (u->value < w->value)
  251.                 {
  252.                     if (w->left == NULL)
  253.                     {
  254.                         w->left = u;
  255.                         u->parent = w;
  256.                         done = true;
  257.                     }
  258.                     else
  259.                     {
  260.                         w = w->left;
  261.                     }
  262.                 }
  263.                 else if (u->value > w->value)
  264.                 {
  265.                     if (w->right == NULL)
  266.                     {
  267.                         w->right = u;
  268.                         u->parent = w;
  269.                         done = true;
  270.                     }
  271.                     else
  272.                     {
  273.                         w = w->right;
  274.                     }
  275.                 }
  276.                 else
  277.                     return -1;
  278.                 d++;
  279.             }
  280.             while (!done);
  281.             n++;
  282.             q++;
  283.             return d;
  284.         }
  285. };
  286.  
  287. int main()
  288. {
  289.     ScapeGoatTree sgt;
  290.     cout<<"ScapeGoat Tree Test"<<endl;
  291.     char ch;
  292.     int val;
  293.     /*  Perform tree operations  */
  294.     do
  295.     {
  296.         cout<<"\nScapeGoat Tree Operations\n";
  297.         cout<<"1. Insert "<<endl;
  298.         cout<<"2. Count nodes"<<endl;
  299.         cout<<"3. Search"<<endl;
  300.         cout<<"4. Check empty"<<endl;
  301.         cout<<"5. Make empty"<<endl;
  302.         int choice;
  303.         cout<<"Enter your Choice: ";
  304.         cin>>choice;
  305.         switch (choice)
  306.         {
  307.         case 1 :
  308.             cout<<"Enter integer element to insert: ";
  309.             cin>>val;
  310.             sgt.add(val);
  311.             break;
  312.         case 2 :
  313.             cout<<"Nodes = " <<sgt.size()<<endl;
  314.             break;
  315.         case 3 :
  316.             cout<<"Enter integer element to search: ";
  317.             cin>>val;
  318.             if (sgt.search(val))
  319.                 cout<<val<<" found in the tree"<<endl;
  320.             else
  321.                 cout<<val<<" not found"<<endl;
  322.             break;
  323.         case 4 :
  324.             cout<<"Empty status = ";
  325.             if (sgt.isEmpty())
  326.                 cout<<"Tree is empty"<<endl;
  327.             else
  328.                 cout<<"Tree is non - empty"<<endl;
  329.             break;
  330.         case 5 :
  331.             cout<<"\nTree cleared\n";
  332.             sgt.makeEmpty();
  333.             break;
  334.         default :
  335.             cout<<"Wrong Entry \n ";
  336.             break;
  337.         }
  338.  
  339.         /*  Display tree*/
  340.         cout<<"\nPost order : ";
  341.         sgt.postorder();
  342.         cout<<"\nPre order : ";
  343.         sgt.preorder();
  344.         cout<<"\nIn order : ";
  345.         sgt.inorder();
  346.         cout<<"\nDo you want to continue (Type y or n) \n";
  347.         cin>>ch;
  348.     }
  349.     while (ch == 'Y'|| ch == 'y');
  350.     return 0;
  351. }

advertisement
$ g++ sgt.cpp
$ a.out
ScapeGoat Tree Test
 
ScapeGoat Tree Operations
1. Insert
2. Count nodes
3. Search
4. Check empty
5. Make empty
Enter your Choice: 1
Enter integer element to insert: 34
 
Post order : 34
Pre order : 34
In order : 34
Do you want to continue (Type y or n)
y
 
ScapeGoat Tree Operations
1. Insert
2. Count nodes
3. Search
4. Check empty
5. Make empty
Enter your Choice: 1
Enter integer element to insert: 67
 
Post order : 67   34
Pre order : 34   67
In order : 34   67
Do you want to continue (Type y or n)
y
 
ScapeGoat Tree Operations
1. Insert
2. Count nodes
3. Search
4. Check empty
5. Make empty
Enter your Choice: 1
Enter integer element to insert: 11
 
Post order : 11   67   34
Pre order : 34   11   67
In order : 11   34   67
Do you want to continue (Type y or n)
y
 
ScapeGoat Tree Operations
1. Insert
2. Count nodes
3. Search
4. Check empty
5. Make empty
Enter your Choice: 1
Enter integer element to insert: 24
 
Post order : 24   11   67   34
Pre order : 34   11   24   67
In order : 11   24   34   67
Do you want to continue (Type y or n)
y
 
ScapeGoat Tree Operations
1. Insert
2. Count nodes
3. Search
4. Check empty
5. Make empty
Enter your Choice: 1
Enter integer element to insert: 6
 
Post order : 6   24   11   67   34
Pre order : 34   11   6   24   67
In order : 6   11   24   34   67
Do you want to continue (Type y or n)
y
 
ScapeGoat Tree Operations
1. Insert
2. Count nodes
3. Search
4. Check empty
5. Make empty
Enter your Choice: 1
Enter integer element to insert: 97
 
Post order : 6   24   11   97   67   34
Pre order : 34   11   6   24   67   97
In order : 6   11   24   34   67   97
Do you want to continue (Type y or n)
y
 
ScapeGoat Tree Operations
1. Insert
2. Count nodes
3. Search
4. Check empty
5. Make empty
Enter your Choice: 1
Enter integer element to insert: 12
 
Post order : 6   12   24   11   97   67   34
Pre order : 34   11   6   24   12   67   97
In order : 6   11   12   24   34   67   97
Do you want to continue (Type y or n)
y
 
ScapeGoat Tree Operations
1. Insert
2. Count nodes
3. Search
4. Check empty
5. Make empty
Enter your Choice: 1
Enter integer element to insert: 57
 
Post order : 6   12   24   11   57   97   67   34
Pre order : 34   11   6   24   12   67   57   97
In order : 6   11   12   24   34   57   67   97
Do you want to continue (Type y or n)
y
 
ScapeGoat Tree Operations
1. Insert
2. Count nodes
3. Search
4. Check empty
5. Make empty
Enter your Choice: 2
Nodes = 8
 
Post order : 6   12   24   11   57   97   67   34
Pre order : 34   11   6   24   12   67   57   97
In order : 6   11   12   24   34   57   67   97
Do you want to continue (Type y or n)
y
 
ScapeGoat Tree Operations
1. Insert
2. Count nodes
3. Search
4. Check empty
5. Make empty
Enter your Choice: 3
Enter integer element to search: 57
57 found in the tree
 
Post order : 6   12   24   11   57   97   67   34
Pre order : 34   11   6   24   12   67   57   97
In order : 6   11   12   24   34   57   67   97
Do you want to continue (Type y or n)
y
 
ScapeGoat Tree Operations
1. Insert
2. Count nodes
3. Search
4. Check empty
5. Make empty
Enter your Choice: 5
 
Tree cleared
 
Post order :
Pre order :
In order :
Do you want to continue (Type y or n)
n
 
 
------------------
(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
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