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

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!

## Top comments (0)