AVL Trees (Adelson-Velsky and Landis Trees)

A Self-Balancing Binary Search Tree

What is an AVL Tree?

An AVL Tree is a self-balancing binary search tree that ensures balance by performing rotations.

Main Properties of an AVL Tree

Left subtree nodes are smaller than or equal to the root.
Right subtree nodes are greater than the root.
The height difference between left and right subtrees is at most 1.

Common Operations

Insertion

Insert node using BST rules → If smaller, go left; if larger, go right
Update height of each ancestor → Height = 1 + max(left height, right height)
Calculate balance factor → BF = height(subtree left) - height(subtree right)
Check imbalance → If BF ∉ [-1, 0, 1], tree is unbalanced
Determine rotation type if unbalanced
Apply any necessary rotations → Restore balance while moving up the tree
Repeat until root is balanced → Ensure entire tree is balanced before stopping

Diagram of AVL Tree vs. Regular BST

AVL and Binary Tree Comparison

Further Reading

Learn more about AVL Trees: