2
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ Your question is not precise. Could you please tell what particular thing you did not understand. $\endgroup$ Feb 27, 2022 at 16:31
  • $\begingroup$ @InuyashaYagami I understand why they performed the rotations that they did, but I don't understand exactly how they got the final weight from the original weight. $\endgroup$ Feb 27, 2022 at 21:16
  • $\begingroup$ @InuyashaYagami I checked the textbook again and you're correct about me mis-transcribing the rotation result. I edited to fix it. Thanks for pointing out the mistake. $\endgroup$ Feb 27, 2022 at 21:32

1 Answer 1

1
$\begingroup$

Here we are checking the case $2.1$, enter image description here

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].$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.