AVL trees are a special type of binary search trees that automatically rebalance themselves every time we add or remove nodes.

• Average: 0(log n)
• Worst: O(n)

Balanced tree

Perfect tree

Skewed trees

How do our trees become unbalanced?

This happens when we insert sorted values in them, either in ascending or descending order. Even if our numbers are not sorted, binary search trees can still become unbalanced.

There are different algorithms for balancing trees.

AVL trees are the first self balancing trees, introduced in the 1960s. They're named after their investors. Adelson, Valsky, and Landis.

They're actually a special type of binary search trees, but they have a self-balancing property, so every time we insert or remove a value, the tree rebalances itself.

SELF-BALANCING TREES