I was trying to come up with a case where one would need rebalance the following case in an AVL tree:

enter image description here

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?

  • $\begingroup$ I agree -- this can not happen in isolation. What's the context? Does your teacher distinguish single and double rotations? $\endgroup$ – Raphael Feb 24 '16 at 9:33
  • $\begingroup$ context is just me thinking about AVL tree rotations. I am just following MITs OCW course. I think they do distinguish between single and double rotations. But I was just wondering on my own mind in the simple isolated case of insertions, if that were true. $\endgroup$ – Charlie Parker Feb 24 '16 at 21:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.