DEV Community

Cover image for Rotation in AVL tree
Aya Bouchiha
Aya Bouchiha

Posted on • Edited 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)