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
Sanfoundry Global Education & Learning Series – 1000 C++ Programs.
advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.
Next Steps:
- Get Free Certificate of Merit in Data Structure I
- Participate in Data Structure I Certification Contest
- Become a Top Ranker in Data Structure I
- Take Data Structure I Tests
- Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Related Posts:
- Apply for Data Structure Internship
- Apply for Information Technology Internship
- Practice Design & Analysis of Algorithms MCQ
- Buy Computer Science Books
- Apply for Computer Science Internship