Balanced BSTs: AVL Trees
Explore how AVL trees, a type of self-balancing binary search tree, maintain efficient operations by keeping tree heights balanced. Understand balance factors, identify imbalance cases, and learn how rotations restore balance after insertions and deletions. Gain practical knowledge of implementing AVL trees and their advantages over standard BSTs in maintaining fast search times.
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
...