How many balance checks are needed in an AVL tree insertion / deletion

Question

I've been reading literature on AVL tree and found it is not elaborated very much on how many balance checks are needed in an AVL tree insertion / deletion.

For example, after inserting a node, do we need to check balance from the new node all the way up to the root? Or could we stop after a rotation(s) is committed?

How about in a deletion with the strategy of copying the rightmost node in the left sub-tree? Check up from the newly deleted (rightmost node in the left sub-tree) node to the root? could we stop after a rotation(s) is committed?

Answer 1

After an insertion, you need to update the balance factor of each "parent" all the way up the tree until the root; so it's a max of O(log n) updates. But you will only have to do a single restructuring to restore the tree to it's invariants.

After a delete, like insertion, you will have to update the balance factor all the way up the tree; so again it's O(log n) updates. But, unlike insert, you may have multiple restructuring rotations to restore the tree to it's invariants.

http://en.wikipedia.org/wiki/AVL_tree

Answer 2

I've been searching a bit deeper, and I've found when you can stop checking:

• When the balance factor of an upper node of a node inserted is 0.
• After a rotation. This is a consequence of the previous affirmation.

http://www.superstarcoders.com/blogs/posts/efficient-avl-tree-in-c-sharp.aspx

http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx