Balanced BSTs

Binary search trees that keep their height $O(\log n)$ under insertion and deletion. In competitive programming you rarely write one — std::set and std::map are red-black trees — but knowing the trade-offs matters, and sometimes you need one you can modify.

The family

Tree	Balance rule	Height	Notes
AVL	subtree heights differ by $\le 1$	$\le 1.44\log n$	strictest; fastest lookups, more rotations
Red-black	no two consecutive red nodes; equal black-height	$\le 2\log n$	what std::set and std::map use
Splay	move the accessed node to the root	amortized $O(\log n)$	self-adjusting; basis of link-cut trees
Treap	random priorities form a heap	expected $O(\log n)$	easiest to write, supports split/merge
Scapegoat	rebuild any subtree that becomes too unbalanced	amortized $O(\log n)$	no per-node balance data
B-tree / B+ tree	many keys per node	$O({\log }_{B}n)$	for disk and cache; every database uses one
WBLT / weight-balanced	subtree sizes bounded ratio	$O(\log n)$	supports order statistics naturally

Which to write yourself

If you need a balanced BST you can extend — with subtree aggregates, lazy propagation, split and merge — write a treap. It is 40 lines, the balancing is a coin flip, and split/merge make range operations trivial.

Splay trees are the alternative when you need the access locality property or are building link-cut trees. AVL and red-black trees are worth understanding but almost never worth implementing.

What the STL gives you

set<int> s;                       // ordered, unique
multiset<int> ms;                 // ordered, duplicates
map<int,int> m;                   // ordered key -> value
 
s.insert(x);
s.erase(s.find(x));               // erase ONE occurrence (erase(x) removes ALL in a multiset)
auto it = s.lower_bound(x);       // first >= x
auto it2 = s.upper_bound(x);      // first > x
if (it != s.begin()) --it;        // predecessor

Two classic bugs

1. multiset::erase(value) erases every copy. Use erase(find(value)) to remove one.
2. std::lower_bound(s.begin(), s.end(), x) on a set is $O(n)$ — the iterators are not random access. Always use the member function s.lower_bound(x).

Order statistics — what std::set cannot do

std::set has no “$k$-th smallest” or “rank of $x$”. Three options:

1. PBDS `tree` — a GNU extension giving find_by_order and order_of_key in $O(\log n)$. One #include and two using lines.
2. BIT over compressed values — if the value set is known in advance, this is faster and portable.
3. Treap with subtree sizes — if you need arbitrary extra aggregates too.

Implicit-key BSTs — treating a BST as an array

A treap keyed by position rather than value (an implicit treap) supports operations no array can:

Operation	Cost
Insert / erase at any position	$O(\log n)$
Reverse a subrange	$O(\log n)$ with a lazy flag
Cyclic shift a subrange	$O(\log n)$
Move a subrange elsewhere	$O(\log n)$
Range aggregate and range update	$O(\log n)$
Split into two sequences / concatenate	$O(\log n)$

This is the structure to reach for when a problem does things to an array that a segment tree cannot express — insertion, deletion or reordering.

Rope

A balanced BST over string chunks, giving $O(\log n)$ concatenation, splitting and insertion into a string. GNU C++ ships one as __gnu_cxx::rope. Rarely needed, but it is the right answer for “build a string with many insertions in the middle”.

Complexity summary

All the balanced variants give $O(\log n)$ for search, insert and delete. They differ in the constant, in the extra data per node, and in which additional operations they support cheaply — split/merge (treap, splay), order statistics (any with subtree sizes), and access locality (splay).

See also: Treap · Ordered Set / PBDS · General Data Structures