Energy-Balanced Binary Search Tree (EB-BST): Red-Black trees use rotations to explicitly maintain a balanced BST to ensure efficiency in the dictionary operations. Splay trees are a self-adjusting alternative. On the other hand, an Energy-Balanced BST explicitly stores a potential energy parameter at each node in the tree. As dictionary operations are performed, the potential energies of tree nodes are increased or decreased. Whenever the potential energy of a node reaches a threshold level, we rebuild the subtree rooted at that node. More specifically, an EB-BST is a binary search tree T in which each node x maintains w[x] (weight of x, i.e., the number of nodes in the subtree rooted at x, including x. Assume w[nil]=0.) More importantly, each node x of T also maintains a potential energy parameter p[x]. Search, insert and delete operations are done as in standard (unbalanced) binary search trees, with one small modification. Every time we perform an insert or delete which traverses a search path from the root of T to a node v in T, we increment p[x] by 1 for each node x on that search path. If there is no node on this path such that p[x] w[x]/2, then we are done. Otherwise, let x be the highest node in T (i.e., closest to the root) such that p[x] w[x]/2. We rebuild the subtree rooted at x as a completely balanced binary search tree, and we zero out the potential fields of each node in this subtree (including x). (Note: a binary tree is called completely balanced, if for each node, the sizes of the left and right subtrees of that node differ by at most one.) (a) Show the rebuilding can be done in time linear in the size of the subtree that is being rebuilt. That is, design and analyze an algorithm that converts an arbitrary given BST into an equivalent completely balanced BST in time linear in the size of that tree. (b) Prove that if x and y are any two sibling nodes in an EB-BST, then w[y] 3w[x] +2. [Hint: observe the potential energy of their parent node.] (c) Using part (b), prove that the maximum height of any n-node EB-BST is O(log n). (d) Prove that the amortized time of any dictionary operation on any n-node EB-BST is O(log n).

Please help Quick!