Hello, today, we're going to talk about **AVL tree**.

#day_19

## why we need to use AVL trees.

Sometimes, the Binary search tree's operations become O(n) instead of O(log n) due to being a skewed binary search tree, that's why **A**delson, **V**elskii and **L**andis. *so what's an AVL tree ?*

if you're not familiar with binary search tree, this post will help you :)

## Definition of AVL tree

AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes.

## Time and Space complexity

The space complexity of the avl tree is **O(n)**

insert | search | delete |
---|---|---|

O(log n) | O(log n) | O(log n) |

## Balance factor

the difference between the height of left and right subtrees can be calculated using this formula below:

```
BalanceFactor = height(left-sutree) β height(right-sutree)
```

if the balance factor was 1 or 0 or -1, the tree is balanced, if not, we use the rotation to make it balanced. There are four types of rotation:

- Right rotation
- Left rotation
- Right-Left rotation
- Left-Right rotation

in the next post, we'll cover rotation types with the implementation, see you tomorrow, have a great day!

## Discussion (0)