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?