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.

```
/*
```

 * C++ Program to Implement ScapeGoat Tree

```
 */
```
```
#include <iostream>
```
```
#include <cstdlib>
```
```
#include <cmath>
```
```
using namespace std;
```
```
/*
```
```
 * Class SGTNode
```
```
 */
```
```
 
```
```
class SGTNode
```
```
{
```
```
    public:
```
```
        SGTNode *right, *left, *parent;
```
```
        int value;
```
```
        SGTNode()
```
```
        {
```
```
            value = 0;
```
```
            right = NULL;
```
```
            left = NULL;
```
```
            parent = NULL;
```
```
        }
```
```
        SGTNode(int val)
```
```
        {
```
```
            value = val;
```
```
            right = NULL;
```
```
            left = NULL;
```
```
            parent = NULL;
```
```
        }
```
```
};
```
```
 
```
```
 
```
```
/*
```
```
 *   Class ScapeGoatTree
```
```
 */
```
```
 
```
```
class ScapeGoatTree
```
```
{
```
```
    private:
```
```
        SGTNode *root;
```
```
        int n, q;
```
```
    public:
```
```
        ScapeGoatTree()
```
```
        {
```
```
            root = NULL;
```
```
            n = 0;
```
```
        }
```
```
 
```

        /* Function to check if tree is empty */

```
        bool isEmpty()
```
```
        {
```
```
            return root == NULL;
```
```
        }
```
```
 
```
```
        /* Function to clear  tree */
```
```
        void makeEmpty()
```
```
        {
```
```
            root = NULL;
```
```
            n = 0;
```
```
        }
```
```
 
```

        /* Function to count number of nodes recursively */

```
        int size(SGTNode *r)
```
```
        {
```
```
            if (r == NULL)
```
```
                return 0;
```
```
            else
```
```
            {
```
```
                int l = 1;
```
```
                l += size(r->left);
```
```
                l += size(r->right);
```
```
                return l;
```
```
            }
```
```
        }
```
```
 
```

        /* Functions to search for an element */

```
        bool search(int val)
```
```
        {
```
```
            return search(root, val);
```
```
        }
```
```
 
```

        /* Function to search for an element recursively */

        bool search(SGTNode *r, int val)

```
        {
```
```
            bool found = false;
```

            while ((r != NULL) && !found)

```
            {
```
```
                int rval = r->value;
```
```
                if (val < rval)
```
```
                    r = r->left;
```
```
                else if (val > rval)
```
```
                    r = r->right;
```
```
                else
```
```
                {
```
```
                    found = true;
```
```
                    break;
```
```
                }
```
```
                found = search(r, val);
```
```
            }
```
```
            return found;
```
```
        }
```
```
 
```

        /* Function to return current size of tree */

```
        int size()
```
```
        {
```
```
            return n;
```
```
        }
```
```
 
```

        /* Function for inorder traversal */

```
        void inorder()
```
```
        {
```
```
            inorder(root);
```
```
        }
```
```
        void inorder(SGTNode *r)
```
```
        {
```
```
            if (r != NULL)
```
```
            {
```
```
                inorder(r->left);
```
```
                cout<<r->value<<"   ";
```
```
                inorder(r->right);
```
```
            }
```
```
            else
```
```
                return;
```
```
        }
```
```
 
```

        /* Function for preorder traversal */

```
        void preorder()
```
```
        {
```
```
            preorder(root);
```
```
        }
```
```
        void preorder(SGTNode *r)
```
```
        {
```
```
            if (r != NULL)
```
```
            {
```
```
                cout<<r->value<<"   ";
```
```
                preorder(r->left);
```
```
                preorder(r->right);
```
```
            }
```
```
            else
```
```
                return;
```
```
        }
```
```
 
```

        /* Function for postorder traversal */

```
        void postorder()
```
```
        {
```
```
            postorder(root);
```
```
        }
```
```
        void postorder(SGTNode *r)
```
```
        {
```
```
            if (r != NULL)
```
```
            {
```
```
                postorder(r->left);
```
```
                postorder(r->right);
```
```
                cout<<r->value<<"   ";
```
```
            }
```
```
            else
```
```
                return;
```
```
        }
```
```
 
```
```
        static int const log32(int q)
```
```
        {
```

            double const log23 = 2.4663034623764317;

            return (int)ceil(log23 * log(q));

```
        }
```
```
 
```

        /* Function to insert an element */

```
        bool add(int x)
```
```
        {
```

            /* first do basic insertion keeping track of depth */

            SGTNode *u = new SGTNode(x);

```
            int d = addWithDepth(u);
```
```
            if (d > log32(q))
```
```
            {
```

                /* depth exceeded, find scapegoat */

```
                SGTNode *w = u->parent;
```

                while (3 * size(w) <= 2 * size(w->parent))

```
                    w = w->parent;
```
```
                rebuild(w->parent);
```
```
            }
```
```
            return d >= 0;
```
```
        }
```
```
 
```

        /* Function to rebuild tree from node u */

```
        void rebuild(SGTNode *u)
```
```
        {
```
```
            int ns = size(u);
```
```
            SGTNode *p = u->parent;
```

            SGTNode **a = new SGTNode* [ns];

