Balance factor changes after local rotations in AVL tree

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

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)

StackExchange Computer Science Q#48861, answer score: 5