Does the rebalancing propagate upwards only to update the height of the nodes in an AVL tree?

I was studying AVL trees and was wondering if the only reason one propagates upwards to the node in an insert is to change the height. It seems to me that rebalancing does not recursively propagate back with only inserts but one might have to go back to change heights (since only nodes on the path from insertion point to root node have possibly changed in height, so we need to make sure we update them).

However, I was trying to form some type of proof that we don't actually recurse to the root and actually perform rebalancing. The proof I sort of had was the following:

The only way to recurse back to fix a unbalanced node is if we have two violations due to an insertion. One at some point down the tree and another one higher up the tree. When we do an insert the node increased height which caused these two unbalances. For us to have to recurse back we need to make sure even after the rebalancing of the lowest node, that the height doesn't decrease due to the rebalancing. This is unfortunately unavoidable because for that to happen, we'd need to be in one of the cases of rebalancing where the node's height doesn't change. Since the height of a node always decreases in an insert, then we don't actually need to rebalance.

Why don't we need to rebalance? That is because the only time we need to rebalance and the height doesn't change is when the right child of the lowest violating node $x$ has two subtrees that are balanced. That is not possible to happen because for that to happen, you need two inserts to cause that unbalance, but a single insert would cause the imbalance already, so the second insert won't make the right child of $x$ have two balanced subtrees.

• Please cite the source you are referring to resp. learning from. Feb 24, 2016 at 9:38

• $\Theta(\log n)$ has nothing to do with this -- you need this much time to find the insertion position, anyway. You have to update balance values after every insertion, yes. (Why wouldn't you?) Feb 25, 2016 at 13:14