AVL Trees

AVL trees

AVL is named after its inventors G. M. Adelson-Velsky and E. M. Landis. An AVL tree is a height-balanced binary search tree: at every node, the heights of the two subtrees differ by at most 1.

A node's balance factor is its left-subtree height minus its right-subtree height. A tree is AVL-balanced only when every balance factor is −1, 0 or 1.

Restoring balance

Insertion or deletion can break the balance condition.

Left and right rotations restore balance.

Left rotation

Rotate nodes X and Y counterclockwise: X's right child replaces X, and X becomes its left child.

Right rotation

Rotate nodes X and Y clockwise: X's left child replaces X, and X becomes its right child.

There are four imbalance cases.

Left-left (LL): right rotation

Right-right (RR): left rotation

Left-right (LR): rotate left, then right

Right-left (RL): rotate right, then left

Inserting and deleting nodes

For example, insert 3, 2, 1, 4, 5, 6, 7, 16, 15 and 14 in order.