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

$ 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
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.