I was trying to come up with a case where one would need rebalance the following case in an AVL tree:
I think that case impossible to happen during an insert. It seems to me that its impossible to get to case 2 with only inserts (might be possible with deletes) since to get to that state we need B and C to have the same height, k-1 and increase both by 1 with one single insert. That seems impossible with only 1 single insert. Does that mean that case in rebalancing an AVL tree is impossible? Or can it maybe happen when one has to propagate rebalancing back in the AVL tree?
In fact, when does that case ever happen?