Randomly generate 1,000 unique values in the range of [1-10,000] and insert them
ID: 3583143 • Letter: R
Question
Randomly generate 1,000 unique values in the range of [1-10,000] and insert them into a red black tree. Print height of the tree. Print sum of all values in the tree (should use one of the traversals). Clear the binary search trees. Print whether trees are empty before and after clear operation.
Can you please incorporate this into what is done below?
#include<iostream>
using namespace std;
struct node
{
int key;
node *parent;
char color;
node *left;
node *right;
};
/*
* @post class RBtree defined
*/
class RBtree
{
node *root;
node *q;
public :
RBtree()
{
q=NULL;
root=NULL;
}
void insert();
void insertfix(node *);
void leftrotate(node *);
void rightrotate(node *);
void del();
node* successor(node *);
void delfix(node *);
void disp();
void display( node *);
void search();
};
/*
* @pre class RB tree
* @post inserts node into RB tree
*/
void RBtree::insert()
{
int z,i=0;
cout<<"Enter key of the node to be inserted: ";
cin>>z;
node *p,*q;
node *t=new node;
t->key=z;
t->left=NULL;
t->right=NULL;
t->color='r';
p=root;
q=NULL;
if(root==NULL)
{
root=t;
t->parent=NULL;
}
else
{
while(p!=NULL)
{
q=p;
if(p->key<t->key)
p=p->right;
else
p=p->left;
}
t->parent=q;
if(q->key<t->key)
q->right=t;
else
q->left=t;
}
insertfix(t);
}
void RBtree::insertfix(node *t)
{
node *u;
if(root==t)
{
t->color='b';
return;
}
while(t->parent!=NULL&&t->parent->color=='r')
{
node *g=t->parent->parent;
if(g->left==t->parent)
{
if(g->right!=NULL)
{
u=g->right;
if(u->color=='r')
{
t->parent->color='b';
u->color='b';
g->color='r';
t=g;
}
}
else
{
if(t->parent->right==t)
{
t=t->parent;
leftrotate(t);
}
t->parent->color='b';
g->color='r';
rightrotate(g);
}
}
else
{
if(g->left!=NULL)
{
u=g->left;
if(u->color=='r')
{
t->parent->color='b';
u->color='b';
g->color='r';
t=g;
}
}
else
{
if(t->parent->left==t)
{
t=t->parent;
rightrotate(t);
}
t->parent->color='b';
g->color='r';
leftrotate(g);
}
}
root->color='b';
}
}
/*
* @pre Class RB tree
*
* @post deletes node from RB tree
*/
void RBtree::del()
{
if(root==NULL)
{
cout<<" Empty Tree." ;
return ;
}
int x;
cout<<" Enter the key of the node to be deleted: ";
cin>>x;
node *p;
p=root;
node *y=NULL;
node *q=NULL;
int found=0;
while(p!=NULL&&found==0)
{
if(p->key==x)
found=1;
if(found==0)
{
if(p->key<x)
p=p->right;
else
p=p->left;
}
}
if(found==0)
{
cout<<" Element Not Found.";
return ;
}
else
{
cout<<" Deleted Element: "<<p->key;
cout<<" Color: ";
if(p->color=='b')
cout<<"Black ";
else
cout<<"Red ";
if(p->parent!=NULL)
cout<<" Parent: "<<p->parent->key;
else
cout<<" There is no parent of the node. ";
if(p->right!=NULL)
cout<<" Right Child: "<<p->right->key;
else
cout<<" There is no right child of the node. ";
if(p->left!=NULL)
cout<<" Left Child: "<<p->left->key;
else
cout<<" There is no left child of the node. ";
cout<<" Node Deleted.";
if(p->left==NULL||p->right==NULL)
y=p;
else
y=successor(p);
if(y->left!=NULL)
q=y->left;
else
{
if(y->right!=NULL)
q=y->right;
else
q=NULL;
}
if(q!=NULL)
q->parent=y->parent;
if(y->parent==NULL)
root=q;
else
{
if(y==y->parent->left)
y->parent->left=q;
else
y->parent->right=q;
}
if(y!=p)
{
p->color=y->color;
p->key=y->key;
}
if(y->color=='b')
delfix(q);
}
}
void RBtree::delfix(node *p)
{
node *s;
while(p!=root&&p->color=='b')
{
if(p->parent->left==p)
{
s=p->parent->right;
if(s->color=='r')
{
s->color='b';
p->parent->color='r';
leftrotate(p->parent);
s=p->parent->right;
}
if(s->right->color=='b'&&s->left->color=='b')
{
s->color='r';
p=p->parent;
}
else
{
if(s->right->color=='b')
{
s->left->color=='b';
s->color='r';
rightrotate(s);
s=p->parent->right;
}
s->color=p->parent->color;
p->parent->color='b';
s->right->color='b';
leftrotate(p->parent);
p=root;
}
}
else
{
s=p->parent->left;
if(s->color=='r')
{
s->color='b';
p->parent->color='r';
rightrotate(p->parent);
s=p->parent->left;
}
if(s->left->color=='b'&&s->right->color=='b')
{
s->color='r';
p=p->parent;
}
else
{
if(s->left->color=='b')
{
s->right->color='b';
s->color='r';
leftrotate(s);
s=p->parent->left;
}
s->color=p->parent->color;
p->parent->color='b';
s->left->color='b';
rightrotate(p->parent);
p=root;
}
}
p->color='b';
root->color='b';
}
}
void RBtree::leftrotate(node *p)
{
if(p->right==NULL)
return ;
else
{
node *y=p->right;
if(y->left!=NULL)
{
p->right=y->left;
y->left->parent=p;
}
else
p->right=NULL;
if(p->parent!=NULL)
y->parent=p->parent;
if(p->parent==NULL)
root=y;
else
{
if(p==p->parent->left)
p->parent->left=y;
else
p->parent->right=y;
}
y->left=p;
p->parent=y;
}
}
void RBtree::rightrotate(node *p)
{
if(p->left==NULL)
return ;
else
{
node *y=p->left;
if(y->right!=NULL)
{
p->left=y->right;
y->right->parent=p;
}
else
p->left=NULL;
if(p->parent!=NULL)
y->parent=p->parent;
if(p->parent==NULL)
root=y;
else
{
if(p==p->parent->left)
p->parent->left=y;
else
p->parent->right=y;
}
y->right=p;
p->parent=y;
}
}
node* RBtree::successor(node *p)
{
node *y=NULL;
if(p->left!=NULL)
{
y=p->left;
while(y->right!=NULL)
y=y->right;
}
else
{
y=p->right;
while(y->left!=NULL)
y=y->left;
}
return y;
}
void RBtree::disp()
{
display(root);
}
/*********************
*Pulled these from main
*Can't define a function in a function. whoops!
*********************/
/*
* @pre Class RBtree
*
* @post displays current state of RB tree
*/
void RBtree::display(node *p)
{
if(root==NULL)
{
cout<<" Empty Tree.";
return ;
}
if(p!=NULL)
{
cout<<" NODE: ";
cout<<" Key: "<<p->key;
cout<<" Color: ";
if(p->color=='b')
cout<<"Black";
else
cout<<"Red";
if(p->parent!=NULL)
cout<<" Parent: "<<p->parent->key;
else
cout<<" There is no parent of the node. ";
if(p->right!=NULL)
cout<<" Right Child: "<<p->right->key;
else
cout<<" There is no right child of the node. ";
if(p->left!=NULL)
cout<<" Left Child: "<<p->left->key;
else
cout<<" There is no left child of the node. ";
cout<<endl;
if(p->left)
{
cout<<" Left: ";
display(p->left);
}
/*else
cout<<" No Left Child. ";*/
if(p->right)
{
cout<<" Right: ";
display(p->right);
}
/*else
cout<<" No Right Child. "*/
}
}
/*
* @pre class RB tree
*
* @post finds node in the RB tree and displays it to the user
*/
void RBtree::search()
{
if(root==NULL)
{
cout<<" Empty Tree " ;
return ;
}
int x;
cout<<" Enter key of the node to be searched: ";
cin>>x;
node *p=root;
int found=0;
while(p!=NULL&& found==0)
{
if(p->key==x)
found=1;
if(found==0)
{
if(p->key<x)
p=p->right;
else
p=p->left;
}
}
if(found==0)
cout<<" Element Not Found.";
else
{
cout<<" FOUND NODE: ";
cout<<" Key: "<<p->key;
cout<<" Colour: ";
if(p->color=='b')
cout<<"Black";
else
cout<<"Red";
if(p->parent!=NULL)
cout<<" Parent: "<<p->parent->key;
else
cout<<" There is no parent of the node. ";
if(p->right!=NULL)
cout<<" Right Child: "<<p->right->key;
else
cout<<" There is no right child of the node. ";
if(p->left!=NULL)
cout<<" Left Child: "<<p->left->key;
else
cout<<" There is no left child of the node. ";
cout<<endl;
}
}
/*
*Main function Starts Here *****
*/
int main()
{
int ch,y=0;
RBtree obj;
do
{
cout<<" RED BLACK TREE " ;
cout<<" 1. Insert in the tree ";
cout<<" 2. Delete a node from the tree";
cout<<" 3. Search for an element in the tree";
cout<<" 4. Display the tree ";
cout<<" 5. Exit " ;
cout<<" Enter Your Choice: ";
cin>>ch;
switch(ch)
{
case 1 : obj.insert();
cout<<" Node Inserted. ";
break;
case 2 : obj.del();
break;
case 3 : obj.search();
break;
case 4 : obj.disp();
break;
case 5 : y=1;
break;
default : cout<<" Enter a Valid Choice.";
}
cout<<endl;
}
while(y!=1);
return 1;
}
Explanation / Answer
#include<iostream>
using namespace std;
struct node
{
int key;
node *parent;
char color;
node *left;
node *right;
};
/*
* @post class RBtree defined
*/
class RBtree
{
node *root;
node *q;
int sum;
public:
RBtree()
{
q=NULL;
root=NULL;
sum=0;
}
void insert();
void insertfix(node *);
void leftrotate(node *);
void rightrotate(node *);
void del();
node* successor(node *);
void delfix(node *);
void disp();
void display( node *);
void search();
void hei();
int height(node* );
void inorder();
void in_order_sum(node *p);
void clear();
node* pos_clear(node*);
};
/*
* @pre class RB tree
* @post inserts node into RB tree
*/
void RBtree::clear()
{
pos_clear(root);
cout<<"Tree is cleared ";
}
node* RBtree::pos_clear(node *p)
{
if (p!=NULL)
{
in_order_sum(p->left);
in_order_sum(p->right);
p=NULL;
return p;
}
return p;
}
void RBtree::inorder()
{
in_order_sum(root);
cout<<"Sum of values is "<<sum<<endl;
}
void RBtree::in_order_sum(node *p)
{
if (!p)
{
return;
}
in_order_sum(p->left);
sum = sum + p->key;
in_order_sum(p->right);
}
void RBtree::hei()
{
cout<<"height is "<<height(root)<<endl;
}
int RBtree::height(node *node)
{
if (!node) return -1;
return 1 + max(height(node->left), height(node->right));
}
void RBtree::insert()
{
int z,i=0;
cout<<"Enter key of the node to be inserted: ";
cin>>z;
node *p,*q;
node *t=new node;
t->key=z;
t->left=NULL;
t->right=NULL;
t->color='r';
p=root;
q=NULL;
if(root==NULL)
{
root=t;
t->parent=NULL;
}
else
{
while(p!=NULL)
{
q=p;
if(p->key<t->key)
p=p->right;
else
p=p->left;
}
t->parent=q;
if(q->key<t->key)
q->right=t;
else
q->left=t;
}
insertfix(t);
}
void RBtree::insertfix(node *t)
{
node *u;
if(root==t)
{
t->color='b';
return;
}
while(t->parent!=NULL&&t->parent->color=='r')
{
node *g=t->parent->parent;
if(g->left==t->parent)
{
if(g->right!=NULL)
{
u=g->right;
if(u->color=='r')
{
t->parent->color='b';
u->color='b';
g->color='r';
t=g;
}
}
else
{
if(t->parent->right==t)
{
t=t->parent;
leftrotate(t);
}
t->parent->color='b';
g->color='r';
rightrotate(g);
}
}
else
{
if(g->left!=NULL)
{
u=g->left;
if(u->color=='r')
{
t->parent->color='b';
u->color='b';
g->color='r';
t=g;
}
}
else
{
if(t->parent->left==t)
{
t=t->parent;
rightrotate(t);
}
t->parent->color='b';
g->color='r';
leftrotate(g);
}
}
root->color='b';
}
}
/*
* @pre Class RB tree
*
* @post deletes node from RB tree
*/
void RBtree::del()
{
if(root==NULL)
{
cout<<" Empty Tree." ;
return ;
}
int x;
cout<<" Enter the key of the node to be deleted: ";
cin>>x;
node *p;
p=root;
node *y=NULL;
node *q=NULL;
int found=0;
while(p!=NULL&&found==0)
{
if(p->key==x)
found=1;
if(found==0)
{
if(p->key<x)
p=p->right;
else
p=p->left;
}
}
if(found==0)
{
cout<<" Element Not Found.";
return ;
}
else
{
cout<<" Deleted Element: "<<p->key;
cout<<" Color: ";
if(p->color=='b')
cout<<"Black ";
else
cout<<"Red ";
if(p->parent!=NULL)
cout<<" Parent: "<<p->parent->key;
else
cout<<" There is no parent of the node. ";
if(p->right!=NULL)
cout<<" Right Child: "<<p->right->key;
else
cout<<" There is no right child of the node. ";
if(p->left!=NULL)
cout<<" Left Child: "<<p->left->key;
else
cout<<" There is no left child of the node. ";
cout<<" Node Deleted.";
if(p->left==NULL||p->right==NULL)
y=p;
else
y=successor(p);
if(y->left!=NULL)
q=y->left;
else
{
if(y->right!=NULL)
q=y->right;
else
q=NULL;
}
if(q!=NULL)
q->parent=y->parent;
if(y->parent==NULL)
root=q;
else
{
if(y==y->parent->left)
y->parent->left=q;
else
y->parent->right=q;
}
if(y!=p)
{
p->color=y->color;
p->key=y->key;
}
if(y->color=='b')
delfix(q);
}
}
void RBtree::delfix(node *p)
{
node *s;
while(p!=root&&p->color=='b')
{
if(p->parent->left==p)
{
s=p->parent->right;
if(s->color=='r')
{
s->color='b';
p->parent->color='r';
leftrotate(p->parent);
s=p->parent->right;
}
if(s->right->color=='b'&&s->left->color=='b')
{
s->color='r';
p=p->parent;
}
else
{
if(s->right->color=='b')
{
s->left->color=='b';
s->color='r';
rightrotate(s);
s=p->parent->right;
}
s->color=p->parent->color;
p->parent->color='b';
s->right->color='b';
leftrotate(p->parent);
p=root;
}
}
else
{
s=p->parent->left;
if(s->color=='r')
{
s->color='b';
p->parent->color='r';
rightrotate(p->parent);
s=p->parent->left;
}
if(s->left->color=='b'&&s->right->color=='b')
{
s->color='r';
p=p->parent;
}
else
{
if(s->left->color=='b')
{
s->right->color='b';
s->color='r';
leftrotate(s);
s=p->parent->left;
}
s->color=p->parent->color;
p->parent->color='b';
s->left->color='b';
rightrotate(p->parent);
p=root;
}
}
p->color='b';
root->color='b';
}
}
void RBtree::leftrotate(node *p)
{
if(p->right==NULL)
return ;
else
{
node *y=p->right;
if(y->left!=NULL)
{
p->right=y->left;
y->left->parent=p;
}
else
p->right=NULL;
if(p->parent!=NULL)
y->parent=p->parent;
if(p->parent==NULL)
root=y;
else
{
if(p==p->parent->left)
p->parent->left=y;
else
p->parent->right=y;
}
y->left=p;
p->parent=y;
}
}
void RBtree::rightrotate(node *p)
{
if(p->left==NULL)
return ;
else
{
node *y=p->left;
if(y->right!=NULL)
{
p->left=y->right;
y->right->parent=p;
}
else
p->left=NULL;
if(p->parent!=NULL)
y->parent=p->parent;
if(p->parent==NULL)
root=y;
else
{
if(p==p->parent->left)
p->parent->left=y;
else
p->parent->right=y;
}
y->right=p;
p->parent=y;
}
}
node* RBtree::successor(node *p)
{
node *y=NULL;
if(p->left!=NULL)
{
y=p->left;
while(y->right!=NULL)
y=y->right;
}
else
{
y=p->right;
while(y->left!=NULL)
y=y->left;
}
return y;
}
void RBtree::disp()
{
display(root);
}
/*********************
*Pulled these from main
*Can't define a function in a function. whoops!
*********************/
/*
* @pre Class RBtree
*
* @post displays current state of RB tree
*/
void RBtree::display(node *p)
{
if(root==NULL)
{
cout<<" Empty Tree.";
return ;
}
if(p!=NULL)
{
cout<<" NODE: ";
cout<<" Key: "<<p->key;
cout<<" Color: ";
if(p->color=='b')
cout<<"Black";
else
cout<<"Red";
if(p->parent!=NULL)
cout<<" Parent: "<<p->parent->key;
else
cout<<" There is no parent of the node. ";
if(p->right!=NULL)
cout<<" Right Child: "<<p->right->key;
else
cout<<" There is no right child of the node. ";
if(p->left!=NULL)
cout<<" Left Child: "<<p->left->key;
else
cout<<" There is no left child of the node. ";
cout<<endl;
if(p->left)
{
cout<<" Left: ";
display(p->left);
}
/*else
cout<<" No Left Child. ";*/
if(p->right)
{
cout<<" Right: ";
display(p->right);
}
/*else
cout<<" No Right Child. "*/
}
}
/*
* @pre class RB tree
*
* @post finds node in the RB tree and displays it to the user
*/
void RBtree::search()
{
if(root==NULL)
{
cout<<" Empty Tree " ;
return ;
}
int x;
cout<<" Enter key of the node to be searched: ";
cin>>x;
node *p=root;
int found=0;
while(p!=NULL&& found==0)
{
if(p->key==x)
found=1;
if(found==0)
{
if(p->key<x)
p=p->right;
else
p=p->left;
}
}
if(found==0)
cout<<" Element Not Found.";
else
{
cout<<" FOUND NODE: ";
cout<<" Key: "<<p->key;
cout<<" Colour: ";
if(p->color=='b')
cout<<"Black";
else
cout<<"Red";
if(p->parent!=NULL)
cout<<" Parent: "<<p->parent->key;
else
cout<<" There is no parent of the node. ";
if(p->right!=NULL)
cout<<" Right Child: "<<p->right->key;
else
cout<<" There is no right child of the node. ";
if(p->left!=NULL)
cout<<" Left Child: "<<p->left->key;
else
cout<<" There is no left child of the node. ";
cout<<endl;
}
}
/*
*Main function Starts Here *****
*/
int main()
{
int ch,y=0;
RBtree obj;
do
{
cout<<" RED BLACK TREE " ;
cout<<" 1. Insert in the tree ";
cout<<" 2. Delete a node from the tree";
cout<<" 3. Search for an element in the tree";
cout<<" 4. Display the tree ";
cout<<" 5. Height OF the tree ";
cout<<" 6.Sum of all values in the tree ";
cout<<" 7.clear binary tree ";
cout<<" 8. Exit ";
cout<<" Enter Your Choice: ";
cin>>ch;
switch(ch)
{
case 1 : obj.insert();
cout<<" Node Inserted. ";
break;
case 2 : obj.del();
break;
case 3 : obj.search();
break;
case 4 : obj.disp();
break;
case 5:obj.hei();
break;
case 6:obj.inorder();
break;
case 7: obj.clear();
break;
case 8: y=1;
break;
default : cout<<" Enter a Valid Choice.";
}
cout<<endl;
}
while(y!=1);
return 1;
}
===============================================================
Output:
akshay@akshay-Inspiron-3537:~/Chegg$ g++ rbtree.cpp
akshay@akshay-Inspiron-3537:~/Chegg$ ./a.out
RED BLACK TREE
1. Insert in the tree
2. Delete a node from the tree
3. Search for an element in the tree
4. Display the tree
5. Height OF the tree
6.Sum of all values in the tree
7.clear binary tree
8. Exit
Enter Your Choice: 1
Enter key of the node to be inserted: 1
Node Inserted.
RED BLACK TREE
1. Insert in the tree
2. Delete a node from the tree
3. Search for an element in the tree
4. Display the tree
5. Height OF the tree
6.Sum of all values in the tree
7.clear binary tree
8. Exit
Enter Your Choice: 1
Enter key of the node to be inserted: 2
Node Inserted.
RED BLACK TREE
1. Insert in the tree
2. Delete a node from the tree
3. Search for an element in the tree
4. Display the tree
5. Height OF the tree
6.Sum of all values in the tree
7.clear binary tree
8. Exit
Enter Your Choice: 1
Enter key of the node to be inserted: 3
Node Inserted.
RED BLACK TREE
1. Insert in the tree
2. Delete a node from the tree
3. Search for an element in the tree
4. Display the tree
5. Height OF the tree
6.Sum of all values in the tree
7.clear binary tree
8. Exit
Enter Your Choice: 5
height is 1
RED BLACK TREE
1. Insert in the tree
2. Delete a node from the tree
3. Search for an element in the tree
4. Display the tree
5. Height OF the tree
6.Sum of all values in the tree
7.clear binary tree
8. Exit
Enter Your Choice: 6
Sum of values is 6
RED BLACK TREE
1. Insert in the tree
2. Delete a node from the tree
3. Search for an element in the tree
4. Display the tree
5. Height OF the tree
6.Sum of all values in the tree
7.clear binary tree
8. Exit
Enter Your Choice: 7
Tree is cleared
RED BLACK TREE
1. Insert in the tree
2. Delete a node from the tree
3. Search for an element in the tree
4. Display the tree
5. Height OF the tree
6.Sum of all values in the tree
7.clear binary tree
8. Exit
Enter Your Choice: 8
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.