Rotation in AVL tree

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.

Type of Rotation

before starting, I want to remention that the BalanceFactor BalanceFactor = height(left sub-tre…


This content originally appeared on DEV Community and was authored by Aya Bouchiha

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.

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)

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)

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)

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)

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)

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

     15 (bf:-2)
      \
       16 (bf:-1)
        \
         19 (bf:0)

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)

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)

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

     15 (bf:2)
    /
   13  (bf:1)
  /
11 (bf:0)

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)

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

References and useful Resources


This content originally appeared on DEV Community and was authored by Aya Bouchiha


Print Share Comment Cite Upload Translate Updates
APA

Aya Bouchiha | Sciencx (2021-07-01T23:13:04+00:00) Rotation in AVL tree. Retrieved from https://www.scien.cx/2021/07/01/rotation-in-avl-tree/

MLA
" » Rotation in AVL tree." Aya Bouchiha | Sciencx - Thursday July 1, 2021, https://www.scien.cx/2021/07/01/rotation-in-avl-tree/
HARVARD
Aya Bouchiha | Sciencx Thursday July 1, 2021 » Rotation in AVL tree., viewed ,<https://www.scien.cx/2021/07/01/rotation-in-avl-tree/>
VANCOUVER
Aya Bouchiha | Sciencx - » Rotation in AVL tree. [Internet]. [Accessed ]. Available from: https://www.scien.cx/2021/07/01/rotation-in-avl-tree/
CHICAGO
" » Rotation in AVL tree." Aya Bouchiha | Sciencx - Accessed . https://www.scien.cx/2021/07/01/rotation-in-avl-tree/
IEEE
" » Rotation in AVL tree." Aya Bouchiha | Sciencx [Online]. Available: https://www.scien.cx/2021/07/01/rotation-in-avl-tree/. [Accessed: ]
rf:citation
» Rotation in AVL tree | Aya Bouchiha | Sciencx | https://www.scien.cx/2021/07/01/rotation-in-avl-tree/ |

Please log in to upload a file.



There are no updates yet.
Click the Upload button above to add an update.

You must be logged in to translate posts. Please log in or register.

Related Posts