Question

In this assignment, you will develop a C program to construct a red and black tree. For a given input sequence the tree is unique by using RB-INSERT on one number at a time. Below is an example:

The input is a sequence of numbers separated by comma, e.g. 1,8,11,2, … You can enter the numbers using an input file and output the tree, or through a command line with one number at a time (with “X” to stop entering and printing the output). The output should reflect the above tree in the pre-order traversal, by listing nodes with B and R indicating the black and red colors. In addtion, please also show the height and the black height of the red and black tree, as well as the second largest element on the tree. A sample output is:

Pre-order traversal of the tree:

1-B; 2-R; 5-R; 8-R, 7-B; 11-B; 14-B; 15-R;

The height of the red and black tree is 4.

The black height of the red and black tree is 2.

The second largest element of the tree is 14.

• Your program should compile using gcc on a unix/lunix machine. Using a makefile is encouraged but not required. You can also provide a readme file if needed.

• Although not encouraged, you may use g++ for a C++ code. Provide a readme file if you use C++ to explain how to compile and run the program. No other programming language will be accepted.

Answer 1

#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 Preorder();
};

// A recursive function to do level order traversal
void PreorderHelper(Node *root)
{
if (root != NULL)
{
cout << root->data << " ";
PreorderHelper(root->left);
PreorderHelper(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;
}

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::Preorder() { PreorderHelper(root);}

// Driver Code
int main()
{
RBTree tree;

tree.insert(1);
tree.insert(2);
tree.insert(5);
tree.insert(8);
tree.insert(7);
tree.insert(11);
tree.insert(14);
tree.insert(15);

cout << "Preorder Traversal of Created Red black Tree\n";
tree.Preorder();
return 0;
}

/*
first of all create a structure and class that you have to create a red black tree. Assign a pointer values as left and right.
After that assign parent, left and right tends to null.Create a function to preorder the given values. In preorder function give
the conditions to preorder the values.Use the scope resolution operator(::} to rotate right and left of red black tree.And fix the
violation to find the node to be red or a black.After that use the insert function to insert the values.In main function call the
values to be traverse.
*/