Balanced BSTs: AVL Trees
Explore how AVL trees keep binary search trees balanced by maintaining a balance factor and using specific rotations after insertions and deletions. Understand the four types of rotations and how they restore balance, ensuring operations run efficiently with guaranteed logarithmic time complexity.
We'll cover the following...
An AVL tree is a special type of self-balancing binary search tree (BST). It automatically maintains balance after every insertion and deletion.
The main idea behind AVL trees is simple:
The height of the left and right subtrees of any node should differ by at most 1.
If this condition is violated, the tree performs rotations to restore balance.
AVL trees were the first self-balancing BSTs, introduced by Adelson-Velsky and Landis (hence the name AVL).
Why AVL trees are needed
In a normal BST, performance depends on the shape of the tree.
If the tree is balanced, operations are fast →
If the tree becomes skewed, operations become slow →
Example of a skewed BST:
This behaves like a linked list, making searching inefficient.
AVL trees solve this problem by automatically maintaining balance, ensuring that operations remain fast.
Balance factor
The key concept in AVL trees is the balance factor.
The balance factor is defined as:
Balance Factor = Height(left subtree) - Height(right subtree)
For an AVL tree, the balance factor of every node must be:
, , or
If it becomes less than
Example
Balance factors:
Node
...