Search trees keep keys in order so that lookup, insertion, deletion and range queries all run in time proportional to the tree height. The trees in this section differ in how they keep that height small, and in what they are optimised for: memory, disk, access patterns or multi-dimensional data.
Search trees and their balanced variants: BST, AVL, red-black, splay, B-tree, Cartesian and KD trees.
An AVL tree (Adelson-Velsky & Landis, 1962 — the original self-balancing BST) keeps every node's subtree heights within 1 of each other. It is more rig
A B-tree is a self-balancing search tree where each node holds many keys and has many children — designed to minimize disk reads. It's the structure behind
A binary search tree (BST) is a binary tree where every node's left subtree contains smaller keys and right subtree contains larger keys. Average O(log n)…
A Cartesian tree is a binary tree built from a sequence: every node is greater (or smaller, for a min-heap variant) than its descendants in heap order, while…
A KD-tree (k-dimensional tree) is a binary tree that partitions k-dimensional space by alternating splitting axes. It enables fast nearest-neighbor and range…
A red-black tree is a self-balancing BST where each node is colored red or black and a small set of color invariants keep the tree height ≤ 2 log(n+1). Used…
A splay tree is a self-adjusting BST: every access (search, insert, delete) moves the touched node to the root through a sequence of rotations called…
A plain BST is the foundation: every key in the left subtree is smaller and every key in the right is larger. Inserting sorted data turns it into a linked list, so balanced variants add rotations. AVL trees keep subtree heights within one; red-black trees allow more slack and rotate less on updates; splay trees move each accessed key to the root, which is good for skewed access; Cartesian trees (treaps when priorities are random) combine BST order with heap order. B-trees generalise to many keys per node to match disk pages, and KD trees split on alternating dimensions for spatial queries.
| Tree | Search (worst) | Balance | Best for |
|---|---|---|---|
| BST | O(n) | None | Teaching, random insert order |
| AVL | O(log n) | Strict | Read-heavy in-memory lookups |
| Red-black | O(log n) | Relaxed | General maps (std::map, Java TreeMap) |
| Splay | O(log n) amortized | Self-adjusting | Caches, skewed access |
| Cartesian / treap | O(log n) expected | Randomized | Simple balanced trees, split/merge |
| B-tree | O(log n) | Strict, wide nodes | Databases and file systems |
| KD tree | O(n) worst, about O(log n) typical | By median splits | Nearest neighbour in low dimensions |