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:
- 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