C++ Programming Project

Objectives• Practice on operations on Red-Black tree, such as insert, search, find
minimum/maximum, traversal, etc.
File(s) Given (right-click to download each of the files)
•
•
•
Task6.cpp (Partialy given. This is the driver program used it to check your
RedBlackTree.cpp)
RedBlackTree.h (Given. Don’t change it, but feel free to add auxillary
functions)
RedBlackTree.cpp (Partialy given, need to add your own codes inside. For
all functions, you can find their algorithms/psedocode in textbook Chp.12
and Chp.13)
1. Task Description
This is a programming task. You are required to implement a red black tree with
some of its operations. Follow the instructions closely.
1. Similar as what you did in Task #5, you will need to implement a data structure
to represent a tree node. Each node represents a Student and have the following
data fields:
struct Node
{
int id;
string firstName, lastName;
double gpa;
Node *parent;
Node *leftChild;
Node *rightChild;
string color;
};
The unique key to identify each node will be a combination of id,
firstName and lastName of the Student. Each node should also have its parent
node called parent, its left child node called leftChild, its right child node
called rightChild, 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 id firrst in increasing order; then
compare their firstName and lastName.
4. Your red black tree needs to have operations called treePreorder,
treeInorder and treePostorder which will print all tree nodes in a pre-, in- and
post-order traversal respectively.
5. Your red black tree also needs to have operations
called treeSearch, treeMinimum, treeMaximum, treeSuccessor and treePredecess
or.
6. Your red black tree also needs to have treeInsert operation. To implement this,
first you will need to define general Binary Search Tree insertion, right and left
rotate, then they will be called in your treeInsert 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. The driver program Task6.cpp is patially given, inside you will find commands
such as: 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:
Command: tree_inorder
123456 Walter
Brown
291001 Ryanne
Mccord
356533 Diego
Roberts
471444 Aidan
Morgan
579614 Tamara
Garrido
625921 Qian
Shaffer
754880 Aron
Liu
891001 Ryanne
Mccord
3.66
3.55
2.10
3.14
3.94
3.56
3.48
3.55
RED
BLACK
RED
BLACK
BLACK
RED
BLACK
RED
It should print tree is empty if the RBT 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:
Command: tree_preorder
471444 Aidan
Morgan
291001 Ryanne
Mccord
123456 Walter
Brown
356533 Diego
Roberts
625921 Qian
Shaffer
579614 Tamara
Garrido
754880 Aron
Liu
891001 Ryanne
Mccord
3.14
3.55
3.66
2.10
3.56
3.94
3.48
3.55
BLACK
BLACK
RED
RED
RED
BLACK
BLACK
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:
Command: tree_postorder
123456 Walter
Brown
356533 Diego
Roberts
291001 Ryanne
Mccord
579614 Tamara
Garrido
891001 Ryanne
Mccord
754880 Aron
Liu
625921 Qian
Shaffer
471444 Aidan
Morgan
3.66
2.10
3.55
3.94
3.55
3.48
3.56
3.14
RED
RED
BLACK
BLACK
RED
BLACK
RED
BLACK
It should print tree is empty if the tree is empty.
tree_minimum
It should call treeMinimum and print the first node in in-order traversal of the
RBT (i.e. the smallest node inside the tree) using the following format:
Command: tree_minimum
The MINIMUM is:
123456 Walter
Brown
3.66
BLACK
It should print tree is empty if the tree is empty.
tree_maximum
It should call treeMaximum and print the last node in in-order traversal (i.e. the
largest node inside the tree) using the following format:
Command: tree_maximum
The MAXIMUM is:
891001 Ryanne
Mccord
3.55
RED
It should print tree is empty if the tree is empty.
tree_predecessor,id,firstName,lastName
It should call treePredecessor and search for the predecessor of the given Student.
An example of this command is:
tree_predecessor,471444,Aidan,Morgan
If it finds its predecessor, then it should print the result as:
Command: tree_predecessor
471444 Aidan
Morgan is FOUND.
Its Predecessor is:
356533 Diego
Roberts
2.10
RED
If it cannot find its predecessor, then it should print, for example:
Command: tree_predecessor
123456 Walter
Brown is FOUND.
Its Predecessor does NOT EXIST
tree_successor,id,firstName,lastName
It should call treeSuccessor and search for the successor of the given address. An
example of this command is:
tree_successor,356533,Diego,Roberts
If it find its successor, then it should print the result as:
Command: tree_successor
356533 Diego
Roberts is FOUND.
Its Successor is:
471444 Aidan
Morgan
3.14
If it cannot find its successor, then it should print:
Command: tree_successor
891001 Ryanne
Mccord is FOUND.
Its Successor does NOT EXIST
RED
tree_search,id,firstName,lastName
It should call treeSearch and search the RBT with the given information. An
example of this command is:
tree_search,356533,Diego,Roberts
If it can find the Student inside the data structure, then it should print the result by
showing:
Command: tree_search
356533 Diego
Roberts is FOUND.
If it cannot find the Student, then it should print:
Command: tree_search
471444 Sherry
Morgan is NOT FOUND.
tree_insert,id,firstName,lastName,gpa
It should call treeInsert and attempt to insert the given Student. If there exists
another Student item with the same id, firstName, and lastName, then it should not
be inserted inside. An example of this command is:
tree_insert,123456,Walter,Brown,3.66
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:
Command: quit
The number of nodes deleted: 8
2. Implementation/Documentation Requirements
• You need implement this program using C++ and it has to read from the
input file input1.txt, input2, etc.
• Your program needs to compile and execute in general.asu.edu.
To compile, for example under c++ version 11 (to use certain function such
as stod or stoi), type for example:
g++ -std=c++11 -o prog *.cpp *.h
To run with the input test cases, type for example:
./prog myout1.txt
Copy any codes from other people’s programs is considered to be cheating and
will lead to a report to the Dean and you will be penalized. Also check the rules
stated in the syllabus of the course regarding the academic integrity.
3. Other Requirements
•
You need to implement this program by using C++ and your program need
to compile, execute and pass the test cases.
•
For this task, you are NOT allowed to use any predefined data
structures (such as vector, list in C++ STL etc.) except arrays and strings,
you need to build your own BST data structures and operations associated
with it (such as insertion, extraction, searching, etc) from scratch.Your code
should be well documented and commented.
4. Input and Output Test Cases
Input
The following four input files are provided for you for testing purpose. They were
designed to check your program step by step, for example, test case #1 is designed
to make sure the red-black tree insertion works, test case #2 is designed to make
sure tree_minimum, tree_maximum and tree_search functions work, etc. I
recommend that you check your code with input1.txt first, followed by input2.txt,
input3.txt, last check with input4.txt.
•
•
•
•
input1.txt
input2.txt
input3.txt
input4.txt
Output
The following files are the expected outputs of the corresponding input files from
the previous section (Right-click and use “Save As”). Note: for this task, your
output should be the SAME as our solution output, if not, your program
didn’t pass the test cases! Consider using DiffMerge to compare your program’s
output with our solution output.
•
•
•
output1.txt
output2.txt
output3.txt
•
output4.txt
5. Submission
1) Test your program by using above four test cases, compare your program’s
output with our solution output, make sure they contain exactly the same
strings/characters before you submit the Three (3) source file:
•
•
•
Task6.cpp
RedBlackTree.h
RedBlackTree.cpp
2) Submit ONLY the source code file(s), namely Task6.cpp,
RedBlackTree.h and RedBlackTree.cpp, make sure your file’s name is
EXACTLY Task6.cpp and RedBlackTree.h and RedBlackTree.cpp (NOT the
task6.cpp)
6. Rubric
• – Documentation (correct and complete code description and comments,
header for each function/method)
•
– Indentation and Spacing (easy to read)
•
– void insertNode(Node *node) function correctly. (*This is the
general insertion for a BST)
•
– Node* treeSearch(int id, string firstName,
string lastName)function correctly.
•
– preorderTraversal/inorderTraversal/postorderTrave
rsal(Node *node)function correctly.
•
– findMinimumNode/findMaximumNode(Node
*node) functions correctly.
•
– findPredecessorNode/findSuccessorNode(Node
*node) functions correctly.
•
– leftRotate/rightRotate(Node *node) functions correctly.
•
– fixUp(Node *node)functions correctly.
•
– Correct output for the four test cases