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

Improve this question
$\endgroup$
3
  • $\begingroup$ Can you perform a right rotation at node 7 on the bottom right graph? $\endgroup$
    – John L.
    Nov 12, 2018 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, 2018 at 0:38
  • $\begingroup$ Basically you are right. However, please check my answer. $\endgroup$
    – John L.
    Nov 13, 2018 at 6:06

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
1
  • $\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, 2018 at 10:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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