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
- balance factor — For a tree node, the height of its left subtree minus the height of its right subtree.
- rotation — A small local rearrangement of a search tree that lifts a child above its parent while keeping the keys in order.
- balanced tree — A tree kept close to its minimum possible height, O(log n), so that searches never take long paths.
- binary search tree — A binary tree in which every key in a node's left subtree is smaller than the node's key and every key in its right subtree is larger.
Taught in
- Binary Search Trees: Search, Insert And Delete — Algorithms & Data Structures for Working Engineers
- AVL Trees: Rotations That Keep The Guarantee — Algorithms & Data Structures for Working Engineers