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.)

(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).