# AVL Tree — Insertion

What is AVL Tree :

AVL tree is widely known as self-balancing binary search tree. It is named after its cre­ator (Georgy Adelson-Velsky and Lan­dis’ tree). In AVL Tree, the heights of child sub­trees at any node dif­fer by at most 1. At any­time if height dif­fer­ence becomes greater than 1 then tree bal­anc­ing is done to restore its property.

Search, Inser­tion and dele­tion, all oper­a­tions takes O(logn) time since the tree is balanced.

Why AVL Tree is bet­ter than nor­mal Binary Search Tree:

Aver­age time com­plex­ity in binary search tree for any oper­a­tion takes O(logn) time but there are times when your tree is skewed. In those cases the oper­a­tions on them takes O(n) time but in AVL Tree, since it is always bal­anced, it always takes O(logn) time.

How Tree bal­anced itself:

There are two basic oper­a­tions, using which tree bal­anced itself.

• Left Rota­tion
• Right Rota­tion.

AVL-Rotations

How These Rota­tion works to bal­ance the tree:

• Let ‘A’ be the new node added to the tree.
• Once ‘A’ is added, start trav­el­ling up from ‘A’ to root and find the unbal­anced node, bal­ance it and again keep trav­el­ing up.
• Say you have found the node z which is unbalanced.
• Node y is the child of z and x be the grand­child of z.

Then there will be four possibilities

1. Left-Left Case : — x is the left child of y and y is the left child of z.
2. Left-Right Case : — x is the right child of y and y is the left child of z.
3. Right-Left Case : — x is the left child of y and y is the right child of z.
4. Right-Right Case : — x is the right child of y and y is the right child of z.

Left-Left Case : — x is the left child of y and y is the left child of z.

Left-Right Case : — x is the right child of y and y is the left child of z.

Right-Left Case : — x is the left child of y and y is the right child of z.

Right-Right Case : — x is the right child of y and y is the right child of z.

Inser­tion Operation:

1. Insert the new Node using recur­sion so while back track­ing you will all the par­ents nodes to check whether they are still bal­anced or not.
2. Every node has a field called height with default value as 1.
3. When new node is added, its parent’s node height get increased by 1.
4. So as men­tioned in step 1, every ances­tors height will get updated while back track­ing to the root.
5. At every node the bal­ance fac­tor will also be checked. bal­ance fac­tor = (height of left Sub­tree — height of right Subtree).
6. If bal­ance fac­tor =1 means tree is bal­anced at that node.
7. If bal­ance fac­tor >1 means tree is not bal­anced at that node, left height is more that the right height so that means we need rota­tion. (Either Left-Left Case or Left-Right Case).
8. Say the cur­rent node which we are check­ing is X and If new node is less than the X.left then it will be Left-Left case, and if new node is greater than the X.left then it will be Left-Right case. see the pic­tures above.
9. If bal­ance fac­tor <-1 means tree is not bal­anced at that node, right height is more that the left height so that means we need rota­tion. (Either Right-Right Case or Right– Left Case)
10. Say the cur­rent node which we are check­ing is X and If new node is less than the X.right then it will be Right-Right case, and if new node is greater than the X.right then it will be Right-Left case. see the pic­tures above.

Com­plete Code:

Out­put:

```Inorder Traversal of Constructed AVL Tree : 1 2 4 5 6 9 10 11 14 20
New Root of AVL Tree is : 5
```

#### You may also like...

• Caleb

Thank you for your very clear expla­na­tion. I am not sure, but I think the nodes both after hav­ing been Left-rotated in LEFT-RIGHT case and right-rotated in RIGHT-LEFT case is posi­tioned a bit wrong in the pictures.

• tuto­ri­al­hori­zon

Thanks for the com­ment, Could you please more spe­cific about the what is wrong in the pic­ture since i am find­ing it correct.

• Caleb

OK, in fact i am not pro­fi­cient at this so was look­ing for mate­ri­als involved in the above AVL tree.
what i thought it wrong was in case of left right :

when left rotat­ing
i under­stood the posi­tion to be like

z
x T4
y T3
T1 T2

is it i under­stood that wrong?

• tuto­ri­al­hori­zon

Caleb, you under­stand­ing is absolutely right. Very good catch. I was still see­ing it wrong , I was just con­cen­trat­ing on child nodes not the par­ent nodes, my bad. Thanks a lot . I will cor­rect it in next few days, out for new year vaca­tion :). Please let me know if you find more mis­takes in same or dif­fer­ent articles.

• Caleb

it was a very good arti­cle which enough made me under­stood straight­for­ward its mech­a­nism even for a novice of algo­rithms just like me. thank you for your infor­ma­tive stuffs and i expect to learn much from tutorialhorizen.com !

• Chris­t­ian Soto

I think i see a prob­lem when you are insert­ing a new node. If it’s a leaf, wouldn’t the height be just 0? But the code here saws node.height=Math.max(getHeight(node.left), getHeight(node.right)) + 1;

• Man­ju­nath Anand

The left-right case and right-left case dia­grams are wrong. From the left-right case orig­i­nal dia­gram z>x>y can be inferred how­ever after rotat­ing it becomes z>y>x which is incor­rect. Refer to the below link for the cor­rect dia­grams :-