CS301 Assignment 3
Assignment 3
Submission A pdf copy of your own solutions to Problems 1 and 2 should be
submitted at SUCourse+.
Grading Full credit will be given to correct solutions that are described clearly.
Problem 1 To compute the black-height of a given node in a red-black tree (RBT)
in constant time, consider augmenting the black-heights of nodes as additional
attributes in the nodes of the RBT. Please explain why this augmentation does not
increase the asymptotic time complexity of inserting a node into an RBT in the
worst case.
Problem 2 To compute the depth of a given node in an RBT in constant time, consider augmenting the depths of nodes as additional attributes in the nodes of the
RBT. Please explain by an example why this augmentation increases the asymptotic time complexity of inserting a node into an RBT in the worst case.
1
