3. In lecture 8, we have seen that extra attributes size can be maintained on a red-black tree without affecting the asy

[answerhappygod]

3 In Lecture 8 We Have Seen That Extra Attributes Size Can Be Maintained On A Red Black Tree Without Affecting The Asy 1 (46.96 KiB) Viewed 30 times

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.