# AVL Tree – Insertion

What is AVL Tree :

AVL tree is widely known as self-balancing binary search tree. It is named after its creator (Georgy Adelson-Velsky and Landis’ tree). In AVL Tree, the heights of child subtrees at any node differ by at most 1. At anytime if height difference becomes greater than 1 then tree balancing is done to restore its property.

Search, Insertion and deletion, all operations takes O(logn) time since the tree is balanced.

Why AVL Tree is better than normal Binary Search Tree:

Average time complexity in binary search tree for any operation takes O(logn) time but there are times when your tree is skewed. In those cases the operations on them takes O(n) time but in AVL Tree, since it is always balanced, it always takes O(logn) time.

How Tree balanced itself:

There are two basic operations, using which tree balanced itself.

• Left Rotation
• Right Rotation.

How These Rotation works to balance the tree:

• Let ‘A’ be the new node added to the tree.
• Once ‘A’ is added, start travelling up from ‘A’ to root and find the unbalanced node, balance it and again keep traveling up.
• Say you have found the node z which is unbalanced.
• Node y is the child of z and x be the grandchild 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.

Insertion Operation:

1. Insert the new Node using recursion so while backtracking you will all the parent’s nodes to check whether they are still balanced or not.
2. Every node has a field called height with a default value of 1.
3. When a new node is added, its parent’s node height get increased by 1.
4. So as mentioned in step 1, every ancestor’s height will get updated while backtracking to the root.
5. At every node, the balance factor will also be checked. balance factor = (height of left Subtree – the height of right Subtree).
6. If balance factor =1 means the tree is balanced at that node.
7. If balance factor >1 means the tree is not balanced at that node, left height is more than the right height so that means we need rotation. (Either Left-Left Case or Left-Right Case).
8. Say the current node which we are checking is X and If the new node is less than the X.left then it will be the Left-Left case, and if the new node is greater than the X.left then it will be the Left-Right case. see the pictures above.
9. If balance factor <-1 means the tree is not balanced at that node, right height is more than the left height so that means we need rotation. (Either Right-Right Case or Right- Left Case)
10. Say the current node which we are checking is X and If the new node is less than the X.right then it will be Right-Right case, and if the new node is greater than the X.right then it will be Right-Left case. see the pictures above.

Code:

Output:

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

### 10 thoughts on “AVL Tree – Insertion”

1. Thank you for your very clear explanation. I am not sure, but I think the nodes both after having been Left-rotated in LEFT-RIGHT case and right-rotated in RIGHT-LEFT case is positioned a bit wrong in the pictures.

• Thanks for the comment, Could you please more specific about the what is wrong in the picture since i am finding it correct.

• OK, in fact i am not proficient at this so was looking for materials involved in the above AVL tree.
what i thought it wrong was in case of left right :

when left rotating
i understood the position to be like

z
x T4
y T3
T1 T2

is it i understood that wrong?

• Caleb, you understanding is absolutely right. Very good catch. I was still seeing it wrong , I was just concentrating on child nodes not the parent nodes, my bad. Thanks a lot . I will correct it in next few days, out for new year vacation :). Please let me know if you find more mistakes in same or different articles.

• it was a very good article which enough made me understood straightforward its mechanism even for a novice of algorithms just like me. thank you for your informative stuffs and i expect to learn much from tutorialhorizen.com !

2. I think i see a problem when you are inserting 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;

3. The left-right case and right-left case diagrams are wrong. From the left-right case original diagram z>x>y can be inferred however after rotating it becomes z>y>x which is incorrect. Refer to the below link for the correct diagrams :-

4. Nice article. I’ve one question though. What I couldn’t see is the part where we should connect parent and rotated node right after the rotation.

• Nevermind :). I’ve just seen that part.

5. 