## DEV Community 👩‍💻👨‍💻 is a community of 921,001 amazing developers

We're a place where coders share, stay up-to-date and grow their careers. Aya Bouchiha

Posted on • Updated on

# Introduction to AVL tree

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 Adelson, Velskii and Landis. 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:

1. Right rotation
2. Left rotation
3. Right-Left rotation
4. Left-Right rotation

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

## 🌚 Friends don't let friends browse without dark mode.

Sorry, it's true.