TreesTrees

AVL Tree

A self-balancing BST that keeps every node's subtree heights within 1 of each other using rotations, guaranteeing O(log n) operations.

Learn AVL Tree →

Commands — insert N commands separated by commas

Empty tree

1/63Empty AVL tree. Each node shows its balance factor bf = height(left) − height(right); the invariant is |bf| ≤ 1 everywhere.

Comparing / rebalancingInsertion pathNewly insertedMoved by a rotation

PseudocodeLearn AVL Tree →

1insert(node, key): BST insert recursively
2update height(node); bf = height(left) - height(right)
3if bf > 1 and key < node.left.key:  LL → rotateRight(node)
4if bf < -1 and key > node.right.key: RR → rotateLeft(node)
5if bf > 1 and key > node.left.key:  LR → rotateLeft(node.left), then rotateRight(node)
6if bf < -1 and key < node.right.key: RL → rotateRight(node.right), then rotateLeft(node)
7return node (possibly the new subtree root)

Variables

height0

Complexity

access O(log n)

search O(log n)

insert O(log n)

delete O(log n)

Speed