17-3 Amortized weight-balanced trees

Consider an ordinary binary search tree augmented by adding to each node $x$ the attribute $x.size$ giving the number of keys stored in the subtree rooted at $x$. Let $\alpha$ be a constant in the range $1 / 2 \le \alpha < 1$. We say that a given node $x$ is $\alpha$-balanced if $x.left.size \le \alpha \cdot x.size$ and $x.right.size \le \alpha \cdot x.size$. The tree as a whole is $\alpha$-balanced if every node in the tree is $\alpha$-balanced. The following amortized approach to maintaining weight-balanced trees was suggested by G. Varghese.

a. A $1 / 2$-balanced tree is, in a sense, as balanced as it can be. Given a node $x$ in an arbitrary binary search tree, show how to rebuild the subtree rooted at $x$ so that it becomes $1 / 2$-balanced. Your algorithm should run in time $\Theta(x.size)$, and it can use $O(x.size)$ auxiliary storage.

b. Show that performing a search in an $n$-node $\alpha$-balanced binary search tree takes $O(\lg n)$ worst-case time.

For the remainder of this problem, assume that the constant $\alpha$ is strictly greater than $1 / 2$. Suppose that we implement $\text{INSERT}$ and $\text{DELETE}$ as usual for an $n$-node binary search tree, except that after every such operation, if any node in the tree is no longer $\alpha$-balanced, then we "rebuild" the subtree rooted at the highest such node in the tree so that it becomes $1 / 2$-balanced.

We shall analyze this rebuilding scheme using the potential method. For a node $x$ in a binary search tree $T$, we define

$$\Delta(x) = |x.left.size - x.right.size|,$$

and we define the potential of $T$ as

$$\Phi(T) = c \sum_{x \in T: \Delta(x) \ge 2} \Delta(x),$$

where $c$ is a sufficiently large constant that depends on $\alpha$.

c. Argue that any binary search tree has nonnegative potential and that a $1 / 2$-balanced tree has potential $0$.

d. Suppose that $m$ units of potential can pay for rebuilding an $m$-node subtree. How large must $c$ be in terms of $\alpha$ in order for it to take $O(1)$ amortized time to rebuild a subtree that is not $\alpha$-balanced?

e. Show that inserting a node into or deleting a node from an $n$-node $\alpha$-balanced tree costs $O(\lg n)$ amortized time.

a. Since we have $O(x.size)$ auxiliary space, we will take the tree rooted at $x$ and write down an inorder traversal of the tree into the extra space. This will only take linear time to do because it will visit each node thrice, once when passing to its left child, once when the nodes value is output and passing to the right child, and once when passing to the parent. Then, once the inorder traversal is written down, we can convert it back to a binary tree by selecting the median of the list to be the root, and recursing on the two halves of the list that remain on both sides. Since we can index into the middle element of a list in constant time, we will have the recurrence

$$T(n) = 2T(n / 2) + 1,$$

which has solution that is linear. Since both trees come from the same underlying inorder traversal, the result is a $\text{BST}$ since the original was. Also, since the root at each point was selected so that half the elements are larger and half the elements are smaller, it is a $1 / 2$-balanced tree.

b. We will show by induction that any tree with $\le \alpha^{-d} + d$ elements has a depth of at most $d$. This is clearly true for $d = 0$ because any tree with a single node has depth $0$, and since $\alpha^0 = 1$, we have that our restriction on the number of elements requires there to only be one. Now, suppose that in some inductive step we had a contradiction, that is, some tree of depth $d$ that is $\alpha$ balanced but has more than $\alpha - d$ elements.

We know that both of the subtrees are alpha balanced, and by being alpha balanced at the root, we have

$$root.left.size \le \alpha \cdot root.size,$$

which implies

$$root.right.size > root.size - \alpha \cdot root.size - 1.$$

So,

$$\begin{aligned} root.right.size & > (1 - \alpha)root.size - 1 \\ & > (1 - \alpha)\alpha - d + d - 1 \\ & = (\alpha - 1 - 1)\alpha - d + 1 + d - 1 \\ & \ge \alpha - d + 1 + d - 1, \end{aligned}$$

which is a contradiction to the fact that it held for all smaller values of $d$ because any child of a tree of depth d has depth $d - 1$.

c. The potential function is a sum of $\Delta(x)$ each of which is the absolute value of a quantity, so, since it is a sum of nonnegative values, it is nonnegative regardless of the input $\text{BST}$.

If we suppose that our tree is $1 / 2$-balanced, then, for every node $x$, we'll have that $\Delta(x) \le 1$, so, the sum we compute to find the potential will be over no nonzero terms.

d.

$$\begin{aligned} \hat c_i & = c_i + \Phi(D_i) - \Phi(D_{i - 1}) \\ O(1) & = m + \Phi(D_i) - \Phi(D_{i - 1}) \\ \Phi(D_{i - 1}) & = m + \Phi(D_i) \\ \Phi(D_{i - 1}) & \ge m. \end{aligned}$$

$$\begin{aligned} \Delta(x) & = x.left.size - x.right.size \\ & \ge \alpha \cdot m - ((1 - \alpha) m - 1) \\ & = (2\alpha - 1)m + 1. \end{aligned}$$

$$\begin{aligned} m & \le c((2\alpha - 1)m + 1) \\ c & \ge \frac{m}{(2\alpha - 1)m + 1} \\ & \ge \frac{1}{2\alpha}. \end{aligned}$$

e. Suppose that our tree is $\alpha$ balanced. Then, we know that performing a search takes time $O(\lg(n))$. So, we perform that search and insert the element that we need to insert or delete the element we found. Then, we may have made the tree become unbalanced. However, we know that since we only changed one position, we have only changed the $\Delta$ value for all of the parents of the node that we either inserted or deleted. Therefore, we can rebuild the balanced properties starting at the lowest such unbalanced node and working up.

Since each one only takes ammortized constant time, and there are $O(\lg(n))$ many trees made unbalanced, tot total time to rebalanced every subtree is $O(\lg(n))$ ammortized time.