AVL trees - how to insert correctly?

Question

I was doing some research about AVL trees, and i got to know that the insertion order matters in AVL trees. But i didnt find something that could clarify me whats the best way to know which is the correct insertion order in a AVL tree. for example:

I have to insert 1 2 3 4 5, how do i know which is the best way to insert and why?

PS: its not homework, its a doubt i am having with AVL trees thanks in advance

Answer 1

When inserting a new element, you can violate the AVL tree properties. Therefore when you insert a new element, you may need to balance the tree. You can do it with either left or right rotation.

If the tree is right heavy, and if the trees right subtree is left heavy, preform a right-left rotation, otherwise a single left rotation will do it.

If the tree is left heavy and the left subtree is right heavy, perform a left-right rotation. Otherwise, a single right rotation will do it.

(Left rotation): Assume node v and right child x of node v is on the path from z to the root. W denotes the right child of x on the path —> left rotation. New balance values: b(x) = 0 and b(v) = 0. Each child moves one left.

(Right rotation): Assume node v and left child x of node v is on the path from z to the root. W denotes the left child of x on the path —> Right rotation. New balance values: b(x) = 0 and b(v) = 0.

Answer 2

I will not answer your question directly, but i really suggest you visiting this site. Really helped me to understand AVL Tree ,and how the common functions (as Insert,Delete,Search) work.Try to toggle options from the left side!

I hope this helps :)