[Solved] BLG335E Homework 3-Red-Black Trees

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 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.

1

BLG 335E – Analysis of Algorithms I 2020/2021 Fall Homework 3

Sample Input File

Season ,Name,Team, Rebound , Assist , Point2016−2017, Ali Muhammed,FEN,93 ,106 ,3862016−2017,Ekpe Udoh,FEN,241 ,68 ,3762016−2017,Jan Vesely ,FEN,154 ,49 ,3282016−2017,Bogdan Bogdanovic ,FEN,84 ,80 ,3212016−2017,Gigi Datome ,FEN,122 ,35 ,3032016−2017,Kostas Sloukas ,FEN,62 ,130 ,268 2016−2017,Nikola Kalinic ,FEN,101 ,51 ,2492016−2017,James Nunnally ,FEN,67 ,58 ,1922016−2017,Pero Antic ,FEN,75 ,19 ,1302016−2017,Melih Mahmutoglu ,FEN,10 ,11 ,792016−2017,Ahmet Duverioglu ,FEN,12 ,1 ,302016−2017,Anthony Bennett ,FEN,9 ,2 ,122016−2017, Baris Hersek ,FEN,0 ,0 ,42016−2017,Berk Ugurlu ,FEN,1 ,2 ,2 2016−2017,Egehan Arna ,FEN,0 ,0 ,02016−2017,Yordan Minchev ,FEN,2 ,0 ,02017−2018,Jan Vesely ,FEN,174 ,53 ,4242017−2018,Brad Wanamaker,FEN,97 ,138 ,408 2017−2018,Kostas Sloukas ,FEN,87 ,188 ,3512017−2018,Gigi Datome ,FEN,117 ,38 ,3362017−2018, Nicolo Melli ,FEN,179 ,62 ,3202017−2018,James Nunnally ,FEN,59 ,39 ,2692017−2018,Marko Guduric ,FEN,56 ,69 ,2412017−2018,Jason Thompson ,FEN,140 ,30 ,1802017−2018, Ali Muhammed,FEN,23 ,25 ,1462017−2018,Nikola Kalinic ,FEN,30 ,23 ,1042017−2018,Ahmet Duverioglu ,FEN,48 ,14 ,902017−2018,Melih Mahmutoglu ,FEN,10 ,5 ,352017−2018,Sinan Guler ,FEN,9 ,7 ,23 2017−2018,Egehan Arna ,FEN,0 ,1 ,22017−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 . csvEnd of the 2016−2017 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 2017−2018 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, i^th PG, i^th SG, i^th SF, i^th PF and i^th C, that return the name of the i^th Point Guard, i^th Shooting Guard, i^th Small Forward, i^th Power Forward and i^th Center, respectively, what will be your strategy? Provide a pseudocode with explanations to implement these methods but do not implement them.