AVL tree

A self-balancing binary search tree in which the heights of every node's two subtrees differ by at most one.

In more detail

Named after its inventors Adelson-Velsky and Landis, it checks balance factors after each insert and fixes any violation with one or two rotations. Its height stays below about 1.44 times log2 n, so search, insert and delete are O(log n) even for sorted or adversarial input. The cost is extra bookkeeping on every update.

Related terms

Taught in

References