0
$\begingroup$

Starting with an initially empty AVL-tree, draw the resulting AVL-tree after inserting the following elements one after another. 50, 70, 30, 10, 20, 15.

I'm not sure if I am doing it correctly since I am new to AVL trees. Do I rotate if there's an inequality after the insertion or do I insert everything then only rotate the AVL tree?

Here's my attempt:

  1. First I insert 50, 70, 30, 10, 20.
      50 
     /  \
    30  70
    /
   10
    \ 
    20

Then I realise there's an imbalance so I do a rotation and get

      50 
     /  \
    20  70
   /  \
  10  30

There's one more element to insert which is 15. so, I insert it into the tree

      50 
     /  \
    20  70
   /  \
  10  30
   \
    15

and there's an imbalance again. So I rotate it

      20 
    /   \
  10    50
    \   / \
    15 30  70

My question here is do I insert everything then only rotate or rotate whenever there's an imbalance while inserting? I did the latter. May I know if my approach is correct? I'm new to AVL trees. Thank you

$\endgroup$
  • $\begingroup$ After every element insert you balance the tree. $\endgroup$ – Apoorv Ingle Nov 10 '19 at 18:58

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.