Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

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

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-LeftLeft-Right Case : — x is the right child of y and y is the left child of z.

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

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

Right-RightInser­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 :-
    https://upload.wikimedia.org/wikipedia/commons/c/c4/Tree_Rebalancing.gif