Answer Happy

3. In lecture 8, we have seen that extra attributes size can be maintained on a red-black tree without affecting the asymptotic performance of red-black tree operations; and with the help of size, we can find the ith smallest element in an augmented red-black tree with n internal nodes in 0 (Ign) time. If an element x is the ith smallest element in a red-black tree T, then we say that rank (x) = i in tree T. a) Assume that size is stored correctly as an attribute in each node of a red-black tree T, and x is some unique key that exists in T. Present an efficient algorithm that returns rank (x) in T. b) Can we also maintain rank in tree T as attributes in the nodes without affecting the asymptotic performance of any of the red-black tree operations? Prove your answer. Note that, we assume that size is stored correctly as an attribute in each node of tree T.