C++- Need to take this code and implement a red-black Tree using the existing co
ID: 3916168 • Letter: C
Question
C++- Need to take this code and implement a red-black Tree using the existing code and include an output function to demonstrate that the red-black tree rules are being maintained.
Thanks! the code is below:
#include <iostream>
#include <stack>
#include <ctime>
using namespace std;
template <class T>
class BST;
template <class T>
class BSTNode{
BSTNode<T>* left;
BSTNode<T>* right;
BSTNode<T>* parent;
T data;
public:
BSTNode(T newdata = T(), BSTNode<T>* newparent = nullptr, BSTNode<T>* newleft = nullptr, BSTNode<T>* newright = nullptr){
data = newdata; parent = newparent; left = newleft; right = newright;
}
friend class BST < T > ;
};
template <class T>
class BST{
BSTNode<T>* root;
int countOfNodes;
BSTNode<T>* recursiveCopy(const BSTNode<T>* rhs);
void printInOrder(BSTNode<T>* ptr);
public:
BST() :root(nullptr){}
BST(const BST<T>& rhs) :root(nullptr){ *this = rhs; }
~BST(){ clear(); }
bool isEmpty(){ return root == nullptr; }
void remove(const T& val){ remove(find(val)); }
bool findInTree(const T& val){ return find(val) != nullptr; }
void clear(){ while (!isEmpty()) remove(root); }
int size(){ return countOfNodes; }
BST<T>& operator=(const BST<T>& rhs);
void insert(const T&);
void remove(BSTNode<T>* ptr);
BSTNode<T>* find(const T&);
void printInOrder(){ if (root!=nullptr) printInOrder(root); }
};
template<class T>
void BST<T>::printInOrder(BSTNode<T>* ptr){
if (ptr->left != nullptr)
printInOrder(ptr->left);
cout << ptr->data<<endl;
if (ptr->right != nullptr)
printInOrder(ptr->right);
}
template <class T>
BSTNode<T>* BST<T>::find(const T& val){
BSTNode<T>* temp = root;
while (temp != nullptr && temp->data != val){
if (val < temp->data)
temp = temp->left;
else
temp = temp->right;
}
return temp;
}
template <class T>
void BST<T>::remove(BSTNode<T>* ptr){
if (ptr == nullptr) //someone asked me to remove a value that isnt in the tree... okay, done!
return;
if (countOfNodes == 1 && ptr == root){ //this is the last node
countOfNodes--;
delete root;
root = nullptr;
}
else if (ptr->left == nullptr && ptr->right == nullptr){ //no children, delete and update parent
BSTNode<T>* parent = ptr->parent;
if (parent != nullptr){ //update the parent's child pointer
if (ptr == parent->left)
parent->left = nullptr;
else
parent->right = nullptr;
}
delete ptr;
countOfNodes--;
}
else if (ptr->left == nullptr) { //node has a right child
BSTNode<T>* temp = ptr->right;
BSTNode<T>* parent = ptr->parent;
if (parent != nullptr){
if (ptr == parent->left)
parent->left = temp;
else
parent->right = temp;
}
else
root = temp;
temp->parent = parent;
delete ptr;
countOfNodes--;
}
else if (ptr->right == nullptr) { //node has a left child
BSTNode<T>* temp = ptr->left;
BSTNode<T>* parent = ptr->parent;
if (parent != nullptr){
if (ptr == parent->right)
parent->right = temp;
else
parent->left = temp;
}
else
root = temp;
temp->parent = parent;
delete ptr;
countOfNodes--;
}
else{ //the node has two children!!! - Bad
//Replace the data with the min of the right subtree
BSTNode<T>* temp = ptr->right;
while (temp->left != nullptr)
temp = temp->left;
ptr->data = temp->data;
remove(temp); //Recursion at its finest....ahhh!
}
}
template <class T>
void BST<T>::insert(const T& val){
countOfNodes++;
if (root == nullptr){//New node is the first on the tree
root = new BSTNode<T>(val);
return;
}
else{
BSTNode<T>* prev=root;
BSTNode<T>* temp=root;
while (temp != nullptr){
prev = temp;
if (val < temp->data)
temp = temp->left;
else
temp = temp->right;
}
//prev is a pointer to the node on which we will insert
if (val < prev->data){ //val will be a left child of prev
prev->left = new BSTNode<T>(val, prev);
}
else
prev->right = new BSTNode<T>(val, prev);
}
}
template <class T>
BSTNode<T>* BST<T>::recursiveCopy(const BSTNode<T>* rhs){
if (rhs == nullptr)
return nullptr;
BSTNode<T>* temp = new BSTNode<T>(rhs->data);
temp->left = recursiveCopy(rhs->left);
temp->right = recursiveCopy(rhs->right);
if (temp->left!=nullptr)
temp->left->parent = temp;
if (temp->right)
temp->right->parent = temp;
return temp;
}
template <class T>
BST<T>& BST<T>::operator=(const BST<T>& rhs){
if (this == &rhs)
return *this;
clear();
root = recursiveCopy(rhs.root);
countOfNodes = rhs.countOfNodes;
return *this;
}
int main(){
BST < int > t1;
srand(time(NULL));
for (int i = 0; i < 100; i++)
t1.insert(rand() % 1000);
BST<int> t2 = t1;
for (int i = 0; i < 10; i++)
t2.remove(rand() % 1000);
t2.printInOrder();
}
int stackDemo(){
stack<char> s;
string input = "int main(){cout<<"this is a test"; int x[5]; myfunc(x[0]);}";
for (int i=0; i < input.length(); i++){
char c = input[i];
if (c == '{' || c == '(' || c == '"' || c == '['){
if (c == '"' && s.top() == '"')
s.pop();
else
s.push(c);
}
else if (c == '}' || c == ')' || c == ']'){
if (c == '}' && s.top() == '{')
s.pop();
else if (c == ')' && s.top() == '(')
s.pop();
else if (c == ']' && s.top() == '[')
s.pop();
else{
cout << "ERROR! Found " << c << " but the top is " << s.top() << endl;
return 1;
}
}
}
if (!s.empty())
cout << "ERROR the stack is not empty but the string is done!" << endl;
else{
cout << "The code is balanced." << endl;
}
return 0;
}
Explanation / Answer
using namespace std;
enum Color {RED, BLACK};
struct Node
{
int data;
bool color;
Node *left, *right, *parent;
// Constructor
Node(int data)
{
this->data = data;
left = right = parent = NULL;
}
};
// Class to represent Red-Black Tree
class RBTree
{
private:
Node *root;
protected:
void rotateLeft(Node *&, Node *&);
void rotateRight(Node *&, Node *&);
void fixViolation(Node *&, Node *&);
public:
// Constructor
RBTree() { root = NULL; }
void insert(const int &n);
void inorder();
void levelOrder();
};
// A recursive function to do level order traversal
void inorderHelper(Node *root)
{
if (root == NULL)
return;
inorderHelper(root->left);
cout << root->data << " ";
inorderHelper(root->right);
}
/* A utility function to insert a new node with given key
in BST */
Node* BSTInsert(Node* root, Node *pt)
{
/* If the tree is empty, return a new node */
if (root == NULL)
return pt;
/* Otherwise, recur down the tree */
if (pt->data < root->data)
{
root->left = BSTInsert(root->left, pt);
root->left->parent = root;
}
else if (pt->data > root->data)
{
root->right = BSTInsert(root->right, pt);
root->right->parent = root;
}
/* return the (unchanged) node pointer */
return root;
}
// Utility function to do level order traversal
void levelOrderHelper(Node *root)
{
if (root == NULL)
return;
std::queue<Node *> q;
q.push(root);
while (!q.empty())
{
Node *temp = q.front();
cout << temp->data << " ";
q.pop();
if (temp->left != NULL)
q.push(temp->left);
if (temp->right != NULL)
q.push(temp->right);
}
}
void RBTree::rotateLeft(Node *&root, Node *&pt)
{
Node *pt_right = pt->right;
pt->right = pt_right->left;
if (pt->right != NULL)
pt->right->parent = pt;
pt_right->parent = pt->parent;
if (pt->parent == NULL)
root = pt_right;
else if (pt == pt->parent->left)
pt->parent->left = pt_right;
else
pt->parent->right = pt_right;
pt_right->left = pt;
pt->parent = pt_right;
}
void RBTree::rotateRight(Node *&root, Node *&pt)
{
Node *pt_left = pt->left;
pt->left = pt_left->right;
if (pt->left != NULL)
pt->left->parent = pt;
pt_left->parent = pt->parent;
if (pt->parent == NULL)
root = pt_left;
else if (pt == pt->parent->left)
pt->parent->left = pt_left;
else
pt->parent->right = pt_left;
pt_left->right = pt;
pt->parent = pt_left;
}
// This function fixes violations caused by BST insertion
void RBTree::fixViolation(Node *&root, Node *&pt)
{
Node *parent_pt = NULL;
Node *grand_parent_pt = NULL;
while ((pt != root) && (pt->color != BLACK) &&
(pt->parent->color == RED))
{
parent_pt = pt->parent;
grand_parent_pt = pt->parent->parent;
/* Case : A
Parent of pt is left child of Grand-parent of pt */
if (parent_pt == grand_parent_pt->left)
{
Node *uncle_pt = grand_parent_pt->right;
/* Case : 1
The uncle of pt is also red
Only Recoloring required */
if (uncle_pt != NULL && uncle_pt->color == RED)
{
grand_parent_pt->color = RED;
parent_pt->color = BLACK;
uncle_pt->color = BLACK;
pt = grand_parent_pt;
}
else
{
/* Case : 2
pt is right child of its parent
Left-rotation required */
if (pt == parent_pt->right)
{
rotateLeft(root, parent_pt);
pt = parent_pt;
parent_pt = pt->parent;
}
/* Case : 3
pt is left child of its parent
Right-rotation required */
rotateRight(root, grand_parent_pt);
swap(parent_pt->color, grand_parent_pt->color);
pt = parent_pt;
}
}
/* Case : B
Parent of pt is right child of Grand-parent of pt */
else
{
Node *uncle_pt = grand_parent_pt->left;
/* Case : 1
The uncle of pt is also red
Only Recoloring required */
if ((uncle_pt != NULL) && (uncle_pt->color == RED))
{
grand_parent_pt->color = RED;
parent_pt->color = BLACK;
uncle_pt->color = BLACK;
pt = grand_parent_pt;
}
else
{
/* Case : 2
pt is left child of its parent
Right-rotation required */
if (pt == parent_pt->left)
{
rotateRight(root, parent_pt);
pt = parent_pt;
parent_pt = pt->parent;
}
/* Case : 3
pt is right child of its parent
Left-rotation required */
rotateLeft(root, grand_parent_pt);
swap(parent_pt->color, grand_parent_pt->color);
pt = parent_pt;
}
}
}
root->color = BLACK;
}
// Function to insert a new node with given data
void RBTree::insert(const int &data)
{
Node *pt = new Node(data);
// Do a normal BST insert
root = BSTInsert(root, pt);
// fix Red Black Tree violations
fixViolation(root, pt);
}
// Function to do inorder and level order traversals
void RBTree::inorder() { inorderHelper(root);}
void RBTree::levelOrder() { levelOrderHelper(root); }
// Driver Code
int main()
{
RBTree tree;
tree.insert(7);
tree.insert(6);
tree.insert(5);
tree.insert(4);
tree.insert(3);
tree.insert(2);
tree.insert(1);
cout << "Inoder Traversal of Created Tree ";
tree.inorder();
cout << " Level Order Traversal of Created Tree ";
tree.levelOrder();
return 0;
}
using namespace std;
enum Color {RED, BLACK};
struct Node
{
int data;
bool color;
Node *left, *right, *parent;
// Constructor
Node(int data)
{
this->data = data;
left = right = parent = NULL;
}
};
// Class to represent Red-Black Tree
class RBTree
{
private:
Node *root;
protected:
void rotateLeft(Node *&, Node *&);
void rotateRight(Node *&, Node *&);
void fixViolation(Node *&, Node *&);
public:
// Constructor
RBTree() { root = NULL; }
void insert(const int &n);
void inorder();
void levelOrder();
};
// A recursive function to do level order traversal
void inorderHelper(Node *root)
{
if (root == NULL)
return;
inorderHelper(root->left);
cout << root->data << " ";
inorderHelper(root->right);
}
/* A utility function to insert a new node with given key
in BST */
Node* BSTInsert(Node* root, Node *pt)
{
/* If the tree is empty, return a new node */
if (root == NULL)
return pt;
/* Otherwise, recur down the tree */
if (pt->data < root->data)
{
root->left = BSTInsert(root->left, pt);
root->left->parent = root;
}
else if (pt->data > root->data)
{
root->right = BSTInsert(root->right, pt);
root->right->parent = root;
}
/* return the (unchanged) node pointer */
return root;
}
// Utility function to do level order traversal
void levelOrderHelper(Node *root)
{
if (root == NULL)
return;
std::queue<Node *> q;
q.push(root);
while (!q.empty())
{
Node *temp = q.front();
cout << temp->data << " ";
q.pop();
if (temp->left != NULL)
q.push(temp->left);
if (temp->right != NULL)
q.push(temp->right);
}
}
void RBTree::rotateLeft(Node *&root, Node *&pt)
{
Node *pt_right = pt->right;
pt->right = pt_right->left;
if (pt->right != NULL)
pt->right->parent = pt;
pt_right->parent = pt->parent;
if (pt->parent == NULL)
root = pt_right;
else if (pt == pt->parent->left)
pt->parent->left = pt_right;
else
pt->parent->right = pt_right;
pt_right->left = pt;
pt->parent = pt_right;
}
void RBTree::rotateRight(Node *&root, Node *&pt)
{
Node *pt_left = pt->left;
pt->left = pt_left->right;
if (pt->left != NULL)
pt->left->parent = pt;
pt_left->parent = pt->parent;
if (pt->parent == NULL)
root = pt_left;
else if (pt == pt->parent->left)
pt->parent->left = pt_left;
else
pt->parent->right = pt_left;
pt_left->right = pt;
pt->parent = pt_left;
}
// This function fixes violations caused by BST insertion
void RBTree::fixViolation(Node *&root, Node *&pt)
{
Node *parent_pt = NULL;
Node *grand_parent_pt = NULL;
while ((pt != root) && (pt->color != BLACK) &&
(pt->parent->color == RED))
{
parent_pt = pt->parent;
grand_parent_pt = pt->parent->parent;
/* Case : A
Parent of pt is left child of Grand-parent of pt */
if (parent_pt == grand_parent_pt->left)
{
Node *uncle_pt = grand_parent_pt->right;
/* Case : 1
The uncle of pt is also red
Only Recoloring required */
if (uncle_pt != NULL && uncle_pt->color == RED)
{
grand_parent_pt->color = RED;
parent_pt->color = BLACK;
uncle_pt->color = BLACK;
pt = grand_parent_pt;
}
else
{
/* Case : 2
pt is right child of its parent
Left-rotation required */
if (pt == parent_pt->right)
{
rotateLeft(root, parent_pt);
pt = parent_pt;
parent_pt = pt->parent;
}
/* Case : 3
pt is left child of its parent
Right-rotation required */
rotateRight(root, grand_parent_pt);
swap(parent_pt->color, grand_parent_pt->color);
pt = parent_pt;
}
}
/* Case : B
Parent of pt is right child of Grand-parent of pt */
else
{
Node *uncle_pt = grand_parent_pt->left;
/* Case : 1
The uncle of pt is also red
Only Recoloring required */
if ((uncle_pt != NULL) && (uncle_pt->color == RED))
{
grand_parent_pt->color = RED;
parent_pt->color = BLACK;
uncle_pt->color = BLACK;
pt = grand_parent_pt;
}
else
{
/* Case : 2
pt is left child of its parent
Right-rotation required */
if (pt == parent_pt->left)
{
rotateRight(root, parent_pt);
pt = parent_pt;
parent_pt = pt->parent;
}
/* Case : 3
pt is right child of its parent
Left-rotation required */
rotateLeft(root, grand_parent_pt);
swap(parent_pt->color, grand_parent_pt->color);
pt = parent_pt;
}
}
}
root->color = BLACK;
}
// Function to insert a new node with given data
void RBTree::insert(const int &data)
{
Node *pt = new Node(data);
// Do a normal BST insert
root = BSTInsert(root, pt);
// fix Red Black Tree violations
fixViolation(root, pt);
}
// Function to do inorder and level order traversals
void RBTree::inorder() { inorderHelper(root);}
void RBTree::levelOrder() { levelOrderHelper(root); }
// Driver Code
int main()
{
RBTree tree;
tree.insert(7);
tree.insert(6);
tree.insert(5);
tree.insert(4);
tree.insert(3);
tree.insert(2);
tree.insert(1);
cout << "Inoder Traversal of Created Tree ";
tree.inorder();
cout << " Level Order Traversal of Created Tree ";
tree.levelOrder();
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.