```
            packIntoArray(u, a, 0);
```
```
            if (p == NULL)
```
```
            {
```

                root = buildBalanced(a, 0, ns);

```
                root->parent = NULL;
```
```
            }
```
```
            else if (p->right == u)
```
```
            {
```

                p->right = buildBalanced(a, 0, ns);

```
                p->right->parent = p;
```
```
            }
```
```
            else
```
```
            {
```

                p->left = buildBalanced(a, 0, ns);

```
                p->left->parent = p;
```
```
            }
```
```
        }
```
```
 
```
```
        /* Function to packIntoArray */
```

        int packIntoArray(SGTNode *u, SGTNode *a[], int i)

```
        {
```
```
            if (u == NULL)
```
```
            {
```
```
                return i;
```
```
            }
```

            i = packIntoArray(u->left, a, i);

```
            a[i++] = u;
```

            return packIntoArray(u->right, a, i);

```
        }
```
```
 
```

        /* Function to build balanced nodes */

        SGTNode *buildBalanced(SGTNode **a, int i, int ns)

```
        {
```
```
            if (ns == 0)
```
```
                return NULL;
```
```
            int m = ns / 2;
```

            a[i + m]->left = buildBalanced(a, i, m);

```
            if (a[i + m]->left != NULL)
```

                a[i + m]->left->parent = a[i + m];

            a[i + m]->right = buildBalanced(a, i + m + 1, ns - m - 1);\

            if (a[i + m]->right != NULL)

                a[i + m]->right->parent = a[i + m];

```
            return a[i + m];
```
```
        }
```
```
 
```
```
        /* Function add with depth */
```
```
        int addWithDepth(SGTNode *u)
```
```
        {
```
```
            SGTNode *w = root;
```
```
            if (w == NULL)
```
```
            {
```
```
                root = u;
```
```
                n++;
```
```
                q++;
```
```
                return 0;
```
```
            }
```
```
            bool done = false;
```
```
            int d = 0;
```
```
            do
```
```
            {
```

                if (u->value < w->value)

```
                {
```

                    if (w->left == NULL)

```
                    {
```
```
                        w->left = u;
```
```
                        u->parent = w;
```
```
                        done = true;
```
```
                    }
```
```
                    else
```
```
                    {
```
```
                        w = w->left;
```
```
                    }
```
```
                }
```

                else if (u->value > w->value)

```
                {
```

                    if (w->right == NULL)

```
                    {
```
```
                        w->right = u;
```
```
                        u->parent = w;
```
```
                        done = true;
```
```
                    }
```
```
                    else
```
```
                    {
```
```
                        w = w->right;
```
```
                    }
```
```
                }
```
```
                else
```
```
                    return -1;
```
```
                d++;
```
```
            }
```
```
            while (!done);
```
```
            n++;
```
```
            q++;
```
```
            return d;
```
```
        }
```
```
};
```
```
 
```
```
int main()
```
```
{
```
```
    ScapeGoatTree sgt;
```
```
    cout<<"ScapeGoat Tree Test"<<endl;
```
```
    char ch;
```
```
    int val;
```
```
    /*  Perform tree operations  */
```
```
    do
```
```
    {
```

        cout<<"\nScapeGoat Tree Operations\n";

```
        cout<<"1. Insert "<<endl;
```
```
        cout<<"2. Count nodes"<<endl;
```
```
        cout<<"3. Search"<<endl;
```
```
        cout<<"4. Check empty"<<endl;
```
```
        cout<<"5. Make empty"<<endl;
```
```
        int choice;
```
```
        cout<<"Enter your Choice: ";
```
```
        cin>>choice;
```
```
        switch (choice)
```
```
        {
```
```
        case 1 :
```

            cout<<"Enter integer element to insert: ";

```
            cin>>val;
```
```
            sgt.add(val);
```
```
            break;
```
```
        case 2 :
```

            cout<<"Nodes = " <<sgt.size()<<endl;

```
            break;
```
```
        case 3 :
```

            cout<<"Enter integer element to search: ";

```
            cin>>val;
```
```
            if (sgt.search(val))
```

                cout<<val<<" found in the tree"<<endl;

```
            else
```

                cout<<val<<" not found"<<endl;

```
            break;
```
```
        case 4 :
```
```
            cout<<"Empty status = ";
```
```
            if (sgt.isEmpty())
```

                cout<<"Tree is empty"<<endl;

```
            else
```

                cout<<"Tree is non - empty"<<endl;

```
            break;
```
```
        case 5 :
```
```
            cout<<"\nTree cleared\n";
```
```
            sgt.makeEmpty();
```
```
            break;
```
```
        default :
```
```
            cout<<"Wrong Entry \n ";
```
```
            break;
```
```
        }
```
```
 
```
```
        /*  Display tree*/
```
```
        cout<<"\nPost order : ";
```
```
        sgt.postorder();
```
```
        cout<<"\nPre order : ";
```
```
        sgt.preorder();
```
```
        cout<<"\nIn order : ";
```
```
        sgt.inorder();
```

        cout<<"\nDo you want to continue (Type y or n) \n";

```
        cin>>ch;
```
```
    }
```
```
    while (ch == 'Y'|| ch == 'y');
```
```
    return 0;
```
```
}
```

$ 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