1 Red-Black Trees
Implementation
In this part, you are going to build a basketball player database with Red-Black Tree. The key for each of the nodes should be the corresponding players name. Point, rebound and assist values should be kept as extra attributes within your nodes. Point, rebound and assist values should be updated for each season accordingly. Your insertion operation should insert a new node into the relevant position in the RedBlack Tree and then recolor and rotate existing nodes in order to meet the constraints and rebalance the tree. At the end of each season you should print all-time point, rebound, and assist leaders. You should use pre-order traversal to recursively print the nodes in red-black tree. The output should properly represent the depth of nodes by indentation as shown in sample run. You should print the tree only at the end of the first season. You must also state whether a node is black (BLACK) or red (RED). You are given euroleague.csv file which contains the information about players. Your code should take filename as an argument.
1
BLG 335E Analysis of Algorithms I 2020/2021 Fall Homework 3
Sample Input File
| Season ,Name,Team, Rebound , Assist , Point20162017, Ali Muhammed,FEN,93 ,106 ,38620162017,Ekpe Udoh,FEN,241 ,68 ,37620162017,Jan Vesely ,FEN,154 ,49 ,32820162017,Bogdan Bogdanovic ,FEN,84 ,80 ,32120162017,Gigi Datome ,FEN,122 ,35 ,30320162017,Kostas Sloukas ,FEN,62 ,130 ,268 20162017,Nikola Kalinic ,FEN,101 ,51 ,24920162017,James Nunnally ,FEN,67 ,58 ,19220162017,Pero Antic ,FEN,75 ,19 ,13020162017,Melih Mahmutoglu ,FEN,10 ,11 ,7920162017,Ahmet Duverioglu ,FEN,12 ,1 ,3020162017,Anthony Bennett ,FEN,9 ,2 ,1220162017, Baris Hersek ,FEN,0 ,0 ,420162017,Berk Ugurlu ,FEN,1 ,2 ,2 20162017,Egehan Arna ,FEN,0 ,0 ,020162017,Yordan Minchev ,FEN,2 ,0 ,020172018,Jan Vesely ,FEN,174 ,53 ,42420172018,Brad Wanamaker,FEN,97 ,138 ,408 20172018,Kostas Sloukas ,FEN,87 ,188 ,35120172018,Gigi Datome ,FEN,117 ,38 ,33620172018, Nicolo Melli ,FEN,179 ,62 ,32020172018,James Nunnally ,FEN,59 ,39 ,26920172018,Marko Guduric ,FEN,56 ,69 ,24120172018,Jason Thompson ,FEN,140 ,30 ,18020172018, Ali Muhammed,FEN,23 ,25 ,14620172018,Nikola Kalinic ,FEN,30 ,23 ,10420172018,Ahmet Duverioglu ,FEN,48 ,14 ,9020172018,Melih Mahmutoglu ,FEN,10 ,5 ,3520172018,Sinan Guler ,FEN,9 ,7 ,23 20172018,Egehan Arna ,FEN,0 ,1 ,220172018, Baris Hersek ,FEN,0 ,0 ,0 |
1
3
5
7
9
11
13
15
17
19
21
23
25
27
29
31
Figure 1: Red-Black Tree at the end of the first season
2
Sample Run
| g++ studentID . cpp o studentID./ studentID sample . csvEnd of the 20162017 SeasonMax Points : 386 Player Name: Ali MuhammedMax Assists : 130 Player Name: Kostas SloukasMax Rebs : 241 Player Name: Ekpe Udoh(BLACK) Jan Vesely(BLACK) Baris Hersek(RED) Ali Muhammed(BLACK) Ahmet Duverioglu(BLACK) Anthony Bennett(RED) Ekpe Udoh(BLACK) Bogdan Bogdanovic(RED) Berk Ugurlu(RED) Egehan Arna(BLACK) Gigi Datome(RED) James Nunnally(BLACK) Nikola Kalinic(BLACK) Kostas Sloukas(RED) Melih Mahmutoglu(BLACK) Pero Antic(RED) Yordan MinchevEnd of the 20172018 SeasonMax Points : 752 Player Name: Jan VeselyMax Assists : 318 Player Name: Kostas SloukasMax Rebs : 328 Player Name: Jan Vesely |
2
4
6
8
10
12
14
16
18
20
22
24
26
2 Report (30 pts)
Complexity
Write down the asymptotic upper bound for the insertion and search operations of RedBlack Tree for worst case and average case with detailed explanations.
RBT vs BST
Compare Red-Black Tree with Standard Binary Search Tree in your own words.
Augmenting Data Structures
Suppose that you are given the position (Point Guard PG, Shooting Guard SG, Small Forward SF, Power Forward PF or Center C) of the players. If you were to augment your Red-Black Tree with 5 new methods, ith PG, ith SG, ith SF, ith PF and ith C, that return the name of the ith Point Guard, ith Shooting Guard, ith Small Forward, ith Power Forward and ith Center, respectively, what will be your strategy? Provide a pseudocode with explanations to implement these methods but do not implement them.
Reviews
There are no reviews yet.