Reference no: EM133404565

Question: Suppose that we can augment a red-black tree of n nodes with an additional attribute at each node, the size, which is the number of (internal) nodes in the subtree rooted at x. That is, size(x) and it is the number of internal nodes in the subtree rooted at x. Also, the size at a node x can be computed using only the information stored in x, left(x), and right(x), and that we can maintain "size" at all nodes during insertion and deletion in O(log n) time. In particular, we can maintain size so that Insert(x) and Delete(x) are supported in O(log n) time. Create a new function on a red-black tree, Count(D, x), which returns the number of elements larger than x in the red-black tree D. Your function should work even if x is not in the red-black tree. Show your function runs in O(log n) time. (pseudo code required)