DEV Community

Cover image for Rotation in AVL tree
Aya Bouchiha
Aya Bouchiha

Posted on • Updated on

Rotation in AVL tree

#algorithms #codenewbie #computerscience #beginners

Hi, on this amazing day we're going to discuss rotation in the AVL tree! if you're not familiar with AVL trees check this post.

#day_19

Type of Rotation

before starting, I want to remention that the BalanceFactor BalanceFactor = height(left sub-tree) - height(right sub-tree) should be -1, 0 or 1.

Right rotation

We use this rotation when the tree is a left unbalanced tree like this example below:

     15 (bf:2) 
    /
  11 (bf:1)      left unbalanced tree
 /
9 (bf:0)
Enter fullscreen mode Exit fullscreen mode

in this case, the tree needs a right rotation (RR), so the unbalanced node(15) becomes a right child of its left child (11)

           11  (bf:0)
         /    \
(bf:0)  9     15 (bf:-0)
Enter fullscreen mode Exit fullscreen mode

Left rotation

We use this rotation when the tree is a right unbalanced tree like this example below:

 15 (bf:-2) 
  \
   17 (bf:-1)   right unbalanced tree
     \
      19 (bf:0)
Enter fullscreen mode Exit fullscreen mode

in this case, the tree needs a left rotation (LL), so the unbalanced node(15) becomes a left child of its right child (17)

           17  (bf:0)
         /    \
(bf:0)  15     19 (bf:0)
Enter fullscreen mode Exit fullscreen mode

Right-Left rotation

The Right Left Rotation is a combination of right rotation followed by a left rotation. Let's see this example:

15 (bf:-2)
  \ 
   19 (bf:1)
  / 
16 (bf:0)
Enter fullscreen mode Exit fullscreen mode

firstly, we'll perform a right rotation so this tree we'll be like this:

     15 (bf:-2)
      \
       16 (bf:-1)
        \
         19 (bf:0)
Enter fullscreen mode Exit fullscreen mode

then we'll perform a left rotation because the tree becomes a right unbalanced tree. That's why (15) will become the left child of its right child (16)

         16 (bf:0)
        /  \
(bf:0)15    19 (bf:0)
Enter fullscreen mode Exit fullscreen mode

Left-Right rotation

The Left-Right Rotation is a combination of left rotation followed by a right rotation. Let's see this example:

    15  (bf:2)
   /  
 11 (bf:-1)
   \
    13 (bf:0)
Enter fullscreen mode Exit fullscreen mode

firstly, we'll perform a left rotation of the tree we'll be like this:

     15 (bf:2)
    /
   13  (bf:1)
  /
11 (bf:0)
Enter fullscreen mode Exit fullscreen mode

then we'll perform a right rotation because the tree becomes a left unbalanced tree. That's why (15) will become the right child of its left child (13)

          13 (bf:0)
         /  \
(bf:0) 11    15 (bf:0)
Enter fullscreen mode Exit fullscreen mode

Tomorrow, I'll cover the implementation of insertion using python!
Thank you for your time and happy coding!

References and useful Resources

Top comments (0)

Read next

yassinesallami profile image

How to create an image authentication system with python streamlit and canva!

Yassine Sallami -

mdarifulhaque profile image

2641. Cousins in Binary Tree II

MD ARIFUL HAQUE -

safdarali profile image

5 Steps You Must Follow to Deploy a React App on Hostinger

Safdar Ali -

safdarali profile image

9 Steps for JWT Authentication in Node.js Application

Safdar Ali -