Balance factor changes after local rotations in AVL tree

Question

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

Answer 1

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)

Answer 2

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