A binary search tree (BST) is a data structure that stores keys in a binary tree subject to an ordering rule: every key in a node’s left subtree precedes the node’s key, and every key in its right subtree follows it. This recursive organization allows a search to discard one subtree at each comparison. Nodes may store keys alone, as in a set, or associate keys with values, as in an ordered dictionary.
Binary search trees combine efficient lookup with access to the order of their contents. They can find minimum and maximum keys, identify neighboring keys, enumerate a range, and produce all entries in sorted order without rearranging them. Their central limitation is that ordering alone does not guarantee efficiency: a tree containing keys may have height proportional to , or it may degenerate into a chain of length proportional to . Balanced, randomized, and self-adjusting variants address this limitation in different ways.
The binary search tree is both a practical family of data structures and a central subject in the analysis of algorithms. Its study connects tree geometry, computational complexity, probability, memory organization, and the design of dynamic ordered collections.
Ordering rules and structural representation
A binary search tree consists of a root and zero, one, or two child subtrees at each node. A node usually contains a key, an associated value, and references to its left and right children. Some implementations also store a parent reference or information needed for balancing. An empty tree has no root. A leaf has no children, while an internal node has at least one. As with other forms of tree, the structure is hierarchical, but the search-tree ordering rule gives that hierarchy a specific relationship to the stored data.
For distinct keys, the defining invariant can be written as
where and denote all nodes in the left and right subtrees of node . The requirement applies to entire subtrees, not merely to immediate children. A root with key , a left child with key , and a right child of that left child with key violates the invariant, even though each direct parent–child comparison appears locally plausible.
Keys need not be integers. Strings, dates, tuples, and application-defined objects can all serve as keys if their comparison relation has the required consistency. Many libraries use a strict weak ordering: two keys are treated as equivalent when neither precedes the other. This equivalence need not coincide with object identity or a separate equality operation. Ordinary floating-point comparisons involving NaN do not satisfy the usual ordering assumptions without an additional comparison policy. Likewise, changing a stored key in place can invalidate the structure even when no pointer changes.
Duplicate keys require an explicit representation policy. A tree can reject duplicates, replace the value associated with an equivalent key, store a count, or attach a collection of records to one node. Another method orders records by a composite key, such as a user key followed by a unique identifier. Simply placing equal keys consistently on one side is possible in an unbalanced tree, but rotations can invalidate that particular convention. Balanced multiset implementations therefore need an invariant compatible with their restructuring operations.
A tree’s height is commonly measured as the greatest number of edges from its root to a leaf; a one-node tree then has height zero. Some descriptions count nodes instead, shifting heights by one. Neither convention changes asymptotic results, but implementations and proofs must use one convention consistently.
Searching, navigation, and ordered traversal
A lookup begins at the root and compares the requested key with the current node’s key. Equality ends a successful search. A smaller key directs the search to the left child, and a larger key directs it to the right child. Reaching an empty child position establishes that the key is absent. The method resembles binary search on a sorted sequence, but a tree’s partitions are determined by its shape rather than by repeatedly selecting the middle array position. An unbalanced tree therefore does not necessarily halve the remaining candidates.
The search maintains a shrinking interval of possible keys. After moving left from a node with key , every remaining candidate must be smaller than ; after moving right from a node with key , every remaining candidate must be greater than . These bounds provide a useful loop invariant for proving correctness. An iterative implementation needs only a current-node reference and constant auxiliary space. A recursive implementation expresses the same reasoning directly but consumes stack space proportional to the search path.
Minimum and maximum queries follow a single direction: repeatedly taking left children reaches the minimum, and repeatedly taking right children reaches the maximum. The successor of a node is the least key strictly greater than its own. If the node has a right subtree, its successor is that subtree’s minimum. Otherwise, the successor is the first ancestor reached by climbing from a left child. Predecessor navigation is symmetric. Without parent references, an implementation can retain the search path or track candidate ancestors during a new search from the root.
An inorder traversal visits the left subtree, the node, and then the right subtree. The ordering invariant ensures that this produces keys in sorted order. It is a specialized depth-first traversal and visits all nodes in time. Recursive traversal uses auxiliary stack space for height ; an explicit stack gives the same bound without depending on the language’s call stack. With parent references, a complete walk can instead maintain constant traversal state.
Ordered navigation also supports lower-bound and upper-bound queries. A lower bound is the first key not less than a target; an upper bound is the first key strictly greater. During a search, the algorithm remembers the best candidate whenever it moves left. To report keys in an interval, it finds the first qualifying key and continues in order until passing the upper endpoint. With suitable traversal state, reporting results takes time rather than performing independent root searches.
Insertion, deletion, and construction
Insertion first follows the same path as an unsuccessful search. At the empty child position where that search terminates, the algorithm installs a new leaf. For example, inserting in that order creates a root at , with smaller keys in its left subtree and larger keys in its right subtree. The insertion order determines the shape: inserting the same keys in increasing order into an ordinary, unbalanced tree produces a rightward chain. Searching and linking require time before any balancing work.
Deletion has three principal cases. A leaf can simply be detached. A node with one child can be replaced by that child, with the parent’s reference redirected accordingly. Removing the root requires updating the tree’s root reference rather than a parent link. These cases preserve order because the replacement subtree already occupies the same allowable key interval. Parent references, subtree counts, and other auxiliary fields must be updated as part of the operation.
For a node with two children, a standard method replaces its entry with its inorder successor, the minimum node in its right subtree, and then removes that successor from its original location. The successor cannot have a left child, so its removal reduces to a simpler case. Using the predecessor works symmetrically. This procedure is commonly called Hibbard deletion, after Thomas N. Hibbard’s 1962 treatment of insertion and deletion in trees.
Replacing an entry and relocating a node are not interchangeable at the implementation level. Copying a successor’s key and value may be inconvenient when records are large, noncopyable, or externally identified by node address. An alternative physically transplants the successor node into the deleted node’s position. Either approach must maintain all relevant links and metadata. In a balanced tree, the removal may also trigger repairs along an ancestor path; completing the ordinary search-tree deletion does not by itself restore the balancing invariant.
Construction need not use repeated insertion. From a sorted array of distinct keys, choosing the middle element as root and recursively constructing the two halves creates a height-balanced tree in time. By contrast, inserting that same sorted array sequentially into an unbalanced tree takes time. A sorted linked list can also be converted in linear time when its length is known: an inorder construction consumes successive list entries while building subtrees of predetermined sizes. These bulk-construction methods exploit knowledge unavailable to a general online insertion operation.
Height, average behavior, and complexity bounds
The cost of basic search-tree operations depends primarily on height. A binary tree of height , using the edge-counting convention, contains at most nodes. Consequently, every binary tree with nodes satisfies
A suitably balanced tree approaches this logarithmic minimum. At the other extreme, a chain has height . Search, insertion, and ordinary deletion therefore take time, giving logarithmic performance in a balanced tree but linear worst-case performance in an unrestricted one.
Average-case claims require an explicit probability model. If distinct keys are inserted in a uniformly random permutation, the resulting random search tree has logarithmic expected search cost and logarithmic expected height. These are separate statements: the average depth concerns a typical stored key, whereas height concerns the deepest path. The assumption is about the relative order of insertion, not merely about whether numeric key values appear irregular. A monotonically ordered stream can generate a chain even when gaps between its values vary unpredictably.
For the random-permutation model, let be the sum of the depths of all nodes. Its expectation is
where is the th harmonic number. Since , a uniformly selected stored key requires approximately node comparisons in expectation, apart from lower-order terms. This is about , illustrating that a random search tree is efficient without being as shallow as a nearly complete tree. These results use probabilistic assumptions; they do not guarantee a particular operation’s cost.
There is also a comparison-based lower bound. Searching among ordered keys and their possible gaps requires distinguishing a number of outcomes proportional to . A binary comparison process therefore needs logarithmic worst-case depth. Balanced binary search trees meet the resulting bound asymptotically in the comparison model. This does not exclude faster structures under stronger assumptions, such as bounded-width integer keys and specialized machine operations.
The familiar time-complexity bounds usually count each key comparison as constant time. Comparing long strings or composite records can cost more, particularly when many keys share long prefixes. Stored nodes occupy space, but their practical memory footprint includes child pointers, optional parent pointers, balancing fields, payloads, and allocator overhead. Auxiliary space complexity depends on the operation: iterative lookup needs extra space, whereas recursive operations can require .
Rotations and deterministic balancing
A tree rotation changes a small portion of a tree without changing its inorder sequence. In a right rotation, a node with left child moves below ; the former right subtree of becomes the left subtree of . If the three surrounding subtrees are , , and , their key order remains
A left rotation reverses this transformation. A rotation updates only a constant number of structural references, although it may also require recalculating local metadata.
An AVL tree, introduced by Georgy Adelson-Velsky and Evgenii Landis in 1962, requires the heights of each node’s two child subtrees to differ by at most one. Its balance factor records that difference. After an update, changes propagate toward the root until the relevant heights stabilize or rotations restore balance. Depending on the direction of imbalance, a repair uses either one rotation or a two-rotation sequence. An insertion needs at most one such local repair, although determining where it is needed can require a logarithmic ancestor walk.
AVL height is logarithmic because the minimum number of nodes at a given height follows a Fibonacci-like recurrence. With empty height and leaf height ,
Its growth implies a height bound of approximately . Deletion can reduce a subtree’s height and cause further imbalance higher up, so repairs may be necessary at multiple ancestor levels. This differs from the insertion case and is an important source of implementation errors.
A red–black tree uses node colors and a different collection of invariants. In a common formulation, the root and empty leaves are black, red nodes cannot have red children, and every path from a node to an empty descendant contains the same number of black nodes. These conditions prevent any root-to-leaf path from becoming more than twice as long as another in the relevant black-height accounting, yielding height at most . Updates restore the rules through recoloring and rotations.
Both AVL and red–black trees provide worst-case lookup, insertion, and deletion, but enforce different shapes and maintenance rules. AVL trees impose a tighter height restriction; red–black trees permit greater local variation. Actual speed depends on key-comparison costs, update frequency, node representation, and cache behavior rather than on height bounds alone. Other deterministic approaches include weight-balanced trees and scapegoat trees. The latter rebuild entire subtrees when balance conditions fail, showing that logarithmic-height maintenance need not rely exclusively on local rotations.
Randomized and self-adjusting variants
A treap assigns each node a key and a priority. The keys satisfy the binary search tree invariant, while the priorities satisfy a heap-order invariant. With distinct keys and priorities, these two requirements determine a unique shape. Insertion first places the new key as an ordinary leaf and then rotates it upward until priority order is restored. Deletion can rotate the target downward until it can be removed, or merge its two child trees using their priorities.
When priorities have a uniformly random relative order independent of the keys, a treap has the same shape distribution as a search tree built from a random insertion permutation. Expected search and update costs are therefore , even when the keys arrive in sorted order. This is an example of a randomized algorithm: the implementation supplies the randomness instead of assuming that the input provides it. A particular realization can still have linear height, so the expected guarantee is not a deterministic worst-case bound.
A splay tree takes a different approach. After an access, it moves the accessed node toward the root through a sequence of rotations called splaying. The basic cases are a single final rotation, two rotations in the same direction, and two rotations in opposite directions, conventionally called zig, zig-zig, and zig-zag. For an unsuccessful lookup, implementations commonly splay the last node visited. No explicit balance factor, color, or random priority is required.
An individual splay operation can take time. Nevertheless, splay trees provide amortized time per standard operation over a sequence, with suitable allowance for the starting tree. Amortized analysis is not an average over random inputs: it bounds the total cost of a sequence by accounting for how expensive operations change the structure and enable cheaper later operations. Splay trees also have stronger locality-sensitive properties, including efficient repeated access to a small working set of keys.
These alternatives embody different notions of efficiency. Deterministic balanced trees limit each operation’s worst-case structural work. Treaps obtain expected guarantees through random choices. Splay trees can exploit access patterns while tolerating occasional expensive operations. Consequently, an average throughput requirement, a strict latency requirement, and a workload dominated by repeated nearby accesses may favor different designs.
Restructuring also affects read behavior. Lookup in an ordinary AVL or red–black tree need not change the tree, whereas splay lookup normally does. That distinction matters for read-only sharing, synchronization, and persistence. A method that reduces subsequent search depths can simultaneously increase writes or contention.
Augmentation, rank queries, and tree composition
A search tree can maintain information beyond its keys and balancing fields. The most common example stores the number of nodes in each subtree:
with an empty subtree having size zero. These counts enable an order-statistic tree to answer rank and selection queries without traversing every preceding element. If duplicates are represented by counts, the recurrence can instead count stored occurrences rather than distinct nodes.
To select the key with zero-based rank , let be the size of the current node’s left subtree. If , continue left. If , return the current entry. Otherwise, continue right with rank . To compute the number of keys smaller than a target, descend as in search, adding the left-subtree size plus one whenever moving right. Both operations take time and therefore in a balanced tree. Counts must be repaired after insertions, deletions, and rotations, including changes above the structurally modified node.
An interval tree can organize intervals by their lower endpoints while storing the greatest upper endpoint in each subtree. To find an interval overlapping a query, the search uses this maximum to rule out subtrees whose intervals end too early. Under a closed-interval convention, if the left subtree’s maximum upper endpoint is less than the query’s lower endpoint, that subtree cannot contain an overlap. A balanced augmented tree supports finding one overlap in logarithmic time. Reporting every overlap requires a traversal and analysis appropriate to the particular interval-tree variant.
Other useful summaries include subtree sums, minima, maxima, and combined application-specific aggregates. The key design requirement is that each node’s summary can be recomputed efficiently from its own entry and its children’s summaries. Constant-time local recomputation allows rotations to preserve the augmentation without changing asymptotic update complexity. Some summaries also permit range aggregation: entire qualifying subtrees can contribute their stored result without visiting each record individually.
Search trees can also be organized around split and join. Splitting at a key separates entries into ordered parts; joining combines trees whose key ranges are properly separated, sometimes with an intermediate key. The balancing algorithm determines how these operations are implemented. They support bulk set union, intersection, and difference more naturally than repeated single-key updates in some settings.
Augmentation does not make arbitrary queries efficient. A tree ordered by surname cannot generally find all records with a given age in logarithmic time unless additional indexing or suitable summaries exist. The usefulness of an augmented tree depends on whether its ordering and metadata allow large regions of the data to be excluded or summarized safely.
Memory layout, persistence, and concurrent access
The traditional representation allocates each node separately and links nodes with pointers. This supports local insertion and deletion but can scatter nearby keys throughout memory. A lookup may incur a dependent pointer load at every level, reducing opportunities for hardware prefetching. The resulting cache behavior can make a balanced tree slower than its comparison count suggests. Pools, arenas, compact indices, and embedded links can reduce allocation overhead or improve locality, although none automatically makes search paths contiguous.
An intrusive tree stores its linkage fields inside application objects rather than in separate wrapper nodes. This can avoid an extra allocation and support direct membership of existing records, but object lifetime becomes part of the tree’s correctness conditions. A record cannot be destroyed while still linked into the structure. Conversely, nonintrusive containers manage their own nodes and may provide stronger ownership boundaries. The trade-off concerns memory management and interface design, not the search invariant itself.
A persistent data structure preserves access to earlier versions after an update. A common search-tree technique is path copying: copy the nodes on the modified root-to-leaf path, reuse unchanged subtrees, and publish a new root. In a balanced tree, a standard update creates new nodes, including those needed for local restructuring. Structural sharing avoids copying the entire collection. This approach is especially natural in functional programming, where nodes can remain immutable after construction.
Parent references complicate structural sharing because a subtree shared by multiple versions may have different logical parents. Persistent implementations therefore commonly use downward-only links and maintain traversal context separately. Memory reclamation also differs from that of a single mutable tree: an old node remains live while any retained version can reach it. Garbage collection or explicit ownership mechanisms can handle this, but retaining many versions may preserve substantial portions of historical data.
Concurrent access introduces coordination requirements beyond ordinary tree correctness. A coarse lock can serialize updates and protect readers, while finer-grained methods lock smaller regions or use atomic operations. Rotations and deletion affect multiple links, so preserving each pointer individually is not enough: readers must observe a valid state under the algorithm’s synchronization rules. In concurrent computing, a linearizable implementation must make each completed operation appear to take effect at a single point between invocation and return.
Memory reclamation is a separate problem from logical deletion. A removed node may still be referenced by another thread that began traversing earlier. Techniques such as hazard pointers, epoch-based reclamation, or garbage collection prevent premature reuse. Whether a design is lock-free, wait-free, or lock-based depends on its complete progress argument, not simply on its use of atomic pointer updates.
Applications and alternatives
Binary search trees are natural implementations of ordered sets and maps. Besides membership and key–value lookup, they support predecessor queries, sorted iteration, and interval selection. For example, a calendar index ordered by timestamp can locate the first event at or after a specified time and then enumerate subsequent events. A balanced tree keeps these operations efficient while allowing arbitrary insertions and deletions. An unordered dictionary provides a different interface and cannot supply these ordering operations directly.
A hash table commonly offers expected constant-time membership, insertion, and deletion under suitable hashing and resizing assumptions. It is often preferable when exact-key lookup dominates. A search tree instead provides deterministic logarithmic bounds when balanced and exposes ordered relationships among keys. The comparison is not simply “constant versus logarithmic”: hashing a long key can be expensive, tree comparison may terminate after a short differing prefix, and collision handling, memory layout, and workload all affect actual cost.
A sorted array supports logarithmic lookup through binary search and offers compact storage and efficient sequential traversal. Its main limitation as a dynamic ordered collection is that inserting or deleting an interior element generally requires shifting elements. Arrays are therefore attractive for static or mostly static data, while trees accommodate frequent updates without moving an entire suffix. Hybrid designs can combine sorted blocks with an index, changing both update costs and locality.
For storage-backed database indexes, a B-tree or B+ tree is often more suitable than a node-per-key binary tree. Each node contains many keys and child references, increasing fan-out and reducing the number of block transfers required for a search. B+ trees also support efficient ordered scans through their leaf organization. A binary search tree’s comparison bound alone does not make it a good disk index; the relevant cost model includes pages, buffering, and persistent writes.
Other data structures specialize in different capabilities. A binary heap efficiently exposes a minimum or maximum but does not enforce search-tree order and generally cannot find an arbitrary key in logarithmic time. A skip list provides an alternative ordered representation based on linked levels, commonly with expected logarithmic operations. Tries navigate symbols or bits of keys rather than comparing complete keys, making their costs depend more directly on key length and representation.
Balanced search trees also appear as components of larger algorithms. A plane-sweep algorithm in computational geometry may maintain an ordered set of active objects; an operating-system component may maintain an ordered collection of ranges or scheduling entities. These applications can impose additional constraints. In particular, a comparator depending on changing external state can silently invalidate a tree unless the algorithm explicitly handles every change that affects stored order.
Historical development and correctness methods
Binary search trees emerged from early work on information retrieval, symbol tables, and dynamic storage organization. The historical record includes multiple related ideas rather than a single universally accepted invention event. Their essential appeal was to retain the selective branching of binary search while avoiding the need to shift a sorted array after every insertion. Subsequent research increasingly separated two issues: preserving key order and controlling the shape produced by a changing sequence of operations.
Several landmark developments established the main balancing approaches. Adelson-Velsky and Landis introduced AVL trees in 1962. Rudolf Bayer developed symmetric binary B-trees in 1972, and Leonidas Guibas and Robert Sedgewick presented the red–black formulation in 1978. Daniel Sleator and Robert Tarjan introduced splay trees in 1985. Cecilia Aragon and Raimund Seidel developed randomized search trees in 1989, establishing the approach commonly associated with treaps. These structures differ in their invariants and guarantees, not merely in implementation details.
Correctness proofs begin with the ordering invariant but must also establish that the representation is a tree. Child links must not form cycles, and a mutable, nonshared tree should not contain the same node in two different positions. Lookup correctness follows from the fact that each comparison discards only keys that cannot equal the target. Insertion preserves the interval restrictions accumulated along its search path. Deletion requires showing that the replacement entry or subtree fits the removed node’s allowed interval.
A validator that compares only each node with its immediate children is insufficient. A stronger method carries lower and upper bounds through the traversal and checks every key against its inherited interval. An inorder traversal can also check monotonicity under the chosen duplicate-key policy, but structural checks are still needed to detect cycles or unintended sharing. Balanced variants require additional checks: stored heights for AVL trees, color and black-height conditions for red–black trees, and priority order for treaps.
Testing usually combines invariant checks with comparison against a simpler reference representation. After each operation in a generated sequence, an implementation can verify that inorder output matches a sorted collection containing the expected entries. Targeted sequences exercise difficult cases: deleting the root, removing a node whose successor has a right child, repeated insertion and deletion of extreme keys, and workloads that trigger multiple balancing repairs. Duplicate keys and comparator-equivalent but nonidentical objects need separate coverage.
Formal verification can express tree shape, key order, balancing, and metadata as explicit predicates. A rotation proof must establish not only preservation of the inorder sequence but also the correctness of every updated field. For concurrent trees, the proof additionally addresses interference, memory safety, and the operation’s observable effect. Performance claims remain separate obligations: proving that a tree always contains the right keys does not prove logarithmic height, bounded memory use, or an amortized cost bound.