1
$\begingroup$

**Insertion of item 5 causes imbalance at root level**]

How to balance this AVL tree after inserting node 5, using left/right rotations as indicated in the AVL tree tutorial. I have tried applying both double rotations but with no luck. Either of the double rotations still ends up producing a tree with imbalance as indicated above.

Do you mean the below solution?

enter image description here

$\endgroup$
  • $\begingroup$ Can you perform a right rotation at node 7 on the bottom right graph? $\endgroup$ – Apass.Jack Nov 12 '18 at 14:37
  • $\begingroup$ Do you mean the above diagram solution in 2 step iteration? I added it to original question since cant add images to replies here. $\endgroup$ – Deepti Kulkarni Nov 13 '18 at 0:38
  • $\begingroup$ Basically you are right. However, please check my answer. $\endgroup$ – Apass.Jack Nov 13 '18 at 6:06
1
$\begingroup$

Oh, my goodness. That AVL tree tutorial at tutorialspoint is so misleading that it is the reason why you became confused. Please ignore that tutorial.

Please study the AVL tree insertion article at GeeksForGeeks instead. Or check some textbook such as Introduction to Algorithms by By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. This recommendation should be one of the best help you can get from asking a question.

In the graph you last uploaded, https://i.stack.imgur.com/0HivT.png, the change from the first tree directly to the last tree is called a right rotation by almost every textbook, tutorial and articles I have seen. The tree in the middle never appears. The tree in the middle is just an extra unnecessary distracting step.

$\endgroup$
  • $\begingroup$ Noted. Thank you. I was trying to follow the steps given in tutorialspoint on rotations. will check the CLRS book. $\endgroup$ – Deepti Kulkarni Nov 13 '18 at 10:15

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.