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   band $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 most simple formula for balance factors. Is there any simpler approach to calculate balance factors, which would always work even if the tree becomes unbalanced?EDIT: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$$
Balance factor changes after local rotations in AVL tree
algorithm analysis;data structures;search trees;balanced search trees
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.htmUsing 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 RotationTo calculate the new balances after a single left rotation; assume we  have the following case:         A                                     B        / \                                   / \       /   \                                 /   \      a     B           ==>                 A     c           / \                             / \          /   \                           /   \         b     c                         a     bThe 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     aIf 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)