AVL Tree

Self-Balancing BSTO(log n)

A self-balancing BST where every node's balance factor (BF = left height − right height) stays within {-1, 0, 1}.

Insert values or use Auto-Demo to see rotations.

Insert values to build the AVL tree.

highlighted node

BF ∈ {-1,0,1} (ok)

|BF| > 1 (imbalanced)

BF= balance factor badge on each node

Rotation types

LL rotation

BF > 1, left-heavy left child

rotateRight(node)

RR rotation

BF < -1, right-heavy right child

rotateLeft(node)

LR rotation

BF > 1, right-heavy left child

rotateLeft(left) → rotateRight(node)

RL rotation

BF < -1, left-heavy right child

rotateRight(right) → rotateLeft(node)