Binary Search Tree
An ordered tree where everything left of a node is smaller and everything right is larger. That single invariant makes search, insert, and delete all O(log n) on a balanced tree.
A binary search tree stores each value in a node with at most two children, maintaining one rule everywhere: left subtree < node < right subtree. Searching walks a single root-to-leaf path, discarding half the remaining tree at every step — the tree-shaped twin of binary search.
Insertion follows the same comparison path until it falls off the tree, attaching the new node where it landed. Deletion has three cases: a leaf simply disappears, a single-child node is bypassed, and a two-child node is replaced by its in-order successor (the smallest value in its right subtree).
The catch is balance. Insert 1, 2, 3, 4, 5 in order and the "tree" degenerates into a linked list with O(n) operations. Self-balancing variants — AVL trees rotate on ±1 height imbalance, red-black trees enforce colour rules — keep the height logarithmic no matter the insertion order. An in-order traversal always yields the values in sorted order.
Operations
| Operation | Complexity |
|---|---|
| search | O(log n) avg / O(n) worst |
| insert | O(log n) avg |
| delete | O(log n) avg |
| in-order walk | O(n), sorted output |
Where it's used
Sorted data with frequent inserts and deletes: database indexes, ordered maps/sets (TreeMap, std::map), range queries.