A red–black tree is a self-balancing binary search tree in which every node carries an additional attribute, conventionally called its color: red or black. Rules governing the arrangement of these colors keep the tree approximately balanced as keys are inserted and removed. For a tree containing elements, search, insertion, and deletion each take time in the worst case.
The structure combines ordered access with predictable update costs. Unlike an ordinary binary search tree, it cannot deteriorate into a linear chain after an unfavorable sequence of insertions. Unlike a hash table, it directly supports operations based on key order, including predecessor and successor queries, sorted iteration, and range searches. These properties make it an important data structure for ordered dictionaries, sets, and various augmented indexes.
Red–black trees developed from balanced multiway search trees in the 1970s. Their binary representation, modest balancing metadata, and bounded number of rotations during conventional updates have made them widely used in libraries and systems software. Their behavior is best understood through the relationship between color invariants, local structural transformations, and the multiway trees that those colors encode.
Structural invariants and the height bound
A red–black tree first obeys the ordinary binary-search ordering rule: keys in a node’s left subtree precede its key, and keys in its right subtree follow it. For a dictionary with unique keys, the comparisons are strict. Containers that permit equivalent keys need an additional convention for representing or ordering those entries. The balancing rules do not determine how duplicates are handled.
The usual definition adds five color properties:
- Every node is either red or black.
- The root is black.
- Every absent child, represented conceptually by a NIL leaf, is black.
- A red node has no red child.
- Every path from a node to a descendant NIL leaf contains the same number of black nodes.
NIL leaves are conceptual external nodes rather than stored elements. An implementation can represent them with null pointers, a shared sentinel object, or another convention. Treating them uniformly as black simplifies both proofs and update cases. The root-black property is sometimes omitted from equivalent definitions because a red root can always be recolored black without disturbing the other properties.
The fifth property defines a node’s black height. One standard convention, used here, defines as the number of black nodes on a path below , excluding itself but including its terminal NIL leaf. For a NIL node, the black height is zero. Equal black heights do not require equal ordinary heights: red nodes may occur between black nodes, lengthening some paths without increasing their black-node count.
Two observations establish the logarithmic height bound. First, a subtree rooted at contains at least
internal nodes. This follows by induction: each child has black height at least , so the minimum size grows at least as fast as that of a complete binary tree of the corresponding black height. Second, the prohibition on consecutive red nodes means that at least half the nodes below the root along any root-to-NIL path are black. If is the maximum number of edges on such a path, then
For example, one million stored elements imply a root-to-NIL height of less than 40 edges under this bound. Actual heights depend on the update sequence and balancing variant. The guarantee concerns the worst possible shape, not an assumption about random input.
Red–black trees are therefore balanced in a bounded-height sense, not necessarily in the sense of having equally sized subtrees. A node can have substantially more descendants on one side than on the other while all color invariants remain valid. This distinction explains both their reliable asymptotic performance and their generally weaker height restriction than more tightly balanced search trees.
Ordered operations and rotations
Searching a red–black tree uses exactly the same procedure as searching an unbalanced binary search tree. At each node, the query key is compared with the stored key; the search stops on a match or proceeds into the appropriate child subtree. Colors are irrelevant to the comparison sequence. Their purpose is to ensure that the number of nodes encountered remains logarithmic.
Several ordered operations follow directly from this structure. The minimum lies at the end of the leftmost downward path, and the maximum at the end of the rightmost path. A node’s successor is the minimum of its right subtree, if that subtree exists. Otherwise, it is the first ancestor reached by climbing from a left child. Predecessor search is symmetric. Parent pointers make upward traversal straightforward; without them, an implementation can retain the search path on a stack.
A lower-bound search finds the first key not less than a query key. Whenever the current node is a possible answer, the search records it and continues left to seek an earlier candidate; otherwise, it continues right. Starting from a lower bound and repeatedly visiting successors reports consecutive entries in time. A complete inorder traversal takes , because each edge is traversed only a constant number of times.
Balancing depends on the tree rotation, a constant-size rearrangement that preserves inorder order. In a left rotation at node , its right child moves into ’s former position. Node becomes ’s left child, and the old left subtree of becomes the right subtree of . The inverse operation is a right rotation. For a left rotation, the ordering relationships are
where , , and denote the three subtrees involved. These relationships remain unchanged after the rotation.
A rotation changes only a fixed number of child and parent links, regardless of subtree size. It must also update the tree’s root pointer if the rotated node was the root. Colors are not inherently part of a rotation: balancing algorithms pair rotations with particular recolorings. A structurally correct rotation can still leave an invalid red–black tree if the associated color changes are wrong.
The time complexity of these operations normally assumes constant-time key comparison. Long strings, composite keys, or user-defined comparators can make comparisons substantially more expensive. If one comparison costs , the comparison component of a lookup is . Cache misses and pointer traversal add further costs that are not captured by the abstract comparison count.
Insertion and repair of red–red violations
Conventional bottom-up insertion begins with an ordinary binary-search insertion. A new internal node replaces a NIL position, receives two black NIL children, and is initially colored red. Making it red preserves the black count on every affected path: the new internal node contributes no additional black node, while the terminal NIL still contributes one.
The only possible color violations are then a red root or a red node with a red parent. If the new node is the root, coloring it black completes the operation. If its parent is black, no repair is necessary. Otherwise, the algorithm examines the new node, its parent, its grandparent, and its uncle—the parent’s sibling. In the conventional repair loop, a red parent necessarily has a grandparent because the root was black before insertion.
If the uncle is red, the parent and uncle are recolored black, and the grandparent is recolored red. Paths through the grandparent retain their former black count: the black contribution moves from the grandparent to one of its children. The local red–red violation disappears, but a new violation may arise between the grandparent and its parent. Repair therefore continues upward with the grandparent as the current node. Repeated recoloring can reach the root, which is made black at completion.
If the uncle is black, including when it is NIL, rotations resolve the violation locally. Suppose the parent is the grandparent’s left child. If the current node is the parent’s right child, the three nodes form an inner, or triangular, configuration. A left rotation at the parent converts this into an outer, or straight-line, configuration. The parent of the resulting configuration is then colored black, the grandparent red, and a right rotation is performed at the grandparent. When the parent is a right child, all directions are reversed.
A small example illustrates the distinction between rotation and recoloring. Inserting , , and in that order first creates a black root , then its red right child . Adding red node creates a red–red chain with a black NIL uncle. One left rotation at , together with recoloring, yields black root and red children and . If is inserted next, its parent and uncle are both red, so recoloring rather than an immediate rotation repairs that level.
This conventional insertion algorithm performs at most two rotations. Recoloring may propagate through ancestors, but the black-uncle rotation case terminates the repair. Including the initial search, insertion takes worst-case time. The two-rotation bound belongs to this particular bottom-up algorithm; other red–black formulations may organize their transformations differently and have different rotation counts.
Deletion and the black-deficit cases
Deletion is more intricate because removing a black node can destroy equal black heights. The first stage is ordinary binary-search-tree deletion. A node with at most one non-NIL child can be spliced out directly. For a node with two non-NIL children, its inorder successor, or alternatively its predecessor, supplies a replacement position or value, reducing the structural removal to a node with at most one non-NIL child.
Two colors must be distinguished carefully in this process: the color assigned to a node moved into the deleted node’s position, and the original color of the node removed from its former position. The latter determines whether a black-height deficit has been created. Copying only a successor’s key and value leaves the target node’s structural identity in place; transplanting the successor node instead changes object identity and requires more pointer updates. Both strategies can implement correct deletion, but they have different consequences for references and iterators.
Removing a red node does not change black height. If a removed black node has a red replacement child, coloring that child black restores the lost contribution. The difficult case is removal of a black node whose replacement is black or NIL. Algorithms often describe the replacement as carrying an extra black, or being double black. This is bookkeeping for a missing black contribution on one side, not necessarily a third stored color.
Let carry this deficit, and suppose is its parent’s left child. Its sibling is therefore the right child. The standard repair has four principal cases, with mirrored versions when is a right child:
- Red sibling: Recolor the sibling black and the parent red, then rotate left at the parent. This converts the situation into one with a black sibling.
- Black sibling with two black children: Color the sibling red and move the deficit to the parent. If the parent was red, making it black absorbs the deficit; otherwise, repair may continue upward.
- Black sibling with a red near child and a black far child: Here the near child is ’s left child. Recolor and rotate right at the sibling to obtain the final case.
- Black sibling with a red far child: Give the sibling the parent’s color, color the parent and far child black, and rotate left at the parent. This restores equal black heights and ends repair.
The cases either move the deficit upward or eliminate it through a local rearrangement. If it reaches the root, discarding the extra black is valid because all root-to-leaf paths lose the same contribution.
The conventional bottom-up deletion algorithm needs at most three rotations, although recoloring and upward propagation may take steps. Implementations must still identify a NIL replacement’s parent. Common solutions use a sentinel with an appropriate parent link or pass the parent separately to the repair routine. Many deletion defects arise from incorrect parent tracking, successor transplantation, or failure to distinguish the removed node’s original color from the replacement’s assigned color.
Multiway interpretation, history, and variants
The conceptual foundation of red–black trees is their correspondence with a 2–3–4 tree, a balanced multiway search tree whose internal nodes contain one, two, or three keys. If every red node is absorbed into its black parent, each resulting group becomes one multiway node. A black node with no red children represents a 2-node; one red child produces a 3-node; two red children produce a 4-node.
A red node cannot itself have a red child, so these groups never grow beyond three keys. Equal black heights ensure that all external leaves of the resulting multiway tree lie at the same depth. Thus the color rules are not merely arbitrary restrictions on binary trees: they encode the level structure of a balanced multiway tree. A 3-node can be represented by a red link leaning either left or right, so the correspondence is not unique.
Insertion can then be understood as adding a key to a multiway node and splitting a full node when necessary. Recoloring a black node with two red children transfers the conceptual middle key upward. Deletion corresponds to borrowing keys from neighboring nodes or merging nodes when one becomes deficient. The binary rotation cases implement these transformations without storing variable-size nodes explicitly.
Rudolf Bayer introduced symmetric binary B-trees in 1972, providing the principal predecessor of the modern structure. Leonidas J. Guibas and Robert Sedgewick presented the red–black formulation in their 1978 paper A Dichromatic Framework for Balanced Trees. The framework connected binary representations, color-based invariants, and balancing algorithms, helping establish the terminology and analysis used in subsequent treatments.
Several algorithmic families satisfy related invariants. Bottom-up algorithms first modify the tree and then repair violations while moving toward the root. Top-down algorithms transform nodes during descent, arranging that the eventual insertion or deletion can be completed without the same style of upward repair. The distinction affects control flow, temporary states, and implementation complexity rather than the fundamental logarithmic-height guarantee.
A left-leaning red–black tree adds restrictions on the orientation of red links to reduce the number of configurations. A common version represents 2–3 trees, allowing only left-leaning red links in the completed structure and excluding nodes with two red children. Other presentations accommodate 2–3–4 trees and use different transformation rules. Insertion and deletion procedures from different variants are not automatically interchangeable.
Functional formulations provide another important variant. Chris Okasaki’s 1999 treatment expressed insertion using a compact set of balancing patterns suitable for immutable trees. Such algorithms make structural sharing natural, but their case organization differs from conventional parent-pointer implementations. Consequently, familiar bounds on rotations for one formulation should not be transferred uncritically to another.
Representation, correctness, and verification
A conventional mutable red–black node stores a key or key–value entry, left and right child pointers, a parent pointer, and a color. Only one bit of information is logically necessary for the color, although alignment and object layout may cause a separate color field to occupy more physical space. Some implementations combine color with unused low-order bits of an aligned pointer. Such packing depends on representation assumptions and is not universally portable.
Parent pointers simplify insertion repair, deletion repair, and iterator movement, but they are not required by the data structure. Recursive implementations can recover ancestry through the call stack; iterative implementations can keep an explicit path. A recursive version uses stack space because the tree height is logarithmic. Iterative parent-pointer versions can perform ordinary updates with auxiliary space, excluding newly allocated nodes.
Correctness has several independent dimensions. The tree must preserve search order, maintain valid links and parent relationships, satisfy the color invariants, and preserve any associated metadata. A tree may return correct results for many searches while already containing a black-height violation. Conversely, perfectly valid colors cannot compensate for a misplaced subtree or an inconsistent comparator.
A recursive validator can check these properties together. It carries permitted key bounds into each subtree, checks parent links and red-child restrictions, and obtains the black heights returned by both children. A NIL child returns zero if the validator consistently uses a convention that excludes NIL from its count. For an internal node, equal child counts are required, and the returned count is increased by one exactly when that node is black. This counting convention differs from some textbook definitions but tests the same equality property.
Testing commonly compares the tree’s contents against a simpler reference representation after generated sequences of operations. Important cases include ascending and descending insertions, repeated root deletion, alternating minimum and maximum deletion, deletion of nodes with two children, and deletion down to an empty tree. Small exhaustive tests are especially effective because many defects require a specific sequence of operations rather than a single unusual key.
Formal verification separates the same obligations into explicit proofs. A rotation needs an ordering-preservation argument; an insertion case needs proofs of black-height preservation and controlled movement of a red–red violation; deletion needs an invariant describing the black deficit. Proofs for pointer-based implementations must additionally account for memory ownership and the absence of unintended cycles.
The comparator is part of the correctness assumptions. Ordered containers commonly require a strict weak ordering or a compatible total order. Mutable keys, inconsistent comparisons, or unhandled exceptional values can invalidate the search structure even when every rotation and recoloring is implemented correctly.
Augmentation and specialized queries
A major strength of red–black trees is that nodes can store summaries of their subtrees. When a summary can be recomputed from a node’s own entry and its children’s summaries in constant time, maintaining it usually preserves logarithmic update complexity. Structural changes affect only the search path and a small number of nodes involved in each rotation.
The standard example is an order-statistic tree. Each node stores its subtree size:
The key of a specified rank can be found by comparing the requested rank with the left subtree’s size. With one-based ranks, the current node has local rank . A smaller requested rank leads left; a larger one leads right after subtracting that local rank. Computing the rank of a key similarly accumulates the sizes of skipped left subtrees. Both operations take .
Rotation updates are local. After a left rotation, the former subtree root has new children and its size must be recomputed first. The promoted node’s size is then recomputed using the updated child. The rotated subtree contains the same elements as before, so its total size is unchanged. Insertions and deletions still require size changes along the affected ancestor paths, even if no rotation occurs.
An interval tree provides another classic augmentation. Nodes store intervals ordered by their lower endpoints and also record the maximum upper endpoint in their subtree. For closed intervals and , overlap occurs exactly when
During an overlap search, a left subtree whose maximum upper endpoint is less than the query’s lower endpoint can be excluded. The search combines this summary with the ordering of lower endpoints to select a promising subtree. Finding one overlapping interval takes in the standard augmented structure. Reporting every overlap needs a traversal and analysis appropriate to that operation; it is not simply a repetition of the single-path proof.
Other useful summaries include subtree sums, minimum priorities, and sequence aggregates. For an associative aggregate, a node can store the ordered combination of its left summary, its own value, and its right summary. Commutativity is unnecessary because rotations preserve inorder order. Query complexity nevertheless depends on the operation being supported: the existence of an aggregate does not make every possible query logarithmic.
The essential design requirement is local maintainability, not merely the presence of extra fields. A quantity that requires inspecting an entire subtree after each rotation can destroy the desired update bound. Implementations with augmentation therefore need explicit rules for propagation, node replacement, and rotation-time recomputation. These rules are as important as the red–black repair itself.
Applications and comparison with other structures
Red–black trees are frequently used to implement ordered maps and sets. Java’s TreeMap and TreeSet are established examples. Widely used C++ standard-library implementations also use red–black trees for ordered associative containers, although the C++ standard specifies behavior and complexity requirements rather than mandating that particular representation. This distinction matters when discussing implementation details such as node layout or balancing cases.
The Linux kernel provides an intrusive red–black tree interface: the tree-link object is embedded within an application’s own structure rather than allocated as a separate generic wrapper. This permits direct control over object layout and avoids an extra indirection between a tree node and its payload. Kernel users supply their own comparison and search logic. Augmentation support allows additional subtree metadata to be maintained where needed. The tree interface does not itself supply the locking required for concurrent access.
Compared with an AVL tree, a red–black tree permits a looser height bound. AVL trees restrict the height difference between sibling subtrees to at most one and consequently have a smaller worst-case height. Conventional red–black algorithms, however, offer small constant bounds on rotations per insertion or deletion. These theoretical distinctions do not determine performance on their own: search frequency, allocation strategy, key size, and processor behavior can outweigh the cost of balancing.
A B-tree or B+ tree groups many keys into each node, reducing the number of node visits and improving locality for page-oriented storage. These structures are therefore central to many database indexes and storage engines. Red–black trees, with several pointers per element and potentially scattered allocations, are usually less well matched to disk pages and can incur substantial cache misses in memory. Compact arrays or high-fanout trees may outperform them even when both offer logarithmic search.
Hash tables usually provide expected constant-time lookup under suitable hashing assumptions, but they do not naturally maintain sorted order. A red–black tree provides worst-case logarithmic comparison counts without depending on a distribution of hash values. A treap instead uses randomized priorities to obtain expected logarithmic height, while a splay tree achieves amortized logarithmic operation costs by reorganizing around accesses. Neither offers precisely the same per-operation worst-case guarantee as a conventional red–black tree.
For immutable software, a persistent data structure based on red–black trees can preserve earlier versions by copying only the modified root-to-leaf path and sharing unchanged subtrees. A single update then typically creates new nodes. In mutable concurrent software, rotations and recolorings require coordination with readers and writers; sequential red–black correctness does not imply thread safety. Specialized concurrent variants may permit temporary imbalance or use different synchronization protocols, so their guarantees must be analyzed separately from those of the ordinary sequential tree.