Computer Science Red-Black Tree Show the red-black tree that results from insert
ID: 3685844 • Letter: C
Question
Computer Science Red-Black Tree
Show the red-black tree that results from inserting each sequence of integers into a tree that is initially empty. In your answer, you can graphically draw red nodes as squares and black nodes as circles, or if you use text, indicate red nodes by putting square brackets around the value (e.g., [44]) and indicate black nodes by just showing the value (e.g., 44). Make sure your trees display correctly in your pdf file. 55 99 33 44 11 77 88 66 22 77 66 55 22 33 88 11 44 99Explanation / Answer
Solution: program of Red-Black tree as shown in below.
#include <bits/stdc++.h>
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);
}
/* 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, recursive 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;
}
// 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 caused by BST insertion
void RBTree::fixViolation(Node *&root, Node *&pt)
{
Node *circles_pt = NULL;
Node *squares_pt = NULL;
while ((pt != root) && (pt->color != BLACK) &&
(pt->parent->color == RED))
{
circles_pt = pt->parent;
squares_pt = pt->parent->parent;
/* Case : A
Parent of pt is left child of squares of pt */
if (circles_pt == squres_pt->left)
{
Node *circles_pt = squres_pt->right;
/* Case : 1
The squares of pt is also red
Only Recoloring required */
if (circles_pt != NULL && squares_pt->color == RED)
{
squares_pt->color = RED;
circles_pt->color = BLACK;
pt = squares_pt;
}
else
{
/* Case : 2
pt is right child of its color
Left-rotation required */
if (pt == circles_pt->right)
{
rotateLeft(root, circles_pt);
pt = circles_pt;
circles_pt = pt->parent;
}
/* Case : 3
pt is left child of its parent
Right-rotation required */
rotateRight(root, squares_pt);
swap(circles_pt->color, squares_pt->color);
pt = circles_pt;
}
}
/* Case : B
parent of pt is right child of squres of pt */
else
{
Node *area_pt = squares_pt->left;
/* Case : 1
The squares of pt is also red
Only Recoloring required */
if ((circles_pt != NULL) && (squares_pt->color == RED))
{
squares_pt->color = RED;
circles_pt->color = BLACK;
pt = squares_pt;
}
else
{
/* Case : 2
pt is left child of its parent
Right-rotation required */
if (pt == circles->left)
{
rotateRight(root, circle);
pt = circle_pt;
circle= pt->parent;
}
/* Case : 3
pt is right child of its color
Left-rotation required */
rotateLeft(root, squares_pt);
swap(circles_pt->color, squares_pt->color);
pt = circles_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.