Red-black tree

A red-black tree is a binary search tree in which each node is coloured red or black, so that no red node has a red child and every path from the root to a leaf passes through the same number of black nodes. These two rules keep the tree's height at most $2{\log }_2(n+1)$ for $n$ keys, so that search, insertion and deletion take $O(\log n)$ time in the worst case. A red-black tree is a binary encoding of a 2-3-4 tree^[2]. Red-black trees are used by the ordered maps of Java and C++ and by the Linux kernel, and in functional languages as persistent sets and maps, where Okasaki's formulation reduces insertion to a single rebalancing rule^[3].

In a binary search tree every key in a node's left subtree is smaller than the node's key and every key in its right subtree larger, so a search follows one path from the root. The cost of an operation is the length of that path, and a tree built by inserting keys in sorted order degenerates into a list of length $n$. A balanced search tree changes the shape of the tree during updates to keep its height logarithmic. Red-black trees do this with one bit of information per node, and rebalance with a constant number of local rearrangements, rotations, per update^[5].

A red-black tree is a binary search tree whose nodes are coloured red or black, with empty leaves counted as black, satisfying:

1. No red node has a red child.

2. Every path from a node down to an empty leaf contains the same number of black nodes.

Many presentations also require the root to be black; any red root can be recoloured black without breaking either rule, so implementations do that after each insertion. The number of black nodes on a path from a node to a leaf, not counting the node itself, is its black height $\mathrm{bh}$.

Height

A subtree whose root has black height $b$ contains at least $2^b-1$ internal nodes, by induction: each child has black height at least $b-1$. By rule 1, at least half of the nodes on any root-to-leaf path are black, so a tree of height $h$ has black height at least $h/2$. Therefore

The bound is tight up to lower-order terms: a tree can have one path that alternates red and black and another that is all black. AVL trees, which bound the difference in height between siblings, satisfy the stronger $h<1.4405{\log }_2(n+2)$^[8]; red-black trees give up some balance in exchange for fewer rotations on update.

A 2-3-4 tree is a B-tree of order 4^[10]: every node holds one, two or three keys and has one more child than keys, and all leaves are at the same depth. A red-black tree is a 2-3-4 tree in which each node is written as a black node with up to two red children. Merging every red node into its black parent recovers the 2-3-4 tree:

Rule 1 says that a 2-3-4 node has at most three keys, and rule 2 is the condition that all leaves of the 2-3-4 tree are at the same depth: the black height is the height of the 2-3-4 tree. The rebalancing operations of red-black trees are the splits and merges of 2-3-4 nodes. Bayer introduced the structure in 1972 as the symmetric binary B-tree^[1], and Guibas and Sedgewick recast it with colours in 1978^[2]. Allowing red nodes only as left children gives a binary encoding of 2-3 trees: Andersson's AA trees^[11] and Sedgewick's left-leaning red-black trees^[6].

A new key is inserted as a red node at the bottom of the tree, which preserves rule 2. It may break rule 1, if its parent is red. Okasaki observed that in a functional implementation every violation can be repaired by one rule applied on the way back up: when a black node has a red child with a red child, there are four possible arrangements, and all four are rewritten into the same tree^[3]:

type color = R | B
type 'a t = E | T of color * 'a t * 'a * 'a t
 
let rec mem x = function
  | E -> false
  | T (_, l, y, r) -> if x < y then mem x l else if x > y then mem x r else true
 
(* Okasaki's balance: the four ways a black node can have a red child with
   a red child, all rebuilt into one shape, a red node with two black
   children. *)
let balance = function
  | B, T (R, T (R, a, x, b), y, c), z, d
  | B, T (R, a, x, T (R, b, y, c)), z, d
  | B, a, x, T (R, T (R, b, y, c), z, d)
  | B, a, x, T (R, b, y, T (R, c, z, d)) ->
      T (R, T (B, a, x, b), y, T (B, c, z, d))
  | color, l, v, r -> T (color, l, v, r)
 
