BLG335E-Homework 3 Red-Black Trees Solved

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 player’s 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 Red–Black 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.



Sample Input File

Season ,Name,Team, Rebound , Assist , Point

2016−2017, Ali Muhammed,FEN,93 ,106 ,386

2016−2017,Ekpe Udoh,FEN,241 ,68 ,376

2016−2017,Jan Vesely ,FEN,154 ,49 ,328

2016−2017,Bogdan Bogdanovic ,FEN,84 ,80 ,321

2016−2017,Gigi Datome ,FEN,122 ,35 ,303

2016−2017,Kostas Sloukas ,FEN,62 ,130 ,268 2016−2017,Nikola Kalinic ,FEN,101 ,51 ,249

2016−2017,James Nunnally ,FEN,67 ,58 ,192

2016−2017,Pero Antic ,FEN,75 ,19 ,130

2016−2017,Melih Mahmutoglu ,FEN,10 ,11 ,79

2016−2017,Ahmet Duverioglu ,FEN,12 ,1 ,30

2016−2017,Anthony Bennett ,FEN,9 ,2 ,12

2016−2017, Baris Hersek ,FEN,0 ,0 ,4

2016−2017,Berk Ugurlu ,FEN,1 ,2 ,2 2016−2017,Egehan Arna ,FEN,0 ,0 ,0

2016−2017,Yordan Minchev ,FEN,2 ,0 ,0

2017−2018,Jan Vesely ,FEN,174 ,53 ,424

2017−2018,Brad Wanamaker,FEN,97 ,138 ,408 2017−2018,Kostas Sloukas ,FEN,87 ,188 ,351

2017−2018,Gigi Datome ,FEN,117 ,38 ,336

2017−2018, Nicolo                  Melli ,FEN,179 ,62 ,320

2017−2018,James Nunnally ,FEN,59 ,39 ,269

2017−2018,Marko Guduric ,FEN,56 ,69 ,241

2017−2018,Jason Thompson ,FEN,140 ,30 ,180

2017−2018, Ali Muhammed,FEN,23 ,25 ,146

2017−2018,Nikola Kalinic ,FEN,30 ,23 ,104

2017−2018,Ahmet Duverioglu ,FEN,48 ,14 ,90

2017−2018,Melih Mahmutoglu ,FEN,10 ,5 ,35

2017−2018,Sinan Guler ,FEN,9 ,7 ,23 2017−2018,Egehan Arna ,FEN,0 ,1 ,2

2017−2018, 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 . csv

End of               the 2016−2017 Season

Max Points :                  386 − Player Name:             Ali Muhammed

Max Assists :                    130 − Player Name:                Kostas Sloukas

Max 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 Minchev

End of               the 2017−2018 Season

Max Points :                        752 − Player Name: Jan Vesely

Max Assists :                    318 − Player Name:                Kostas Sloukas

Max Rebs :                     328 − Player Name: Jan Vesely
2

4

6

8

10

12

14

16

18

20

22

24

26

2 Report 

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.