Description
Problem: In this project, you are expected to implement certain basic Red–Black Tree operations
and then augment your data structure with extra operations for order statistics.
Part A. Implementation (70 points)
1. (40 points)
Implement a basic Red–Black Tree that supports insertion and printing. You do NOT have to
implement updating and deletion.
The key for each of the nodes should be the corresponding person’s name. Age and gender values
should be kept as extra attributes within your nodes.
Your insertion operation should insert a new node into the relevant position in the Red–Black Tree
and then recolor and rotate existing nodes in order to meet the constraints and rebalance the tree.
2. (30 points)
Augment your Red–Black Tree implementation with two new methods, nth woman and nthman,
that return the name of the nth woman and man respectively.
Include the num_woman[x] and num_man[x] fields in your tree nodes, respectively holding the
number of women and men in the sub-tree rooted at x, including x itself. Your implementation
should make use of these fields in parallel with the size[x] field in the OS_SELECT example1
. Make
sure you update these fields as necessary whenever you modify the tree by another operation.
Execution:
You are given an input file (input.txt) containing rows of data, each denoting a person. A name, an
age value and a gender value is encoded for each person. Read the contents of the file and use your
insertion operation to insert each person into your Red–Black Tree.
Your program should run from the command line with the following format:
$ ./
input_file: The relative path to the input file, e.g. ‘input.txt’.
An example execution command could be as below:
./040080154 input.txt
_______________________________________________________________________________
1Refer to the lecture slides if you would like to review the example.
For your output, use your printing operation to display the final state of your Red–Black Tree after
all the elements from the input file have been added. Afterwards, use the num_woman and
num_man methods you implemented to find and print the 3rd woman and the 4th man. You may
display your output on the console rather than using output files.
Your printing operation should use the in-order traversal to recursively print the nodes. The output
should properly represent sub-trees by indentation. Example: The output should properly
represent the depth of nodes by indentation as shown below (use “─” and “┌” instead of spaces).
You must state if a node is black (B) or red (R).
Sample input:
Glen F 29
Ryan F 17
Alex M 13
Dane F 14
Leah F 23
Jude F 26
Evan M 18
Izzy M 27
Fran M 30
Use in-order (reflection of the RB-tree)
>> ┌───(B)Alex-13-M Left
>> ┌───(R)Dane-14-F
>> └───(B)Evan-18-M
>> └───(R)Fran-30-M
>>(B)Glen-29-F
>> ┌───(R)Izzy-27-M
>> ┌───(B)Jude-26-F
>> └───(R)Leah-23-F
>> └───(B)Ryan-17-F
Right
3rd woman: Jude
4th man: Izzy
Part B. Report (30 points)
In your report, you will be expected to address the following questions. You do NOT have to provide
details about your code. However, we ask you to put a screen-shot of your program’s output.
1. (15 points)
Briefly explain what you would do to correctly update the name of a person as a node in the Red–
Black Tree.
2. (15 points)
Briefly explain what you would do to correctly increment (by 1) the ages of all people in the Red–
Black Tree.
Additional Notes:
1. Submissions will be done through the Ninova server. You must submit all your source code in a
single cpp file and a softcopy report (PDF).
2. Make sure that GNU C++ compiler (g++ 4.8.5) compiles your project, and the application runs in
Linux smoothly. You can use ITU ssh server to compile and test your application. This is important
because we will evaluate your homework in Unix using g++.
3. Use comments wherever necessary in your code to explain what you did.
4. You are not allowed to use the standard template library (STL).
Note: If you have any questions, please feel free to contact Res. Asst. Cumali Türkmenoğlu via e-mail
(turkmenogluc@itu.edu.tr).
Academic dishonesty including but not limited to cheating, plagiarism,
collaboration is unacceptable and subject to disciplinary actions