let insert x s =
  let rec ins = function
    | E -> T (R, E, x, E)
    | T (color, l, y, r) as s ->
        if x < y then balance (color, ins l, y, r)
        else if x > y then balance (color, l, y, ins r)
        else s
  in
  match ins s with T (_, l, y, r) -> T (B, l, y, r) | E -> assert false
 
(* The invariants: no red node has a red child, and every path from the
   root to a leaf has the same number of black nodes. Returns that number. *)
let rec black_height = function
  | E -> 1
  | T (c, l, _, r) ->
      (match (c, l, r) with
       | R, T (R, _, _, _), _ | R, _, T (R, _, _, _) -> failwith "red node with a red child"
       | _ -> ());
      let hl = black_height l and hr = black_height r in
      if hl <> hr then failwith "unequal black heights";
      hl + if c = B then 1 else 0
 
let rec height = function E -> 0 | T (_, l, _, r) -> 1 + max (height l) (height r)

keys                 n   height     bh - 1   2 log2(n+1)  plain BST
ascending        10000       18         13          26.6      10000
random           10000       19         10          26.6         28
ascending      1000000       26         19          39.9          -
random         1000000       29         15          39.9          -

The rewrite moves the red violation up one level, where it may be repaired by the next application of balance or reach the root, which is then coloured black. Keys inserted in ascending order, the worst case for an unbalanced tree, give a red-black tree of height 26 for a million keys, against the bound of 39.9. The functional version copies the path from the root to the new node, $O(\log n)$ nodes, and shares everything else with the previous version, so every earlier version of the set remains valid^[13].

Imperative insertion

The imperative algorithm modifies the tree in place and distinguishes cases by the colour of the new node's uncle, the sibling of its parent^[5]. If the uncle is red, the parent and uncle become black and the grandparent red, which moves the violation two levels up without changing the shape of the tree. If the uncle is black, one or two rotations and a recolouring fix the violation and end the process. An insertion therefore performs at most two rotations, and $O(1)$ recolourings amortized over a sequence of operations^[7].

Removing a red node at the bottom of the tree is harmless, but removing a black node leaves one path short of a black node, and the repair propagates upward through several cases. Imperative deletion performs at most three rotations^[5]. Okasaki's paper left deletion out, and the functional versions are noticeably more complicated than insertion. Kahrs gave a compact one^[4]; Germane and Might, noting how often it is omitted, gave another that uses a temporary double-black colour^[9].

(* Deletion, after Kahrs. Removing a black node shortens one path; the
   helpers restore equal black heights on the way back up. *)
type color = R | B
type 'a t = E | T of color * 'a t * 'a * 'a t
 
