Balanced BSTs: AVL Trees
Explore the concept of AVL trees, a type of self-balancing binary search tree that keeps its height balanced through rotations after insertions and deletions. Learn the balance factor, rotation types, and how AVL trees maintain efficient O(log n) operations. Understand insertion and deletion processes with balancing techniques to optimize search-heavy applications.
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 ...