C++ black red tree. 2. Implementation of the data structure -- Provide at least
ID: 3806718 • Letter: C
Question
C++ black red tree.
2. Implementation of the data structure -- Provide at least the following public member methods for the red-black tree class:
Insertion: insert a value in the tree. If the value already exists in the tree, this operation has no effect on the tree.
Search : return true if a given value exists in the tree; otherwise false.
Height : return the height of the tree. The height of an empty tree is -1.
Size: return the number of elements in the tree. The size of an empty tree is 0.
1) It is best to design a system of base and derived classes of binary tree (Height, Size), binary search tree (Search, Binary-Search-Tree-Insertion), and red-black tree (Red-Black-Tree-Insertion) classes. But it is not required to do so. You will also need to design your Node class(es) accordingly.
2) You may find it relatively easy to implement most of above methods in a recursive fashion.
4. About the program:
1) The driver program takes two command line arguments in form of “[N=n] [L=Y/N]”. The first argument specifies the number of elements to be inserted in the tree, i.e. the number of integers. You will use values 100, 1000, 10000, 100000, 1000000, … etc. to test your program. The second argument specifies whether to use the library implementation of the red black tree (e.g. STL set in C++). ‘Y’ means yes; ‘N’ means no. “[]” indicates an argument is optional. By default, N is 1000, L is ‘N’. For example, invoking the following command
./your-program N=100000 L=Y
will generate 100000 integers to be added in the tree provided by the library. And the command
./your-program
will generate 1000 integers to be stored in the tree that you implement. I assumed a C++ program in
above examples. If yours is a Java or Python program, you need to use proper command.
2) Preparation of your input data: For the command line argument N, produce two collections of data,
each has N random integers in the range of [1, 2N]. These two collections of random integers need
to be generated by different seed values of the random generator (e.g. srand() and rand() for
C++). One collection of integers (referred to as tree-data) is to be inserted into the red black tree.
One collection of integers (referred to as search-data) is to be searched in the red black tree. Note
that you will get the same sequence of random numbers given a same seed value for the random
number generator. You want to use the same seed value for all tree-data, and the same seed value
for all search-data to compare the performance of your implementation and the library class of the
red-black tree.
3) Implementation of the program:
a. Produce the tree-data and search-data described above;
b. Create an instance of the red-black-tree (your own implementation or the library class,
depending on the command line argument);
c. Insert all tree-data to the red-black-tree;
d. Print out the height of the tree and the size of the tree. Since there may be duplicated values
from the random generator, this value of size may be less than your input N. If the class
library does not support certain operation, you can skip it. For example, the STL set
does not have public method to display height. Do not print out the values of whole tree.
(But you can print out these values during testing and debugging stage of your work.)
e. Search each value from the search-data in the red-black-tree, count the number of
successful searches, and divide it by the total number of searches. Print the percentage of
successful searches.
Explanation / Answer
#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);
}
/* 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.