Rotation in AVL tree
Tags: algorithms, codenewbie, computerscience, beginners
Published: 2021-07-01 23:13:04

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](https://dev.to/ayabouchiha/introduction-to-avl-tree-fbk).

\#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)
```
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

+ [https://www.educative.io/edpresso/common-avl-rotation-techniques](https://www.educative.io/edpresso/common-avl-rotation-techniques)

+ [https://www.freecodecamp.org/news/avl-tree-insertion-rotation-and-balance-factor/](https://www.freecodecamp.org/news/avl-tree-insertion-rotation-and-balance-factor/)

+ [https://www.tutorialspoint.com/data_structures_algorithms/avl_tree_algorithm.htm](https://www.tutorialspoint.com/data_structures_algorithms/avl_tree_algorithm.htm)

+ [https://en.wikipedia.org/wiki/Tree_rotation](https://en.wikipedia.org/wiki/Tree_rotation)

+ [https://www.youtube.com/watch?v=_8qqlVH5NC0](https://www.youtube.com/watch?v=_8qqlVH5NC0)

+ [https://www.youtube.com/watch?v=YWqla0UX-38](https://www.youtube.com/watch?v=YWqla0UX-38)