Red Black Trees
Assignment Description
This is a programming assignment. You are required to develop a red black tree with some of its
operations. Follow below instructions closely.
1. You need to implement a data structure to representa tree node. Each node should have the following data fields:
· discipline
· gender
· team_or_ind
· event
· venue
· medal
· athlete
· country
The unique key to identify each node will be a combination of discipline, gender, event, and
athlete.
Each node should also have its parent node called parent, its left child node called left, its right
child node called right, and color which should be either RED or BLACK.
2. Using the nodes above, you need to build a red black tree by using their keys.
3. When you compare two nodes, compare their discipline first in alphabetical order; if discipline
is the same, then compare their event; if event are the same, compare their gender; if gender are
the same, then compare athlete. Note: for all these fields, they will be compared in alphabetical
order according to each character’s ASCII number.
- Your red black tree needs to have operations called preorderTreeWalk, inorderTreeWalkand
postorderTreeWalkwhich will print all tree node keys in a pre-, in- and post-order traversal
respectively.
5. Your red black tree also needs to have operations called treeSearch, treeMinimum,
treeMaximum, treeSuccessorand treePredecessor.
6. Your red black tree needs to have treeInsertoperation and to implement this, first you need to
define Binary Search Tree insertion, right rotate, and left rotate functions. They will be called in
your red black tree insertion function.
7. Your red black tree class should have a constructor to initialize its root to be NULL, and a
destructor that will delete all nodes in the tree and perform garbage collections. The destructor
should also print The number of nodes deleted: X, where X is the number of nodes deleted
and it should be called when a user chooses to exit the program.
8. You should implement a driver’s program that takes the commands: tree_inorder,
tree_preorder, tree_postorder, tree_maximum, tree_minimum, tree_successor, tree_predecessor,
tree_insert, and quit. The program should print out each entered command before processing it.
Below please find each command’s detailed description:
tree_inorder
It prints all keys in the tree using the in-order traversal, using the following format:
discipline: Cycling
gender: M
team_or_ind: IND
event: Road
venue: Regent’s Park
medal: 1. GOLD
athlete: AleksanderWinokurow
country: Kazakhstan
color: RED
discipline: Cycling
gender: M
team_or_ind: IND
event: Road
venue: Regent’s Park
medal: 3. BRONZE
athlete: Alexander Kristoff
country: Norway
color: BLACK
discipline: Cycling
gender: M
team_or_ind: IND
event: Road
venue: Regent’s Park
medal: 2. SILVER
athlete: RigobertoUran
country: Colombia
color: RED
It should print tree is empty if the tree is empty.
tree_preorder
It prints all keys in the tree using the pre-order traversal. The format it prints should be similar to
above tree_inorder. For example:
discipline: Cycling
gender: M
team_or_ind: IND
event: Road
venue: Regent’s Park
medal: 3. BRONZE
athlete: Alexander Kristoff
country: Norway
color: BLACK
discipline: Cycling
gender: M
team_or_ind: IND
event: Road
venue: Regent’s Park
medal: 1. GOLD
athlete: AleksanderWinokurow
country: Kazakhstan
color: RED
discipline: Cycling
gender: M
team_or_ind: IND
event: Road
venue: Regent’s Park
medal: 2. SILVER
athlete: RigobertoUran
country: Colombia
color: RED
It should print tree is empty if the tree is empty.
tree_postorder
It prints all keys in the tree using the post-order traversal. The format it prints should be similar
to above tree_inorder. For example:
discipline: Cycling
gender: M
team_or_ind: IND
event: Road
venue: Regent’s Park
medal: 1. GOLD
athlete: AleksanderWinokurow
country: Kazakhstan
color: RED
discipline: Cycling
gender: M
team_or_ind: IND
event: Road
venue: Regent’s Park
medal: 2. SILVER
athlete: RigobertoUran
country: Colombia
color: RED
discipline: Cycling
gender: M
team_or_ind: IND
event: Road
venue: Regent’s Park
medal: 3. BRONZE
athlete: Alexander Kristoff
country: Norway
color: BLACK
It should print tree is empty if the tree is empty.
tree_minimum
It should call treeMinimumand print the first node in in-order traversal (i.e. the smallest node
inside the tree) using the following format:
The first athlete is:
discipline: Cycling
gender: M
team_or_ind: IND
event: Road
venue: Regent’s Park
medal: 1. GOLD
athlete: AleksanderWinokurow
country: Kazakhstan
color: RED
It should print tree is empty if the tree is empty.
tree_maximum
It should call treeMaximumand print the last node in in-order traversal (i.e. the largest node
inside the tree) using the following format:
The last athlete is:
discipline: Cycling
gender: M
team_or_ind: IND
event: Road
venue: Regent’s Park
medal: 2. SILVER
athlete: RigobertoUran
country: Colombia
color: RED
It should print tree is empty if the tree is empty.
tree_predecessor,discipline,gender,event,athlete
It should call treePredecessorand search for the predecessor of the given athlete. An example of
this command is:
tree_predecessor,Cycling,M,Road,AlexanderKristoff
If it finds its predecessor, then it should print the result as:
The predecessor of the medal recipient Alexander Kristoff for Cycling with
event Road is:
discipline: Cycling
gender: M
team_or_ind: IND
event: Road
venue: Regent’s Park
medal: 1. GOLD
athlete: AleksanderWinokurow
country: Kazakhstan
color: RED
If it cannot find its predecessor, then it should print:
The medal recipient AleksanderWinokurow for Cycling with event ROAD does not
have any predecessor
It should print tree is empty if the tree is empty.
tree_successor,discipline,gender,event,athlete
It should call treeSuccessorand search for the successor of the given athlete. An example of this
command is:
tree_successor,Cycling,M,Road,AleksanderWinokurow
If it can find its successor, then it should print the result as:
The successor of the medal recipient Alexander Kristoff for Cycling with
event Road is:
discipline: Cycling
gender: M
team_or_ind: IND
event: Road
venue: Regent’s Park
medal: 3. BRONZE
athlete: Alexander Kristoff
country: Norway
color: BLACK
If it cannot find its successor, then it should print:
The medal recipient Alexander Kristoff for Cycling with event ROAD does not
have any predecessor
It should print tree is empty if the tree is empty.
tree_search,discipline,gender,event,athlete
It should call treeSearchand search the given athlete with the given information. An example of
this command is:
tree_search,Cycling,M,Road,AlexanderKristoff
If it can find the athlete specified, then it should print the result by showing its medal as:
The medal recipient Alexander Kristoff has the medal of 3. BRONZE
If it cannot find the athlete, then it should print:
Alexander Kristoff for Cycling with event Road not found
It should print tree is empty if the tree is empty.
tree_insert,discipline,gender,ind_team,event,venue,medal,athlete,country
It should call treeInsertand attempt to insert the given athlete. If there exists another athlete with
the same discipline, gender, event, and athlete, then it should not be able to insert it. An example
of this command is:
tree_insert,Cycling,M,IND,Road,Regent’s Park,1. GOLD,Aleksander
Winokurow,Kazakhstan
If it can insert, then it should print:
The medal recipient AleksanderWinokurow for Cycling with event Road inserted
If it cannot insert, then it should print:
The medal recipient AleksanderWinokurow for Cycling with event Road NOT
inserted
It should print tree is empty if the tree is empty.
quit
The command quits the program and exit. The red black tree object should be deleted, and it
should print how many nodes are deleted using the following format:
The number nodes deleted: 3
9. Sample Run
Below please find one sample run of the program (user input is in bold)
tree_inorder
next command: tree_inorder
tree is empty
tree_preorder
next command: tree_preorder
tree is empty
tree_postorder
next command: tree_postorder
tree is empty
tree_insert,Cycling,M,IND,Road,Regent’s Park,1. GOLD,Aleksander
Winokurow,Kazakhstan
next command: tree_insert,Cycling,M,IND,Road,Regent’s Park,1. GOLD,Aleksander
Winokurow,Kazakhstan
The medal recipient AleksanderWinokurow for Cycling with event Road inserted
tree_insert,Cycling,M,IND,Road,Regent’s Park,2. SILVER,Rigoberto
Uran,Colombia
next command: tree_insert,Cycling,M,IND,Road,Regent’s Park,2.SILVER,Rigoberto
Uran,Colombia
The medal recipient RigobertoUran for Cycling with event Road inserted
tree_insert,Cycling,M,IND,Road,Regent’s Park,3. BRONZE,Alexander
Kristoff,Norway
next command: tree_insert,Cycling,M,IND,Road,Regent’s Park,3.BRONZE,Alexander
Kristoff,Norway
The medal recipient Alexander Kristoff for Cycling with event Road inserted
tree_inorder
next command: tree_inorder
discipline: Cycling
gender: M
team_or_ind: IND
event: Road
venue: Regent’s Park
medal: 1. GOLD
athlete: AleksanderWinokurow
country: Kazakhstan
color: RED
discipline: Cycling
gender: M
team_or_ind: IND
event: Road
venue: Regent’s Park
medal: 3. BRONZE
athlete: Alexander Kristoff
country: Norway
color: BLACK
discipline: Cycling
gender: M
team_or_ind: IND
event: Road
venue: Regent’s Park
medal: 2. SILVER
athlete: RigobertoUran
country: Colombia
color: RED
tree_preorder
next command: tree_preorder
discipline: Cycling
gender: M
team_or_ind: IND
event: Road
venue: Regent’s Park
medal: 3. BRONZE
athlete: Alexander Kristoff
country: Norway
color: BLACK
discipline: Cycling
gender: M
team_or_ind: IND
event: Road
venue: Regent’s Park
medal: 1. GOLD
athlete: AleksanderWinokurow
country: Kazakhstan
color: RED
discipline: Cycling
gender: M
team_or_ind: IND
event: Road
venue: Regent’s Park
medal: 2. SILVER
athlete: RigobertoUran
country: Colombia
color: RED
tree_postorder
next command: tree_postorder
discipline: Cycling
gender: M
team_or_ind: IND
event: Road
venue: Regent’s Park
medal: 1. GOLD
athlete: AleksanderWinokurow
country: Kazakhstan
color: RED
discipline: Cycling
gender: M
team_or_ind: IND
event: Road
venue: Regent’s Park
medal: 2. SILVER
athlete: RigobertoUran
country: Colombia
color: RED
discipline: Cycling
gender: M
team_or_ind: IND
event: Road
venue: Regent’s Park
medal: 3. BRONZE
athlete: Alexander Kristoff
country: Norway
color: BLACK
tree_maximum
next command: tree_maximum
The last athlete is:
discipline: Cycling
gender: M
team_or_ind: IND
event: Road
venue: Regent’s Park
medal: 2. SILVER
athlete: RigobertoUran
country: Colombia
color: RED
tree_minimum
next command: tree_minimum
The first athlete is:
discipline: Cycling
gender: M
team_or_ind: IND
event: Road
venue: Regent’s Park
medal: 1. GOLD
athlete: AleksanderWinokurow
country: Kazakhstan
color: RED
tree_search,Cycling,M,Road,AlexanderKristoff
next command: tree_search,Cycling,M,Road,AlexanderKristoff
The medal recipient Alexander Kristoff has the medal of 3. BRONZE
tree_search,Archery,M,Archery,team USA
next command: tree_search,Archery,M,Archery,team USA
team USA for Archery with event Archery not found
tree_successor,Fencing,F,Foil,AriannaErrigo
next command: tree_successor,Fencing,F,Foil,AriannaErrigo
The medal recipient Arianna Errigo for Fencing with event Foil does not have
any successor
tree_predecessor,Cycling,M,Road,AlexanderKristoff
next command: tree_predecessor,Cycling,M,Road,AlexanderKristoff
The predecessor of the medal recipient Alexander Kristoff for Cycling with
event Road is:
discipline: Cycling
gender: M
team_or_ind: IND
event: Road
venue: Regent’s Park
medal: 1. GOLD
athlete: AleksanderWinokurow
country: Kazakhstan
color: RED
quit
next command: quit
The number nodes deleted: 3
- Implementation/Documentation Requirements
· You need implement this program using C++ and it has to read from the standard input
(from a keyboard).
· Your program needs to compile and execute in general.asu.edu.
· You need to define treeInorder, treePreorder, treePostorder, treeMinimum,
treeMaximum, treePredecessor, treeSuccessor, treeInsertfor your red black tree, also the
constructor, destructor, leftRotate, rightRotate, and binary search, insertion functions.
· Your code should be well documented and commented, and every file should have your
name at its top.
· Also you are not allowed to use any predefined data structures except arrays and strings, you need to build your own data structures andoperations associated with them (such as insert or search).
Solution
Assignment5.cpp
#include “RedBlackTree.h”
using namespace std;
int main(intagrc, char* agrv[])
{
string in;
string token;
RedBlackTree tree = RedBlackTree();
cout<< “Welcome to Assignment 5. Please type your command line” <<endl;
try
{
getline(std::cin, in);
do
{
cout<< “next command: ” + in <<endl;
if (in.substr(0, 12) == “tree_inorder”)
{
tree.inorderTreeWalk(tree.root);
}
else if (in.substr(0, 13) == “tree_preorder”)
{
tree.preorderTreeWalk(tree.root);
}
else if (in.substr(0, 14) == “tree_postorder”)
{
tree.postorderTreeWalk(tree.root);
}
else if (in.substr(0, 12) == “tree_minimum”)
{
TreeNode* temp = tree.treeMinimum(tree.root);
cout<< “The first athlete is ” <<endl;
temp->print();
}
else if (in.substr(0, 12) == “tree_maximum”)
{
TreeNode* temp = tree.treeMaximum(tree.root);
cout<< “The last athlete is ” <<endl;
temp->print();
}
else if (in.substr(0, 11) == “tree_insert”)
{
//insert using parameters.store in an array of 8.
string parameter = in.substr(12);
int i = 0;
unsignedintpos = parameter.find(“,”);
int index = 0;
string parameters[8];
try
{
while (pos != string::npos&& index < 8) //Split parameters into array
{
parameters[index] = (parameter.substr(i, pos – i));
i = ++pos;
pos = parameter.find(“,”, pos);
if (pos == string::npos)
parameters[index + 1] = (parameter.substr(i, parameter.length()));
index++;
}
TreeNode* temp = new TreeNode(parameters[0], parameters[1], parameters[2], parameters[3], parameters[4], parameters[5], parameters[6],
parameters[7]);
tree.treeInsert(temp);
cout<< “The medal recipient “<< temp->athlete <<” for ” << temp->discipline << ” with event ” << temp->event << ” inserted” <<endl;
}
catch (…)
{
cout<< “Initialization error while reading parameters” <<endl;
}
}
else
{
if (in.substr(0, 11) == “tree_search”)
{
string parameter = in.substr(12);
int i = 0;
unsignedintpos = parameter.find(“,”);
int index = 0;
string parameters[4];
try
{
while (pos != string::npos&& index < 4) //Split parameters into array
{
parameters[index] = (parameter.substr(i, pos – i));
i = ++pos;
pos = parameter.find(“,”, pos);
if (pos == string::npos)
parameters[index + 1] = (parameter.substr(i, parameter.length()));
index++;
}
}
catch (…)
{
cout<< “Initialization error while reading parameters” <<endl;
}
string key = parameters[0] + parameters[1] + parameters[2] + parameters[3];
TreeNode* temp = tree.treeSearch(tree.root, key);
if (temp != tree.nil)
{
cout<< “The medal recipient ” << temp->athlete << ” has the medal of ” << temp->medal <<endl;
}
else
{
cout<< parameters[3] << ” for ” << parameters[0] << ” with event ” << parameters[2] << ” not found” <<endl;
}
}
else if (in.substr(0, 16) == “tree_predecessor”)
{
if (tree.size == 0)
{
cout<< “Tree is empty” <<endl;
continue;
}
string parameter = in.substr(17);
int i = 0;
unsignedintpos = parameter.find(“,”);
int index = 0;
string parameters[4];
try
{
while (pos != string::npos&& index < 4) //Split parameters into array
{
parameters[index] = (parameter.substr(i, pos – i));
i = ++pos;
pos = parameter.find(“,”, pos);
if (pos == string::npos)
parameters[index + 1] = (parameter.substr(i, parameter.length()));
index++;
}
}
catch (…)
{
cout<< “Initialization error while reading parameters” <<endl;
}
string key = parameters[0] + parameters[1] + parameters[2] + parameters[3];
TreeNode* temp = tree.treeSearch(tree.root, key);
TreeNode* pre;
if (temp != tree.nil)
{
pre = tree.treePredecessor(temp);
if (pre == tree.nil)
{
cout<< “The medal recipient ” << parameters[3] << ” for ” << parameters[0] << ” with event ” << parameters[2]
<<” does not have any predecessor” <<endl;
}
else
{
cout<< “The predecessor of the medal recipient ” << parameters[3] << ” for ” << parameters[0] << ” with event ” << parameters[2]
<<” is ” <<endl<<endl;
pre->print();
}
}
else
{
cout<< parameters[3] << ” for ” << parameters[0] << ” with event ” << parameters[2] << ” not found” <<endl;
}
}
else if (in.substr(0, 14) == “tree_successor”)
{
string parameter = in.substr(15);
int i = 0;
unsignedintpos = parameter.find(“,”);
int index = 0;
string parameters[4];
try
{
while (pos != string::npos&& index < 4) //Split parameters into array
{
parameters[index] = (parameter.substr(i, pos – i));
i = ++pos;
pos = parameter.find(“,”, pos);
if (pos == string::npos)
parameters[index + 1] = (parameter.substr(i, parameter.length()));
index++;
}
}
catch (…)
{
cout<< “Initialization error while reading parameters” <<endl;
}
string key = parameters[0] + parameters[1] + parameters[2] + parameters[3];
TreeNode* temp = tree.treeSearch(tree.root, key);
TreeNode* succ;
if (temp != tree.nil)
{
succ = tree.treeSuccessor(temp);
if (succ == tree.nil)
{
cout<< “The medal recipient ” << parameters[3] << ” for ” << parameters[0] << ” with event ” << parameters[2]
<<” does not have any successor” <<endl;
}
else
{
cout<< “The successor of the medal recipient ” << parameters[3] << ” for ” << parameters[0] << ” with event ” << parameters[2]
<<” is ” <<endl<<endl;
succ->print();
}
}
else
{
cout<< parameters[3] << ” for ” << parameters[0] << ” with event ” << parameters[2] << ” not found” <<endl;
}
}
}
cout<<endl;
getline(std::cin, in);
}
while (in != “quit”);
}
catch (…)
{
cout<< “Input error”;
}
}
RedBlackTree.cpp
#include “RedBlackTree.h”
RedBlackTree::RedBlackTree()
{
size = 0;
numDeleted = 0;
nil = new TreeNode();
root = nil;
}
RedBlackTree::~RedBlackTree()
{
deleteRBNode(root);
cout<< “The number nodes deleted: ” <<numDeleted<<endl;
}
voidRedBlackTree::deleteRBNode(TreeNode* node)
{
if (node != nullptr)
{
if (node->left != nil)
deleteRBNode(node->left);
if (node->right != nil)
deleteRBNode(node->right);
delete node;
node = nullptr;
size–;
numDeleted++;
}
}
TreeNode* RedBlackTree::compare(TreeNode* A, TreeNode *B, string maxOrMin)
{
TreeNode* max = nullptr;
TreeNode* min = nullptr;
// Compare discipline
int i = A->discipline.compare(B->discipline);
if (i > 0)
{
max = A;
min = B;
}
else if (i < 0)
{
max = B;
min = A;
}
else
{
// Compare Event
i = A->event.compare(B->event);
if (i > 0)
{
max = A;
min = B;
}
else if (i < 0)
{
max = B;
min = A;
}
else
{
// Compare gender
i = A->gender.compare(B->gender);
if (i > 0)
{
max = A;
min = B;
}
else if (i < 0)
{
max = B;
min = A;
}
else
{
// Compate Athlete
i = A->athlete.compare(B->athlete);
if (i > 0)
{
max = A;
min = B;
}
else if (i < 0)
{
max = B;
min = A;
}
else
{
cout<< “Compare function: All fields match”;
return nil;
//print error
}
}
}
}
if (maxOrMin == “MAX”)
{
return max;
}
else if (maxOrMin == “MIN”)
{
return min;
}
else
{
returnnullptr;
}
}
voidRedBlackTree::inorderTreeWalk(TreeNode* node)
{
if (root == nil)
{
cout<<endl<< “Tree is Empty” <<endl;
}
else if (node != nil)
{
inorderTreeWalk(node->left);
node->print();
inorderTreeWalk(node->right);
}
if (node == nil)
{
return;
}
}
voidRedBlackTree::postorderTreeWalk(TreeNode* node)
{
if (root == nil)
{
cout<<endl<< “Tree is Empty” <<endl;
}
else if (node != nil)
{
postorderTreeWalk(node->left);
postorderTreeWalk(node->right);
node->print();
}
}
voidRedBlackTree::preorderTreeWalk(TreeNode* node)
{
if (root == nil)
{
cout<<endl<< “Tree is Empty” <<endl;
}
else if (node != nil)
{
node->print();
preorderTreeWalk(node->left);
preorderTreeWalk(node->right);
}
}
TreeNode * RedBlackTree::treeSearch(TreeNode* node, string key)
{
if (node == nil || key == node->key)
{
return node;
}
else
{
if (key < node->key)
{
returntreeSearch(node->left, key);
}
else
{
returntreeSearch(node->right, key);
}
}
}
TreeNode * RedBlackTree::treeMinimum(TreeNode* node)
{
while (node->left != nil)
{
node = node->left;
}
return node;
}
TreeNode * RedBlackTree::treeMaximum(TreeNode * node)
{
while (node->right != nil)
{
node = node->right;
}
return node;
}
TreeNode * RedBlackTree::treeSuccessor(TreeNode* node)
{
if (node->right != nil)
{
returntreeMinimum(node->right);
}
else
{
TreeNode* parentNode = node->parent;
while (parentNode != nullptr&& node == parentNode->right)
{
node = parentNode;
parentNode = parentNode->parent;
}
returnparentNode;
}
}
TreeNode * RedBlackTree::treePredecessor(TreeNode * node)
{
if (node->left != nil)
{
returntreeMaximum(node->left);
}
else
{
TreeNode* parentNode = node->parent;
while (parentNode != nullptr&& node == parentNode->left)
{
node = parentNode;
parentNode = parentNode->parent;
}
returnparentNode;
}
}
voidRedBlackTree::treeInsert(TreeNode * toInsert)
{
TreeNode* y;
bstInsert(toInsert);
toInsert->color = “RED”;
if (root == nil)
{
toInsert->color = “BLACK”;
root = toInsert;
size++;
return;
}
while (toInsert->parent->color == “RED”)
{
if (toInsert->parent == toInsert->parent->parent->left)
{
y = toInsert->parent->parent->right;
if (y->color == “RED”)
{
toInsert->parent->color = “BLACK”;
y->color = “BLACK”;
toInsert->parent->parent->color = “RED”;
toInsert = toInsert->parent->parent;
}
else
{
if (toInsert == toInsert->parent->right)
{
toInsert = toInsert->parent;
leftRotate(toInsert);
}
toInsert->parent->color = “BLACK”;
toInsert->parent->parent->color = “RED”;
rightRotate(toInsert->parent->parent);
}
}
else
{
y = toInsert->parent->parent->left;
if (y->color == “RED”)
{
toInsert->parent->color = “BLACK”;
y->color = “BLACK”;
toInsert->parent->parent->color = “RED”;
toInsert = toInsert->parent->parent;
}
else
{
if (toInsert == toInsert->parent->left)
{
toInsert = toInsert->parent;
rightRotate(toInsert);
}
toInsert->parent->color = “BLACK”;
toInsert->parent->parent->color = “RED”;
leftRotate(toInsert->parent->parent);
}
}
}
root->color = “BLACK”;
size++;
}
voidRedBlackTree::bstInsert(TreeNode * toInsert)
{
TreeNode* nodeParent = nil;
TreeNode* node = root;
while (node != nil)
{
nodeParent = node;
TreeNode* temp = compare(toInsert, nodeParent, “MIN”);
if (temp == nil)
{
return;
}
else if (temp->key == toInsert->key)
{
node = node->left;
}
else
{
node = node->right;
}
}
toInsert->parent = nodeParent;
toInsert->color = “RED”;
toInsert->left = nil;
toInsert->right = nil;
if (nodeParent == nil)
{
root = toInsert;
}
else
{
TreeNode* temp = compare(toInsert, nodeParent, “MIN”);
if (temp->key == toInsert->key)
{
nodeParent->left = toInsert;
}
else
{
nodeParent->right = toInsert;
}
}
}
voidRedBlackTree::leftRotate(TreeNode * pivot)
{
TreeNode* rightChild = pivot->right;
pivot->right = rightChild->left;
if (rightChild->left != nullptr)
{
rightChild->left->parent = pivot;
}
rightChild->parent = pivot->parent;
if (pivot == root)
{
root = rightChild;
}
else
{
if (pivot == pivot->parent->left)
{
pivot->parent->left = rightChild;
}
else
{
pivot->parent->right = rightChild;
}
}
rightChild->left = pivot;
pivot->parent = rightChild;
}
voidRedBlackTree::rightRotate(TreeNode * pivot)
{
TreeNode* leftChild = pivot->left;
pivot->left = leftChild->right;
if (leftChild->right != nullptr)
{
leftChild->right->parent = pivot;
}
leftChild->parent = pivot->parent;
if (pivot == root)
{
root = leftChild;
}
else
{
if (pivot == pivot->parent->right)
{
pivot->parent->right = leftChild;
}
else
{
pivot->parent->left = leftChild;
}
}
leftChild->right = pivot;
pivot->parent = leftChild;
}
RedBlackTree.h
#ifndef REDBLACKTREE_H_
#define REDBLACKTREE_H_
#include “TreeNode.h”
classRedBlackTree
{
public:
RedBlackTree();
~RedBlackTree();
TreeNode * compare(TreeNode* A, TreeNode* B, string maxOrMin);
voidinorderTreeWalk(TreeNode* node);
voidpostorderTreeWalk(TreeNode* node);
voidpreorderTreeWalk(TreeNode* node);
TreeNode* treeSearch(TreeNode* node, string key);
TreeNode* treeMinimum(TreeNode* node);
TreeNode* treeMaximum(TreeNode* node);
TreeNode* treeSuccessor(TreeNode* node);
TreeNode* treePredecessor(TreeNode* node);
voidtreeInsert(TreeNode *toInsert);
voidbstInsert(TreeNode *toInsert);
voidleftRotate(TreeNode *pivot);
voidrightRotate(TreeNode *pivot);
TreeNode *root;
TreeNode *nil;
int size;
intnumDeleted;
private:
voiddeleteRBNode(TreeNode* node);
};
#endif /* REDBLACKTREE_H_ */
TreeNode.cpp
#include “TreeNode.h”
TreeNode::TreeNode()
{
discipline = “”;
gender = “”;
team_or_ind = “”;
event = “”;
venue = “”;
medal = “”;
athlete = “”;
country = “”;
color = “”;
key = “”;
}
TreeNode::TreeNode(string dis, string gen, string team, string eve, string ven, string med, string ath, string coun)
{
try
{
discipline = dis;
gender = gen;
team_or_ind = team;
event = eve;
venue = ven;
medal = med;
athlete = ath;
country = coun;
key = discipline + gender + event + athlete;
color = “RED”; // Default node is red color
left = nullptr;
right = nullptr;
parent = nullptr;
}
catch (…)
{
cout<< “Invalid arguments in create TreeNode” <<endl;
}
}
TreeNode::~TreeNode()
{
discipline = “”;
gender = “”;
team_or_ind = “”;
event = “”;
venue = “”;
medal = “”;
athlete = “”;
country = “”;
color = “”;
key = “”;
left = nullptr;
right = nullptr;
parent = nullptr;
}
voidTreeNode::print()
{
cout<< “discipline: ” << discipline <<endl;
cout<< “gender: ” << gender <<endl;
cout<< “team_or_ind: ” <<team_or_ind<<endl;
cout<< “event: ” << event <<endl;
cout<< “venue: ” << venue <<endl;
cout<< “medal: ” << medal <<endl;
cout<< “athlete: ” << athlete <<endl;
cout<< “country: ” << country <<endl;
cout<< “color: ” << color <<endl;
cout<<endl;
}
TreeNode.h
#ifndef TREENODE_H_
#define TREENODE_H_
#include <iostream>
#include <string>
using namespace std;
classTreeNode
{
public:
string discipline;
string gender;
stringteam_or_ind;
string event;
string venue;
string medal;
string athlete;
string country;
string color;
string key;
TreeNode *left;
TreeNode *right;
TreeNode *parent;
/// Constructor
TreeNode(string dis, string gen, string team, string eve, string ven, string medal, string ath, string coun);
TreeNode();
~TreeNode();
void print();
};
#endif /* TREENODE_H_ */