Description

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