Description
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.
Problem2 TocomputethedepthofagivennodeinanRBTinconstanttime,con- sider augmenting the depths of nodes as additional attributes in the nodes of the RBT. Please explain by an example why this augmentation increases the asymp- totic time complexity of inserting a node into an RBT in the worst case.
1
