2 Red-Black Trees (30 points) Consider the binary tree as shown in Figure 2. 65

Question

2 Red-Black Trees (30 points) Consider the binary tree as shown in Figure 2. 65 50 80 10 60 85 5 45 62 Figure 2: Binary Tree: The letter next to each node (e.g., a, b) denotes the tree node, and the number inside each node is the key 2.1 Correctness (10 points) Is this binary tree a valid red-black tree? In other words, does it satisfy the red-black tree properties? If not, which node(s) violates the red-black tree properties, and why? You need to specify which properties are violated, if any. How would you modify the violating node(s) (e.g., color, key value) to make the binary tree a valid red-black tree? Hint: Your answer should incur the minimum amount of change on the current binary tree 2.2 Rotation (10 points) Let T denote the red-black tree in Figure 2 (or the corrected version if you need to modify the tree node(s) in the first question). How does the tree look like after the following operation: Right-Rotate(T, b). Is it still a valid red-black tree after this operation? Justify your answer 2.3 Insertion (10 points) Let T denote the red-black tree in Figure 2 (or the corrected version if you need to modify the tree node(s) in the first question). How does the tree look like after we insert a new node with key 90? Specify if you need to use Case 1, Case 2, or Case 3 in RB-INSERTION

Explanation / Answer

ANSWER::

#include <bits/stdc++.h>
using namespace std;
enum Color {RED, BLACK};
struct Node
{
int data;
bool color;
Node *left, *right, *parent;

Node(int data)
{
this->data = data;
left = right = parent = NULL;
}
};

class RBTree
{
private:
Node *root;
protected:
void rotateLeft(Node *&, Node *&);
void rotateRight(Node *&, Node *&);
void fixViolation(Node *&, Node *&);
public:
RBTree() { root = NULL; }
void insert(const int &n);
void inorder();
void levelOrder();
};
void inorderHelper(Node *root)
{
if (root == NULL)
return;

inorderHelper(root->left);
cout << root->data << " ";
inorderHelper(root->right);
}
Node* BSTInsert(Node* root, Node *pt)
{
if (root == NULL)
return pt;

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 root;
}
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;
}

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;
if (parent_pt == grand_parent_pt->left)
{

Node *uncle_pt = grand_parent_pt->right;

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
{
if (pt == parent_pt->right)
{
rotateLeft(root, parent_pt);
pt = parent_pt;
parent_pt = pt->parent;
}
rotateRight(root, grand_parent_pt);
swap(parent_pt->color, grand_parent_pt->color);
pt = parent_pt;
}
}
else
{
Node *uncle_pt = grand_parent_pt->left;

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
{
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;
}

rotateLeft(root, grand_parent_pt);
swap(parent_pt->color, grand_parent_pt->color);
pt = parent_pt;
}
}
}

root->color = BLACK;
}

void RBTree::insert(const int &data)
{
Node *pt = new Node(data);
root = BSTInsert(root, pt);

fixViolation(root, pt);
}

void RBTree::inorder() { inorderHelper(root);}
void RBTree::levelOrder() { levelOrderHelper(root); }

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

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.