How did the following derivation of the final weight of a weight-balanced search tree node after rotation to make it balanced occur?

Question

I was reading section 3.2 of Advanced Data Structures by Peter Brass (which is about weight-balanced search trees) for self-study. I got stuck on a proof about rebalancing properties.

$\alpha$ and $\epsilon$ are parameters, where $$\epsilon \le \alpha^2 - 2\alpha + \frac{1}{2}$$

The weight of a node is recursively defined:

If node n is a leaf (n.left == NULL and n.right == NULL), then n->weight = 1. Otherwise, n.weight is the sum of the weight of the left and right subtree.

The node n is $\alpha$-weight-balanced if $$n.left.weight \ge \alpha n.weight$$ and $$n.right.weight \ge \alpha n.weight$$

In one case, they start with $n^{old}.left.left.weight > (\alpha + \epsilon)w$ and perform a right ration around $n^{old}$. By this:
$n^{old}.left.left$ becomes $n^{new}.left$
$n^{old}.left.right$ becomes $n^{new}.right.left$.
$n^{old}.right$ becomes $n^{new}.right.right$
Because $n^{old}.left$ was balanced, with $n^{old}.left.weight = (1 - \alpha)w + \delta$, we have $$n^{new}.right.left.weight \in [\alpha(1 - \alpha) w + \alpha\ \delta), (1 - 2 \alpha - \epsilon) w + \delta ]$$

and $$n^{new}.right.right.weight = \alpha w - \delta$$.

I understand why they performed the rotations they did, and I more or less see where the original weights came from (I think), but I'm thoroughly confused as to how the final weights follow from the original weights and the operations they perform. Can someone explain this to me?

Answer 1

Here we are checking the case $2.1$,

The assumptions are

• $n^{old}.weight=w$,
• $n^{old}.right.weight < \alpha\,w,$
• $n^{old}.left.left.weight > (\alpha + \epsilon)w$, and
• $n^{old}.left$ is balanced.

Let $n^{orig}$ be original node $n$, i.e., before the insertion or deletion of a node. Since $n^{orig}$ is weight-balanced, $n^{orig}.right.weight > \alpha\, n^{orig}.weight$. The insertion or deletion of a node can only change the weight of $n$ by $1$, i.e.,

• either $n^{old}.right.weight=n^{orig}.right.weight+1$ and $n^{old}.weight=n^{orig}.weight+1$
• or $n^{old}.right.weight=n^{orig}.right.weight-1$ and $n^{old}.weight=n^{orig}.weight-1$.

The above together with $n^{old}.right.weight < \alpha\,n^{old}.weight$ implies that $n^{old}.weight=n^{orig}.weight-1$ and $$n^{old}.right.weight = \alpha\,n^{old}.right - \delta=\alpha w-\delta$$ for some $\delta\in ]0,1]$.

We have $$n^{old}.left.weight=n^{old}.weight - n^{old}.right.weight =(1 - \alpha)w + \delta.$$ Because $n^{old}.left$ is balanced, $$n^{old}.left.right.weight > \alpha\,n^{old}.left.weight=\alpha((1 - \alpha)w + \delta)=\alpha(1 - \alpha)w + \alpha\delta.$$ On the other hand, we have $$\begin{aligned} n^{old}.left.right.weight &= n^{old}.left.weight - n^{old}.left.left.weight\\ &< (1 - \alpha)w + \delta - ((\alpha + \epsilon)w)\\ &=(1 - 2 \alpha - \epsilon) w + \delta \end{aligned}$$ Hence, $$n^{old}.left.right.weight\in [\alpha(1 - \alpha)w + \alpha\delta, (1 - 2 \alpha - \epsilon) w + \delta].$$