5
$\begingroup$

I try to understand balance factors change after local rotations in AVL trees. Given the rotate_left operation:

  x            y'
 / \          / \
a   y   =>   x'  c
   / \      / \
  b   c    a   b

and $b(x)$, $b(y)$ - balance factors for $x$ and $y$ nodes - I want to find $b(x')$ and $b(y')$.

In my reasoning I will use the Iverson bracket notation, that denotes a number that is 1 if the condition in square brackets is satisfied, and 0 otherwise: $$ [P]=\begin{cases} 1, \text{ if } P \text{ is true}; \\ 0, \text{ otherwise}.\end{cases} $$

Balance factor for the node $x'$ can be calculated like this: $$b(x') = h(b) - h(a)$$

where $h(b)$ and $h(a)$ - the heights of sub-trees $a$ and $b$.

Let's substitute $h(b) = h(y) - b(y)[b(y) > 0] - 1$ and $h(a) = h(x) - b(x)[b(x) > 0] - 1$:

$$b(x') = (h(y) - b(y)[b(y) > 0] - 1) - (h(x) - b(x)[b(x) > 0] - 1)$$

Some simplification:

$$b(x') = h(y) - b(y)[b(y) > 0] - h(x) + b(x)[b(x) > 0]$$

Now substitute $h(y) = h(x) + b(x)[b(x) \le 0] - 1 $:

$$b(x') = h(x) + b(x)[b(x) \le 0] - 1 - b(y)[b(y) > 0] - h(x) + b(x)[b(x) > 0]$$

Obviously, $[b(x) \le 0] + [b(x) > 0] = 1$:

$$b(x') = h(x) + b(x) - 1 - b(y)[b(y) > 0] - h(x)$$

Simplify again:

$$b(x') = b(x) - b(y)[b(y) > 0] - 1$$

In the same way I can find balance factor for $y'$. Skipping intermediate steps I get: $$ b(y') = h(c) - h(x') =\\ ...\\ = b(x) + b(y)[b(y) \le 0] - b(x')[b(x') > 0] - 2$$

Somehow I have feeling that this is not the simplest formula for balance factors.

Is there any simpler approach to calculate balance factors, which would always work even if the tree becomes unbalanced?

EDIT:

The simplest formulas I managed to get look like this (see my own answer for details): $$b(y′)=b(y)+b(x')[b(x')\le0]−1$$ $$b(x′)=b(x)−b(y)[b(y)>0]−1$$

$\endgroup$
  • $\begingroup$ Hint: the balances change in exactly the same fashion, every time. Annotating the four graphics (one per type of rotation) is sufficient to describe the behaviour. $\endgroup$ – Raphael Oct 29 '15 at 18:34
  • $\begingroup$ @Raphael, I want to have a general formula, which keeps balance factors correct even if the tree becomes unbalanced. $\endgroup$ – Maxym Oct 30 '15 at 10:41
3
$\begingroup$

EDIT:
@Maxym's answer is correct after all and is actually equivalent. I had simply misinterpreted the notation. Leaving this answer anyway as the cited link provides a useful explanation.

While @Maxym's answer is on the right track, his formula didn't quite work for me. After beating my head against the wall for quite some time, I found this link written by Brad Appleton that seems to be the right formula (at least my unit tests all work now and my tree stays coherent): http://oopweb.com/Algorithms/Documents/AvlTrees/Volume/AvlTrees.htm

Using Maxym's notation, it would be something like this for the left rotation (also I reversed the order -- since the formula for the new y depends on the new x, it makes sense to me to list x first):

$$b(x′) = b(x) − 1 - max(b(y), 0)$$ $$b(y′) = b(y) - 1 + min(b(x′), 0)$$

And for the right rotation:

$$b(x′) = b(x) + 1 - min(b(y), 0)$$ $$b(y′) = b(y) + 1 + max(b(x′), 0)$$

In case that page goes away, I'm including the relevant portion:

Calculating New Balances After a Rotation

To calculate the new balances after a single left rotation; assume we have the following case:

         A                                     B
        / \                                   / \
       /   \                                 /   \
      a     B           ==>                 A     c
           / \                             / \
          /   \                           /   \
         b     c                         a     b

The left is what the tree looked like BEFORE the rotation and the right is what the tree looks like after the rotation. Capital letters are used to denote single nodes and lowercase letters are used to denote subtrees.

The "balance" of a tree is the height of its right subtree less the height of its left subtree. Therefore, we can calculate the new balances of "A" and "B" as follows (ht is the height function):

NewBal(A) = ht(b) - ht(a)

OldBal(A) = ht(B) - ht(a) = ( 1 + max (ht(b), ht(c)) ) - ht(a)

subtracting the second equation from the first yields:

NewBal(A) - OldBal(A) = ht(b) - ( 1 + max (ht(b), ht(c)) ) + ht(a) - ht(a)

canceling out the ht(a) terms and adding OldBal(A) to both sides yields:

NewBal(A) = OldBal(A) - 1 - (max (ht(b), ht(c)) - ht(b) )

Noting that max(x, y) - z = max(x-z, y-z), we get:

NewBal(A) = OldBal(A) - 1 - (max (ht(b) - ht(b), ht(c) - ht(b)) )

But ht(c) - ht(b) is OldBal(B) so we get:

NewBal(A) = OldBal(A) - 1 - (max (0, OldBal(B)) ) = OldBal(A) - 1 - max (0, OldBal(B))

Thus, for A, we get the equation:

NewBal(A) = OldBal(A) - 1 - max (0, OldBal(B))

To calculate the Balance for B we perform a similar computation:

NewBal(B) = ht(c) - ht(A) = ht(c) - (1 + max(ht(a), ht(b)) )

OldBal(B) = ht(c) - ht(b)

subtracting the second equation from the first yields:

NewBal(B) - OldBal(B) = ht(c) - ht(c) + ht(b) - (1 + max(ht(a), ht(b)) )

canceling, and adding OldBal(B) to both sides gives:

NewBal(B) = OldBal(B) - 1 - (max(ht(a), ht(b)) - ht(b)) = OldBal(B) - 1 - (max(ht(a) - ht(b), ht(b) - ht(b))

But ht(a) - ht(b) is - (ht(b) - ht(a)) = -NewBal(A), so ...

NewBal(B) = OldBal(B) - 1 - max( -NewBal(A), 0)

Using the fact that min(x,y) = -max(-x, -y) we get:

NewBal(B) = OldBal(B) - 1 + min( NewBal(A), 0)

So, for a single left rotation we have shown the the new balances for the nodes A and B are given by the following equations:

NewBal(A) = OldBal(A) - 1 - max(OldBal(B), 0)
NewBal(B) = OldBal(B) - 1 + min(NewBal(A), 0)

Now let us look at the case of a single right rotation. The case we will use is the same one we used for the single left rotation only with all the left and right subtrees switched around so that we have the mirror image of the case we used for our left rotation.

         A                                     B
        / \                                   / \
       /   \                                 /   \
      B     a           ==>                 c     A
     / \                                         / \
    /   \                                       /   \
   c     b                                     b     a

If we perform the same calculations that we made for the left rotation, we will see that the new balances for a single right rotation are given by the following equations:

NewBal(A) = OldBal(A) + 1 - min(OldBal(B), 0)
NewBal(B) = OldBal(B) + 1 + max(NewBal(A), 0)

$\endgroup$
  • $\begingroup$ Upvote for useful link, I didn't know about it when I tried to make the formula myself. Indeed, $b(x′)[b(x′)\le0]=min(b(x′),0)$ and $b(y)[b(y)>0]=max(b(y),0)$. Could you explain in which cases my formula didn't work for you? I use it in my implementation and I want to know about possible pitfalls. $\endgroup$ – Maxym Dec 23 '16 at 19:29
  • $\begingroup$ The place where it failed for me was one particular case when a right rotate was needed before a left rotate. In one case, I ended up with both x and y having a balance of 2 after the right rotation. With this updated algorithm, that resolved correctly. I think the real issue is that max(OldBal(B), 0) is not always 1; it could be 2. $\endgroup$ – Gil Hamilton Dec 23 '16 at 19:44
  • $\begingroup$ My test was really simple. Insert in sequential order numbers 0 - 99, then delete [0, 3, 6,...], then delete [0, 4, 8, ...] (ignoring previously deleted), then delete all of them. Then do the same thing in reverse: insert 99,98,...0, then delete every third one [99, 96, 93, 90, ... ], then every fourth [99, 95, 91, 87, ...] then delete all [99, 98, 97, ...]. Check balance of entire tree by manually calculating heights after every insertion and deletion. Can't remember number being deleted but the tree went from 31=>41=>35 to 35 on top with 31 and 41 below it. $\endgroup$ – Gil Hamilton Dec 23 '16 at 19:52
  • $\begingroup$ Difficult to put in a comment but using parentheses to show the tree layout, the problematic sub-tree (before rotation) was this: (31=>(26=>((25),(29))),(41=>(35=>((34),(37=>(38)))),(46=>(43)))) $\endgroup$ – Gil Hamilton Dec 23 '16 at 20:07
  • $\begingroup$ Well, it shouldn't have happened because the formulas are equal. But I think I know what went wrong. You might misinterpret Iverson bracket notation. That's true that $[b(y)>0]$ can be only 1 or 0, but $b(y)[b(y)>0]$ can be either $b(y)$ or 0 (thus it can be 2 as well). $\endgroup$ – Maxym Dec 23 '16 at 20:34
4
$\begingroup$

I found the answer myself. We know that $$b(x)=b(x')+b(y)[b(y)>0]+1$$ $$b(y′)=b(x)+b(y)[b(y)\le0]−b(x′)[b(x′)>0]−2$$ thus $$b(y′)=b(x')+b(y)[b(y)>0]+1+b(y)[b(y)\le0]−b(x′)[b(x′)>0]−2$$ where $$b(x')−b(x′)[b(x′)>0]=b(x')[b(x')\le0].$$ So, the new balance factors will look like this: $$b(y′)=b(y)+b(x')[b(x')\le0]−1$$ $$b(x′)=b(x)−b(y)[b(y)>0]−1$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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