(* Kahrs's balance also accepts a black node with two red children. *)
let balance l v r =
  match (l, v, r) with
  | T (R, a, x, b), y, T (R, c, z, d)
  | T (R, T (R, a, x, b), y, c), z, d
  | T (R, a, x, T (R, b, y, c)), z, d
  | a, x, T (R, b, y, T (R, c, z, d))
  | a, x, T (R, T (R, b, y, c), z, d) ->
      T (R, T (B, a, x, b), y, T (B, c, z, d))
  | a, x, b -> T (B, a, x, b)
 
let insert x s =
  let rec ins = function
    | E -> T (R, E, x, E)
    | T (R, a, y, b) as s -> if x < y then T (R, ins a, y, b) else if x > y then T (R, a, y, ins b) else s
    | T (B, a, y, b) as s -> if x < y then balance (ins a) y b else if x > y then balance a y (ins b) else s
  in
  match ins s with T (_, a, y, b) -> T (B, a, y, b) | E -> assert false
 
let sub1 = function T (B, a, x, b) -> T (R, a, x, b) | _ -> invalid_arg "sub1"
 
(* The left subtree is one black node short. *)
let balleft l y r =
  match (l, r) with
  | T (R, a, x, b), c -> T (R, T (B, a, x, b), y, c)
  | bl, T (B, a, z, b) -> balance bl y (T (R, a, z, b))
  | bl, T (R, T (B, a, z, b), w, c) -> T (R, T (B, bl, y, a), z, balance b w (sub1 c))
  | _ -> invalid_arg "balleft"
 
(* The right subtree is one black node short. *)
let balright l y r =
  match (l, r) with
  | a, T (R, b, x, c) -> T (R, a, y, T (B, b, x, c))
  | T (B, a, x, b), bl -> balance (T (R, a, x, b)) y bl
  | T (R, a, x, T (B, b, z, c)), bl -> T (R, balance (sub1 a) x b, z, T (B, c, y, bl))
  | _ -> invalid_arg "balright"
 
(* Join two trees of equal black height, all of whose keys are in order. *)
let rec app l r =
  match (l, r) with
  | E, x | x, E -> x
  | T (R, a, x, b), T (R, c, y, d) -> (
      match app b c with
      | T (R, b', z, c') -> T (R, T (R, a, x, b'), z, T (R, c', y, d))
      | bc -> T (R, a, x, T (R, bc, y, d)))
  | T (B, a, x, b), T (B, c, y, d) -> (
      match app b c with
      | T (R, b', z, c') -> T (R, T (B, a, x, b'), z, T (B, c', y, d))
      | bc -> balleft a x (T (B, bc, y, d)))
  | a, T (R, b, x, c) -> T (R, app a b, x, c)
  | T (R, a, x, b), c -> T (R, a, x, app b c)
 
let delete x t =
  let rec del = function
    | E -> E
    | T (_, a, y, b) ->
        if x < y then (match a with T (B, _, _, _) -> balleft (del a) y b | _ -> T (R, del a, y, b))
        else if x > y then (match b with T (B, _, _, _) -> balright a y (del b) | _ -> T (R, a, y, del b))
        else app a b
  in
  match del t with T (_, a, y, b) -> T (B, a, y, b) | E -> E

200000 random operations (99867 inserts, 100133 deletes) on keys 0..1999
invariants held after every operation; contents always equal to Set
final size 964
after deleting everything: empty

balleft and balright are called when one subtree has lost a black node, and restore equal black heights by recolouring the sibling and rebalancing. app joins the two subtrees of a deleted node, which have equal black heights, by descending along the inner edges.

With generalized algebraic data types the colour and the black height can be recorded in a node's type, so that only valid trees type-check^[4]:

(* The invariants in the types. A node's type records its colour and its
   black height as a type-level natural number. *)
type z = Z
type 'n s = S of 'n
type red = Red
type black = Black
 
type (_, _) node =
  | Leaf : (black, z) node
  | R : (black, 'n) node * int * (black, 'n) node -> (red, 'n) node
  | B : (_, 'n) node * int * (_, 'n) node -> (black, 'n s) node
 
(* A tree is a black root of some black height. *)
type tree = Tree : (black, 'n) node -> tree
 
let rec mem : type c n. int -> (c, n) node -> bool =
 fun x -> function
  | Leaf -> false
  | R (l, y, r) -> if x < y then mem x l else x = y || mem x r
  | B (l, y, r) -> if x < y then mem x l else x = y || mem x r
 
let t = Tree (B (R (B (Leaf, 1, Leaf), 2, B (Leaf, 3, Leaf)), 4, B (Leaf, 5, Leaf)))

A black node's children may be of either colour but must have the same black height $n$, and the node's own black height is $n+1$. A red node has black children of equal height. Both invalid trees are rejected by the compiler:

(* A red node with a red child. *)
let red_red = B (R (R (Leaf, 1, Leaf), 2, Leaf), 3, Leaf)
 
(* Paths with different numbers of black nodes. *)
let unequal = B (B (Leaf, 1, Leaf), 2, Leaf)

File "r3_bad.ml", line 12, characters 20-37:
12 | let red_red = B (R (R (Leaf, 1, Leaf), 2, Leaf), 3, Leaf)
                         ^^^^^^^^^^^^^^^^^
Error: This expression has type (red, 'a) node
       but an expression was expected of type (black, 'b) node
       Type red is not compatible with type black
File "r3_bad2.ml", line 12, characters 39-43:
12 | let unequal = B (B (Leaf, 1, Leaf), 2, Leaf)
                                            ^^^^
Error: This expression has type (black, z) node
       but an expression was expected of type (black, z s) node
       Type z is not compatible with type z s

Insertion into such a tree has to be typed too, which requires an intermediate type for the temporarily invalid tree returned by the recursive call, with a red node that may have one red child. Kahrs did this in Haskell with nested types^[4] and GADTs make it direct.

Search, insertion and deletion take $O(\log n)$ time in the worst case. Imperative insertion performs at most two rotations and deletion at most three, and the number of colour changes is $O(1)$ amortized^[7], which makes red-black trees suitable for persistence by node copying, where each modification costs space^[12]. The functional version copies $O(\log n)$ nodes per update, and the extra bit per node is often stored in an unused bit of a pointer.

Java's TreeMap and TreeSet and the std::map and std::set of the GNU and LLVM C++ standard libraries are red-black trees. The Linux kernel has a generic red-black tree used by, among others, its process scheduler, which keeps runnable tasks ordered by virtual run time. Functional languages use a variety of balanced trees: OCaml's Set and Map are height-balanced trees in which sibling heights may differ by up to two, and Haskell's Data.Map uses weight-balanced trees.

Adelson-Velsky and Landis published the first balanced search tree, the AVL tree, in 1962^[8]. Bayer and McCreight introduced B-trees in 1972^[10], and in the same year Bayer described symmetric binary B-trees, the binary form of 2-3-4 trees^[1]. Guibas and Sedgewick introduced the red and black colouring in 1978, as a framework in which several balanced trees could be described^[2]. Tarjan showed in 1983 that updates need only $O(1)$ rotations^[7]. Okasaki's 1999 functional pearl gave the four-case insertion^[3], Kahrs the typed version and a compact deletion in 2001^[4], and Sedgewick the left-leaning variant in 2008^[6].

• Finger treeA persistent sequence with amortized constant-time access at both ends, and concatenation and splitting in logarithmic time. The ends are kept in buffers of one to four elements, and the middle is a finger tree of 2-3 nodes, one level deeper at each step down the spine.
• ZipperA zipper represents a data structure together with a focus, a position inside it: the substructure at the focus, and the path from the focus back to the root together with everything to either side of that path. Moving the focus one step and editing at the focus take constant time, and the structure is persistent, so edits share everything off the path. The type of paths is the derivative of the structure's type, in the sense of calculus.
• GADTA generalized algebraic data type (GADT) is an algebraic data type whose constructors may each give a more specific result type than the declared one, instead of all sharing one polymorphic return type. Matching on a constructor then tells the type checker what the type parameter was, so a single well-typed eval can return an int for an Add node and a bool for an Eq node, checked at compile time rather than by a run-time tag test. GADTs express typed syntax trees, type representations and equality proofs, typed format strings and length-indexed data. The price is that type inference needs annotations.
• Algebraic data typeAn algebraic data type is a type built from sums, where a value is one of several alternatives, and products, where a value has several components at once, possibly recursively. The name comes from counting: the number of values of a sum is the sum of the counts, and of a product their product, so types obey the laws of algebra. Values are taken apart by pattern matching, which the compiler checks for missing cases.
• Braun treeA Braun tree is a binary tree in which, at every node, the left subtree has either the same number of nodes as the right subtree or exactly one more. The shape is therefore determined by the size alone, and the height is ⌊log₂ n⌋ + 1. Used as a flexible array, element 0 is at the root and the bits of an index choose the path, so indexing, updating, and adding or removing an element at the front all take logarithmic time without any rebalancing.
• Hash array mapped trieA hash array mapped trie (HAMT) is a trie over the bits of the keys' hash values: each level consumes a few bits, usually five, to choose one of 32 children, and each node stores only its occupied children in a compact array, located by counting bits in a 32-bit bitmap. Lookups follow about log32 n levels. Updated by copying the path to the changed leaf, a HAMT is a persistent hash map with small, cache-friendly nodes, and it is the standard implementation of immutable maps and sets in Clojure, Scala and Haskell's unordered-containers.
• Leftist heapA leftist heap is a priority queue represented as a heap-ordered binary tree in which, at every node, the right spine of the left child is at least as long as the right spine of the right child. The right spine of the whole tree then has at most log₂(n + 1) nodes, and two heaps can be merged in O(log n) time by merging their right spines like sorted lists. Insertion and deletion of the minimum are special cases of merging. Because merging copies only the right spines, leftist heaps are a standard persistent priority queue in functional languages.
• Splay treeA splay tree is a binary search tree that keeps no balance information and instead moves every node it accesses to the root, by a sequence of rotations called splaying. Single operations can take linear time, but any sequence of m operations on a tree of n nodes takes O((m + n) log n) time, so each operation is logarithmic amortized. Because recently used keys end up near the root, splay trees adapt to the access pattern.
• TrieA trie, or prefix tree, is a tree for a set of strings in which each edge is labelled with a character and each key is the path from the root to a node; keys with a common prefix share the nodes of that prefix. Lookup and insertion take time proportional to the length of the key, independent of the number of keys, and all keys with a given prefix are found in one subtree, in sorted order. Radix and Patricia trees compress chains of single-child nodes, and the same idea applies to integers, read bit by bit.
• Union–findUnion–find, or a disjoint-set forest, maintains a partition of a set into disjoint classes under two operations: union merges two classes, and find returns a representative of an element's class. Each class is a tree of parent pointers whose root is the representative. With union by rank and path compression, any sequence of m operations on n elements takes O(m α(n)) time, where α is the inverse Ackermann function, which is at most 4 for any practical n.

1. [1]R. Bayer, “Symmetric binary B-trees: data structure and maintenance algorithms”, Acta Informatica 1 (1972).
2. [2]L. J. Guibas, R. Sedgewick, “A dichromatic framework for balanced trees”, 19th Symposium on Foundations of Computer Science (1978).
3. [3]C. Okasaki, “Red-black trees in a functional setting”, Journal of Functional Programming 9 (1999).
4. [4]S. Kahrs, “Red-black trees with types”, Journal of Functional Programming 11 (2001).
5. [5]T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, ch. 13, MIT Press (3rd ed., 2009).
6. [6]R. Sedgewick, “Left-leaning red-black trees”, Dagstuhl Workshop on Data Structures (2008).
7. [7]R. E. Tarjan, “Updating a balanced search tree in O(1) rotations”, Information Processing Letters 16 (1983).
8. [8]G. M. Adelson-Velsky, E. M. Landis, “An algorithm for the organization of information”, Soviet Mathematics Doklady 3 (1962).
9. [9]K. Germane, M. Might, “Deletion: the curse of the red-black tree”, Journal of Functional Programming 24 (2014).
10. [10]R. Bayer, E. McCreight, “Organization and maintenance of large ordered indexes”, Acta Informatica 1 (1972).
11. [11]A. Andersson, “Balanced search trees made simple”, Workshop on Algorithms and Data Structures, LNCS 709 (1993).
12. [12]J. R. Driscoll, N. Sarnak, D. D. Sleator, R. E. Tarjan, “Making data structures persistent”, Journal of Computer and System Sciences 38 (1989).
13. [13]C. Okasaki, Purely Functional Data Structures, Cambridge University Press (1998).

last updated 27 September 2026