AIOJ

A red-black tree is a self-balancing binary search tree. Each node additionally stores a color field ("RED" or "BLACK") to ensure that the tree remains balanced during insertion and deletion.

A red-black tree is a variant of a 4-way B-tree (2-3-4 tree).¹

Properties

A valid red-black tree must satisfy the following four properties:

Every node is red or black
NIL nodes (empty leaf nodes) are black
The children of a red node are black
Every path from the root to a NIL node contains the same number of black nodes

The figure below shows a valid red-black tree:

rbtree-example

Note

Some sources add a fifth property: the root must be black. This property requires the root to be recolored black after insertion if it is red. However, because recoloring the root black can also be deferred until deletion, this property is not required (the implementation in this article does satisfy it). For rigor, the original Wikipedia text is quoted here:

Some authors, e.g. Cormen & al.,²claim "the root is black" as fifth requirement; but not Mehlhorn & Sanders³or Sedgewick & Wayne.⁴Since the root can always be changed from red to black, this rule has little effect on analysis. This article also omits it, because it slightly disturbs the recursive algorithms and proofs.

Definition of the Red-Black Tree Class

/**
 * An RBTree-based set implementation
 *
 * @tparam key_t key type
 * @tparam compare_t compare function
 */
template <typename key_t, typename compare_t = std::less<key_t>>
struct rb_tree {
  /**
   * Tree node
   */
  struct node_t {
    node_t *fa;     // == nullptr if root of the tree, otherwise parent
    node_t *ch[2];  // == nullptr if child is empty
                    // ch[0]: left child, ch[1]: right child
    key_t data;
    size_t sz;  // Size of subtree
    bool red;   // == true if node is red, otherwise black

    /**
     * Get child direction of current non-null node
     *
     * @return true if this node is right child of its parent, otherwise false
     */
    auto child_dir() const -> bool { return this == fa->ch[1]; }
  };

  using pointer = node_t *;
  using const_pointer = const node_t *;
  using pointer_const = node_t *const;

  const compare_t compare;
  pointer root;

  rb_tree() : compare{}, root{nullptr} {}
  // ...
};

Note

When storing red-black tree nodes, storing child pointers in an array can improve code reuse.

Operations

Note

There are several ways to implement red-black tree insertion and deletion. This article uses the implementation from Introduction to Algorithms, dividing post-insertion balance maintenance into 3 cases and post-deletion balance maintenance into 4 cases.

Traversal, finding the minimum/maximum, searching for an element, finding an element's rank, finding an element by rank, and finding a predecessor/successor in a red-black tree are the same as in a binary search tree, so they are not repeated here.

In addition, the following conventions are used in the code comments for insertion/deletion balance maintenance:

p means that node p is black;
[p] means that node p is red;
{p} means that node p is red or black;
|p| means that node p is a NIL node or is black.

Rotations

Rotations are key to maintaining balance in most balanced trees. They can change the depths of local nodes without changing the inorder traversal of a valid BST.

rbtree-rotations

Implementation

  /**
   * @param p root of subtree (may be same as {@code root})
   * @param dir direction. 0: left rotate; 1: right rotate
   * @return new root of subtree
   */
  auto rotate(pointer p, bool dir) -> pointer {
    auto g = p->fa;
    auto s = p->ch[!dir];  // new root of subtree
    assert(s);             // pointer to true node required
    s->sz = p->sz, p->sz = size(p->ch[dir]) + size(s->ch[dir]) + 1;
    auto c = s->ch[dir];
    if (c) c->fa = p;
    p->ch[!dir] = c, s->ch[dir] = p;
    p->fa = s, s->fa = g;
    if (g)
      g->ch[p == g->ch[1]] = s;
    else
      root = s;
    return s;
  }

Insertion

Insertion in a red-black tree is similar to insertion in an ordinary BST. In a red-black tree, a newly inserted node is initially red; after insertion, the states of the inserted node and related nodes must be adjusted to satisfy the four properties above.

Implementation

  /**
   * @return nullptr if insert failed, otherwise pointer of inserted node
   */
  auto insert(const key_t &data) -> const_pointer {
    pointer n = new node_t;
    n->fa = n->ch[0] = n->ch[1] = nullptr;
    n->data = data, n->sz = 1;
    pointer now = root, p = nullptr;
    bool dir = 0;
    while (now) {
      p = now;
      dir = compare(now->data, data);
      now = now->ch[dir];
    }
    insert_fixup_leaf(p, n, dir);
    return n;
  }
  /**
   * Insert leaf node {@code n} to {@code p}
   *
   * @param p parent of node which will be inserted
   * @param n leaf node which will be inserted
   * @param dir direction of n, 0: left; 1: right
   */
  void insert_leaf(pointer_const p, pointer_const n, bool dir) {
    if (!p) {
      root = n;
      return;
    }
    p->ch[dir] = n, n->fa = p;
    auto now = p;
    while (now) now->sz++, now = now->fa;
  }
  /**
   * Insert leaf node {@code n} to {@code p}, then fixup
   *
   * @param p parent of node which will be inserted
   * @param n node which will be inserted
   * @param dir direction of n, 0: left; 1: right
   */
  void insert_fixup_leaf(pointer p, pointer n, bool dir) {
    n->red = p;
    insert_leaf(p, n, dir);
    // Fix double red
    // ...
    // Post process: color root black
    root->red = false;
  }

Post-Insertion Balance Maintenance

Note

To deepen your understanding, verify for yourself that Property 4 holds after balance maintenance.

Because an inserted node is red unless it is the root, insertion may violate Property 3, so balance must be maintained.

Let the inserted node be $n$ , its parent be $p$ , its grandparent be $g$ , and its uncle be $u$ . By Property 3, $g$ must be black.

Starting at the insertion position, we recursively maintain balance upward. If $p$ is black, we can stop; otherwise, there are 3 cases.

    while (is_red(p = n->fa)) {
      bool p_dir = p->child_dir();
      auto g = p->fa, u = g->ch[!p_dir];
      // ...
    }

Insertion Case 1

$p$ and $u$ are both red. In this case, recoloring is sufficient.

Implementation

      // Case 1: both p and u are red
      //      g              [g]
      //     / \             / \
      //   [p] [u]   ==>    p   u
      //   /               /
      // [n]             [n]
      if (is_red(u)) {
        p->red = u->red = false;
        g->red = true;
        n = g;
        continue;
      }

Insertion Case 2

$p$ is red, $u$ is black, and the direction of $p$ differs from the direction of $n$ .

We rotate node $p$ to transform this into the third case.

Implementation

      // p is red and u is black
      // Case 2: dir of n is different with dir of p
      //    g              g
      //   / \            / \
      // [p]  u   ==>   [n]  u
      //   \            /
      //   [n]        [p]
      if (n->child_dir() != p_dir) rotate(p, p_dir), std::swap(n, p);

Insertion Case 3

$p$ is red, $u$ is black, and the direction of $p$ is the same as the direction of $n$ .

We rotate node $g$ to make $p$ the root of the subtree, then swap the colors of $p$ and $g$ .

Implementation

      // Case 3: p is red, u is black and dir of n is same as dir of p
      //      g             p
      //     / \           / \
      //   [p]  u   ==>  [n] [g]
      //   /                   \
      // [n]                    u
      p->red = false, g->red = true;
      rotate(g, !p_dir);

Deletion

Deletion in a red-black tree requires a few more steps than deletion in an ordinary BST. Specifically:

If the node $n$ to be deleted has two children, swap the data of $n$ and the smallest node $s$ in the right subtree, and set $n$ to $s$ . Then $n$ cannot have two children.
If the node $n$ to be deleted has one child $s$ , Property 4 implies that $s$ must be red, and Property 3 then implies that $n$ must be black. Thus, replace the pointer corresponding to $n$ in its parent $p$ with the address of $s$ , replace the parent pointer of $s$ with the address of $p$ , and then color $s$ black.
If the node $n$ to be deleted has no children, it can be deleted directly if $n$ is the root or if $n$ is red. Otherwise, direct deletion would violate Property 4, so balance must be maintained.

Implementation

  /**
   * @return succeed or not
   */
  auto erase(const key_t &key) -> bool {
    auto p = lower_bound(key);
    if (!p || p->data != key) return false;
    erase(p);
    return true;
  }

  /**
   * @return {@code next(p)}
   */
  auto erase(pointer p) -> const_pointer {
    if (!p) return nullptr;
    pointer result;
    if (p->ch[0] && p->ch[1]) {
      auto s = leftmost(p->ch[1]);
      std::swap(s->data, p->data);
      result = p, p = s;
    } else
      result = next(p);
    erase_fixup_branch_or_leaf(p);
    delete p;
    return result;
  }
  /**
   * Erase node {@code n}
   *
   * @param n node which will be deleted, must have no more than 2 child
   */
  void erase_branch_or_leaf(pointer_const n) {
    auto p = n->fa, s = n->ch[0] ? n->ch[0] : n->ch[1];
    if (s) s->fa = p;
    if (!p) {
      root = s;
      return;
    }
    p->ch[n->child_dir()] = s;
    auto now = p;
    while (now) now->sz--, now = now->fa;
  }
  /**
   * Erase node {@code n}, then fixup
   *
   * @param n node which will be deleted, must have no more than 2 child
   */
  void erase_fixup_branch_or_leaf(pointer n) {
    bool n_dir = n == root ? false : n->child_dir();
    erase_branch_or_leaf(n);
    auto p = n->fa;
    if (!p) {  // n is root
      if (root) root->red = false;
      return;
    } else {
      auto s = p->ch[n_dir];
      if (s) {  // n has 1 child
        // n must be black and s must be red, so we need to color s black
        s->red = false;
        return;
      }
    }
    // n is not root but leaf with black color, need to be fixup
    // ...
    // Post process: see case 2 & case 4
    n->red = false;
  }

Post-Deletion Balance Maintenance

Note

To deepen your understanding, verify for yourself that Property 4 holds after balance maintenance.

As discussed above, $n$ is a black leaf node and is not the root. Let $n$ 's parent be $p$ , its sibling be $s$ , and its nephews be $c$ and $d$ , respectively.

Deletion maintenance also proceeds recursively upward from $n$ . It can stop if $n$ is the root or if $n$ is red; otherwise, there are 4 cases.

    while (p && !n->red) {
      auto s = p->ch[!n_dir];
      // Delete case 1
      // ...
      // Other cases
      // s must be black
      auto c = s->ch[n_dir], d = s->ch[!n_dir];
      // ...
    end_erase_fixup:
      p = n->fa;
      if (!p) break;
      n_dir = n->child_dir();
    }

Deletion Case 1

$s$ is red.

We rotate $p$ to make $s$ the root of the subtree, then swap the colors of $s$ and $p$ to transform this into one of the other three cases.

Implementation

      // Case 1: s is red
      //    p               s
      //   / \             / \
      // |n| [s]   ==>   [p]  d
      //     / \         / \
      //    c   d      |n|  c
      if (is_red(s)) {
        s->red = false, p->red = true;
        rotate(p, n_dir);
        s = p->ch[!n_dir];
      }

Deletion Case 2

The color of $p$ is unspecified, and $s$ , $c$ , and $d$ are all black.

In this case, it is sufficient to color $s$ red.

Note that if $p$ is red, this would violate Property 3. However, the loop exits immediately when $p$ is red, so we color it black at the end.

Implementation

      // Case 2: both c and d are black
      //   {p}          {p}
      //   / \          / \
      // |n|  s   ==> |n| [s]
      //     / \          / \
      //    c   d        c   d
      // p will be colored black in the end
      if (!is_red(c) && !is_red(d)) {
        s->red = true;
        n = p;
        goto end_erase_fixup;
      }

Deletion Case 3

The color of $p$ is unspecified, $s$ and $d$ are black, and $c$ is red.

We rotate $s$ so that $c$ becomes the root of the subtree formerly rooted at $s$ , then swap the colors of $s$ and $c$ to transform this into the fourth case.

Implementation

      // Case 3: c is red and d is black
      //   {p}          {p}
      //   / \          / \
      // |n|  s   ==> |n|  c
      //     / \            \
      //   [c]  d           [s]
      //                      \
      //                       d
      if (!is_red(d)) {
        c->red = false, s->red = true;
        rotate(s, !n_dir);
        s = p->ch[!n_dir], c = s->ch[n_dir], d = s->ch[!n_dir];
      }

Deletion Case 4

The colors of $p$ and $c$ are unspecified, $s$ is black, and $d$ is red.

We rotate $p$ to make $s$ the root of the subtree, swap the colors of $s$ and $p$ , and color $d$ black; balance maintenance can then stop.

Implementation

      // Case 4: d is red
      //   {p}            {s}
      //   / \            / \
      // |n|  s   ==>    p   d
      //     / \        / \
      //   {c} [d]    |n| {c}
      s->red = p->red, p->red = d->red = false;
      rotate(p, n_dir), n = root;

Reference Code

The following code implements a set with a red-black tree:

Implementation

/**
 * @file rbtree.hpp
 * @brief An RBTree-based set implementation
 * @details The set is sorted according to the {@code compare_t} function
 * provided; This implementation provides find, insert, remove, find order, find
 * key by order in O(log(n)) time.
 * @author [Tiphereth-A](https://github.com/Tiphereth-A)
 */

#ifndef RBTREE_HPP
#define RBTREE_HPP

// --8<-- [start:class]
#include <cassert>
#include <cstdint>
#include <functional>

using std::size_t;

// --8<-- [start:class-node1]
/**
 * An RBTree-based set implementation
 *
 * @tparam key_t key type
 * @tparam compare_t compare function
 */
template <typename key_t, typename compare_t = std::less<key_t>>
struct rb_tree {
  /**
   * Tree node
   */
  struct node_t {
    node_t *fa;     // == nullptr if root of the tree, otherwise parent
    node_t *ch[2];  // == nullptr if child is empty
                    // ch[0]: left child, ch[1]: right child
    key_t data;
    size_t sz;  // Size of subtree
    bool red;   // == true if node is red, otherwise black

    /**
     * Get child direction of current non-null node
     *
     * @return true if this node is right child of its parent, otherwise false
     */
    auto child_dir() const -> bool { return this == fa->ch[1]; }
  };

  using pointer = node_t *;
  using const_pointer = const node_t *;
  using pointer_const = node_t *const;

  const compare_t compare;
  pointer root;

  rb_tree() : compare{}, root{nullptr} {}

  // --8<-- [end:class-node1]

  ~rb_tree() {
    post_order([](auto it) { delete it; });
  }

  auto size() const -> size_t { return size(root); }

  template <typename F>
  void pre_order(F callback) {
    auto f = [&](auto &&f, pointer p) {
      if (!p) return;
      callback(p), f(f, p->ch[0]), f(f, p->ch[1]);
    };
    f(f, root);
  }

  template <typename F>
  void in_order(F callback) {
    auto f = [&](auto &&f, pointer p) {
      if (!p) return;
      f(f, p->ch[0]), callback(p), f(f, p->ch[1]);
    };
    f(f, root);
  }

  template <typename F>
  void post_order(F callback) {
    auto f = [&](auto &&f, pointer p) {
      if (!p) return;
      f(f, p->ch[0]), f(f, p->ch[1]), callback(p);
    };
    f(f, root);
  }

  auto leftmost(const_pointer p) const { return most(p, 0); }

  auto rightmost(const_pointer p) const { return most(p, 1); }

  auto prev(const_pointer p) const { return neighbour(p, 0); }

  auto next(const_pointer p) const { return neighbour(p, 1); }

  auto lower_bound(const key_t &key) const -> pointer {
    const_pointer now = root, ans = nullptr;
    while (now) {
      if (!compare(now->data, key))
        ans = now, now = now->ch[0];
      else
        now = now->ch[1];
    }
    return (pointer)ans;
  }

  auto upper_bound(const key_t &key) const -> pointer {
    const_pointer now = root, ans = nullptr;
    while (now) {
      if (compare(key, now->data))
        ans = now, now = now->ch[0];
      else
        now = now->ch[1];
    }
    return (pointer)ans;
  }

  // Order start from 0
  auto order_of_key(const key_t &key) const -> size_t {
    size_t ans = 0;
    auto now = root;
    while (now) {
      if (!compare(now->data, key))
        now = now->ch[0];
      else
        ans += size(now->ch[0]) + 1, now = now->ch[1];
    }
    return ans;
  }

  // Order start from 0
  auto find_by_order(size_t order) const -> const_pointer {
    const_pointer now = root, ans = nullptr;
    while (now && now->sz >= order) {
      auto lsize = size(now->ch[0]);
      if (order < lsize)
        now = now->ch[0];
      else {
        ans = now;
        if (order == lsize) break;
        now = now->ch[1], order -= lsize + 1;
      }
    }
    return ans;
  }

  // --8<-- [start:insert]
  /**
   * @return nullptr if insert failed, otherwise pointer of inserted node
   */
  auto insert(const key_t &data) -> const_pointer {
    pointer n = new node_t;
    n->fa = n->ch[0] = n->ch[1] = nullptr;
    n->data = data, n->sz = 1;
    pointer now = root, p = nullptr;
    bool dir = 0;
    while (now) {
      p = now;
      dir = compare(now->data, data);
      now = now->ch[dir];
    }
    insert_fixup_leaf(p, n, dir);
    return n;
  }

  // --8<-- [end:insert]
  // --8<-- [start:delete]
  /**
   * @return succeed or not
   */
  auto erase(const key_t &key) -> bool {
    auto p = lower_bound(key);
    if (!p || p->data != key) return false;
    erase(p);
    return true;
  }

  /**
   * @return {@code next(p)}
   */
  auto erase(pointer p) -> const_pointer {
    if (!p) return nullptr;
    pointer result;
    if (p->ch[0] && p->ch[1]) {
      auto s = leftmost(p->ch[1]);
      std::swap(s->data, p->data);
      result = p, p = s;
    } else
      result = next(p);
    erase_fixup_branch_or_leaf(p);
    delete p;
    return result;
  }

  // --8<-- [end:delete]
 private:
  static auto size(const_pointer p) -> size_t { return p ? p->sz : 0; }

  static auto is_red(const_pointer p) -> bool { return p ? p->red : false; }

  /**
   * @param dir 0: leftmost, 1: rightmost
   */
  auto most(const_pointer p, bool dir) const -> pointer {
    if (!p) return nullptr;
    while (p->ch[dir]) p = p->ch[dir];
    return (pointer)p;
  }

  /**
   * @param dir 0: prev, 1: next
   */
  auto neighbour(const_pointer p, bool dir) const -> pointer {
    if (!p) return nullptr;
    if (p->ch[dir]) return most(p->ch[dir], !dir);
    if (p == root) return nullptr;
    while (p && p->fa && p->child_dir() == dir) p = p->fa;
    return p ? p->fa : nullptr;
  }

  // --8<-- [start:insert-leaf]
  /**
   * Insert leaf node {@code n} to {@code p}
   *
   * @param p parent of node which will be inserted
   * @param n leaf node which will be inserted
   * @param dir direction of n, 0: left; 1: right
   */
  void insert_leaf(pointer_const p, pointer_const n, bool dir) {
    if (!p) {
      root = n;
      return;
    }
    p->ch[dir] = n, n->fa = p;
    auto now = p;
    while (now) now->sz++, now = now->fa;
  }

  // --8<-- [end:insert-leaf]
  // --8<-- [start:delete-leaf]
  /**
   * Erase node {@code n}
   *
   * @param n node which will be deleted, must have no more than 2 child
   */
  void erase_branch_or_leaf(pointer_const n) {
    auto p = n->fa, s = n->ch[0] ? n->ch[0] : n->ch[1];
    if (s) s->fa = p;
    if (!p) {
      root = s;
      return;
    }
    p->ch[n->child_dir()] = s;
    auto now = p;
    while (now) now->sz--, now = now->fa;
  }

  // --8<-- [end:delete-leaf]
  // --8<-- [start:rotate]
  /**
   * @param p root of subtree (may be same as {@code root})
   * @param dir direction. 0: left rotate; 1: right rotate
   * @return new root of subtree
   */
  auto rotate(pointer p, bool dir) -> pointer {
    auto g = p->fa;
    auto s = p->ch[!dir];  // new root of subtree
    assert(s);             // pointer to true node required
    s->sz = p->sz, p->sz = size(p->ch[dir]) + size(s->ch[dir]) + 1;
    auto c = s->ch[dir];
    if (c) c->fa = p;
    p->ch[!dir] = c, s->ch[dir] = p;
    p->fa = s, s->fa = g;
    if (g)
      g->ch[p == g->ch[1]] = s;
    else
      root = s;
    return s;
  }

  // --8<-- [end:rotate]
#pragma GCC diagnostic ignored "-Wcomment"

  // --8<-- [start:insert-fixup1]
  /**
   * Insert leaf node {@code n} to {@code p}, then fixup
   *
   * @param p parent of node which will be inserted
   * @param n node which will be inserted
   * @param dir direction of n, 0: left; 1: right
   */
  void insert_fixup_leaf(pointer p, pointer n, bool dir) {
    n->red = p;
    insert_leaf(p, n, dir);
    // Fix double red
    // --8<-- [end:insert-fixup1]
    // --8<-- [start:insert-aux1]
    while (is_red(p = n->fa)) {
      bool p_dir = p->child_dir();
      auto g = p->fa, u = g->ch[!p_dir];
      // --8<-- [end:insert-aux1]
      // --8<-- [start:insert-case1]
      // Case 1: both p and u are red
      //      g              [g]
      //     / \             / \
      //   [p] [u]   ==>    p   u
      //   /               /
      // [n]             [n]
      if (is_red(u)) {
        p->red = u->red = false;
        g->red = true;
        n = g;
        continue;
      }
      // --8<-- [end:insert-case1]
      // --8<-- [start:insert-case2]
      // p is red and u is black
      // Case 2: dir of n is different with dir of p
      //    g              g
      //   / \            / \
      // [p]  u   ==>   [n]  u
      //   \            /
      //   [n]        [p]
      if (n->child_dir() != p_dir) rotate(p, p_dir), std::swap(n, p);
      // --8<-- [end:insert-case2]
      // --8<-- [start:insert-case3]
      // Case 3: p is red, u is black and dir of n is same as dir of p
      //      g             p
      //     / \           / \
      //   [p]  u   ==>  [n] [g]
      //   /                   \
      // [n]                    u
      p->red = false, g->red = true;
      rotate(g, !p_dir);
      // --8<-- [end:insert-case3]
      // --8<-- [start:insert-aux2]
    }
    // --8<-- [end:insert-aux2]
    // --8<-- [start:insert-fixup2]
    // Post process: color root black
    root->red = false;
  }

  // --8<-- [end:insert-fixup2]
  // --8<-- [start:delete-fixup1]
  /**
   * Erase node {@code n}, then fixup
   *
   * @param n node which will be deleted, must have no more than 2 child
   */
  void erase_fixup_branch_or_leaf(pointer n) {
    bool n_dir = n == root ? false : n->child_dir();
    erase_branch_or_leaf(n);
    auto p = n->fa;
    if (!p) {  // n is root
      if (root) root->red = false;
      return;
    } else {
      auto s = p->ch[n_dir];
      if (s) {  // n has 1 child
        // n must be black and s must be red, so we need to color s black
        s->red = false;
        return;
      }
    }
    // n is not root but leaf with black color, need to be fixup
    // --8<-- [end:delete-fixup1]
    // --8<-- [start:delete-aux1]
    while (p && !n->red) {
      auto s = p->ch[!n_dir];
      // --8<-- [end:delete-aux1]
      // --8<-- [start:delete-case1]
      // Case 1: s is red
      //    p               s
      //   / \             / \
      // |n| [s]   ==>   [p]  d
      //     / \         / \
      //    c   d      |n|  c
      if (is_red(s)) {
        s->red = false, p->red = true;
        rotate(p, n_dir);
        s = p->ch[!n_dir];
      }
      // --8<-- [end:delete-case1]
      // --8<-- [start:delete-aux2]
      // s must be black
      auto c = s->ch[n_dir], d = s->ch[!n_dir];
      // --8<-- [end:delete-aux2]
      // --8<-- [start:delete-case2]
      // Case 2: both c and d are black
      //   {p}          {p}
      //   / \          / \
      // |n|  s   ==> |n| [s]
      //     / \          / \
      //    c   d        c   d
      // p will be colored black in the end
      if (!is_red(c) && !is_red(d)) {
        s->red = true;
        n = p;
        goto end_erase_fixup;
      }
      // --8<-- [end:delete-case2]
      // --8<-- [start:delete-case3]
      // Case 3: c is red and d is black
      //   {p}          {p}
      //   / \          / \
      // |n|  s   ==> |n|  c
      //     / \            \
      //   [c]  d           [s]
      //                      \
      //                       d
      if (!is_red(d)) {
        c->red = false, s->red = true;
        rotate(s, !n_dir);
        s = p->ch[!n_dir], c = s->ch[n_dir], d = s->ch[!n_dir];
      }
      // --8<-- [end:delete-case3]
      // --8<-- [start:delete-case4]
      // Case 4: d is red
      //   {p}            {s}
      //   / \            / \
      // |n|  s   ==>    p   d
      //     / \        / \
      //   {c} [d]    |n| {c}
      s->red = p->red, p->red = d->red = false;
      rotate(p, n_dir), n = root;
      // --8<-- [end:delete-case4]
      // --8<-- [start:delete-aux3]
    end_erase_fixup:
      p = n->fa;
      if (!p) break;
      n_dir = n->child_dir();
    }
    // --8<-- [end:delete-aux3]
    // --8<-- [start:delete-fixup2]
    // Post process: see case 2 & case 4
    n->red = false;
  }

  // --8<-- [end:delete-fixup2]
  // --8<-- [start:class-node2]
};

// --8<-- [end:class-node2]
#pragma GCC diagnostic warning "-Wcomment"

// --8<-- [end:class]
#endif  // RBTREE_HPP

Example problems: Luogu P3369 [Template] Ordinary Balanced Tree and Luogu P6136 [Template] Ordinary Balanced Tree (Data-Enhanced Version)

#include <cassert>
#include <cstdint>
#include <functional>

using std::size_t;

// --8<-- [start:class-node1]
/**
 * An RBTree-based set implementation
 *
 * @tparam key_t key type
 * @tparam compare_t compare function
 */
template <typename key_t, typename compare_t = std::less<key_t>>
struct rb_tree {
  /**
   * Tree node
   */
  struct node_t {
    node_t *fa;     // == nullptr if root of the tree, otherwise parent
    node_t *ch[2];  // == nullptr if child is empty
                    // ch[0]: left child, ch[1]: right child
    key_t data;
    size_t sz;  // Size of subtree
    bool red;   // == true if node is red, otherwise black

    /**
     * Get child direction of current non-null node
     *
     * @return true if this node is right child of its parent, otherwise false
     */
    auto child_dir() const -> bool { return this == fa->ch[1]; }
  };

  using pointer = node_t *;
  using const_pointer = const node_t *;
  using pointer_const = node_t *const;

  const compare_t compare;
  pointer root;

  rb_tree() : compare{}, root{nullptr} {}

  // --8<-- [end:class-node1]

  ~rb_tree() {
    post_order([](auto it) { delete it; });
  }

  auto size() const -> size_t { return size(root); }

  template <typename F>
  void pre_order(F callback) {
    auto f = [&](auto &&f, pointer p) {
      if (!p) return;
      callback(p), f(f, p->ch[0]), f(f, p->ch[1]);
    };
    f(f, root);
  }

  template <typename F>
  void in_order(F callback) {
    auto f = [&](auto &&f, pointer p) {
      if (!p) return;
      f(f, p->ch[0]), callback(p), f(f, p->ch[1]);
    };
    f(f, root);
  }

  template <typename F>
  void post_order(F callback) {
    auto f = [&](auto &&f, pointer p) {
      if (!p) return;
      f(f, p->ch[0]), f(f, p->ch[1]), callback(p);
    };
    f(f, root);
  }

  auto leftmost(const_pointer p) const { return most(p, 0); }

  auto rightmost(const_pointer p) const { return most(p, 1); }

  auto prev(const_pointer p) const { return neighbour(p, 0); }

  auto next(const_pointer p) const { return neighbour(p, 1); }

  auto lower_bound(const key_t &key) const -> pointer {
    const_pointer now = root, ans = nullptr;
    while (now) {
      if (!compare(now->data, key))
        ans = now, now = now->ch[0];
      else
        now = now->ch[1];
    }
    return (pointer)ans;
  }

  auto upper_bound(const key_t &key) const -> pointer {
    const_pointer now = root, ans = nullptr;
    while (now) {
      if (compare(key, now->data))
        ans = now, now = now->ch[0];
      else
        now = now->ch[1];
    }
    return (pointer)ans;
  }

  // Order start from 0
  auto order_of_key(const key_t &key) const -> size_t {
    size_t ans = 0;
    auto now = root;
    while (now) {
      if (!compare(now->data, key))
        now = now->ch[0];
      else
        ans += size(now->ch[0]) + 1, now = now->ch[1];
    }
    return ans;
  }

  // Order start from 0
  auto find_by_order(size_t order) const -> const_pointer {
    const_pointer now = root, ans = nullptr;
    while (now && now->sz >= order) {
      auto lsize = size(now->ch[0]);
      if (order < lsize)
        now = now->ch[0];
      else {
        ans = now;
        if (order == lsize) break;
        now = now->ch[1], order -= lsize + 1;
      }
    }
    return ans;
  }

  // --8<-- [start:insert]
  /**
   * @return nullptr if insert failed, otherwise pointer of inserted node
   */
  auto insert(const key_t &data) -> const_pointer {
    pointer n = new node_t;
    n->fa = n->ch[0] = n->ch[1] = nullptr;
    n->data = data, n->sz = 1;
    pointer now = root, p = nullptr;
    bool dir = 0;
    while (now) {
      p = now;
      dir = compare(now->data, data);
      now = now->ch[dir];
    }
    insert_fixup_leaf(p, n, dir);
    return n;
  }

  // --8<-- [end:insert]
  // --8<-- [start:delete]
  /**
   * @return succeed or not
   */
  auto erase(const key_t &key) -> bool {
    auto p = lower_bound(key);
    if (!p || p->data != key) return false;
    erase(p);
    return true;
  }

  /**
   * @return {@code next(p)}
   */
  auto erase(pointer p) -> const_pointer {
    if (!p) return nullptr;
    pointer result;
    if (p->ch[0] && p->ch[1]) {
      auto s = leftmost(p->ch[1]);
      std::swap(s->data, p->data);
      result = p, p = s;
    } else
      result = next(p);
    erase_fixup_branch_or_leaf(p);
    delete p;
    return result;
  }

  // --8<-- [end:delete]
 private:
  static auto size(const_pointer p) -> size_t { return p ? p->sz : 0; }

  static auto is_red(const_pointer p) -> bool { return p ? p->red : false; }

  /**
   * @param dir 0: leftmost, 1: rightmost
   */
  auto most(const_pointer p, bool dir) const -> pointer {
    if (!p) return nullptr;
    while (p->ch[dir]) p = p->ch[dir];
    return (pointer)p;
  }

  /**
   * @param dir 0: prev, 1: next
   */
  auto neighbour(const_pointer p, bool dir) const -> pointer {
    if (!p) return nullptr;
    if (p->ch[dir]) return most(p->ch[dir], !dir);
    if (p == root) return nullptr;
    while (p && p->fa && p->child_dir() == dir) p = p->fa;
    return p ? p->fa : nullptr;
  }

  // --8<-- [start:insert-leaf]
  /**
   * Insert leaf node {@code n} to {@code p}
   *
   * @param p parent of node which will be inserted
   * @param n leaf node which will be inserted
   * @param dir direction of n, 0: left; 1: right
   */
  void insert_leaf(pointer_const p, pointer_const n, bool dir) {
    if (!p) {
      root = n;
      return;
    }
    p->ch[dir] = n, n->fa = p;
    auto now = p;
    while (now) now->sz++, now = now->fa;
  }

  // --8<-- [end:insert-leaf]
  // --8<-- [start:delete-leaf]
  /**
   * Erase node {@code n}
   *
   * @param n node which will be deleted, must have no more than 2 child
   */
  void erase_branch_or_leaf(pointer_const n) {
    auto p = n->fa, s = n->ch[0] ? n->ch[0] : n->ch[1];
    if (s) s->fa = p;
    if (!p) {
      root = s;
      return;
    }
    p->ch[n->child_dir()] = s;
    auto now = p;
    while (now) now->sz--, now = now->fa;
  }

  // --8<-- [end:delete-leaf]
  // --8<-- [start:rotate]
  /**
   * @param p root of subtree (may be same as {@code root})
   * @param dir direction. 0: left rotate; 1: right rotate
   * @return new root of subtree
   */
  auto rotate(pointer p, bool dir) -> pointer {
    auto g = p->fa;
    auto s = p->ch[!dir];  // new root of subtree
    assert(s);             // pointer to true node required
    s->sz = p->sz, p->sz = size(p->ch[dir]) + size(s->ch[dir]) + 1;
    auto c = s->ch[dir];
    if (c) c->fa = p;
    p->ch[!dir] = c, s->ch[dir] = p;
    p->fa = s, s->fa = g;
    if (g)
      g->ch[p == g->ch[1]] = s;
    else
      root = s;
    return s;
  }

  // --8<-- [end:rotate]
#pragma GCC diagnostic ignored "-Wcomment"

  // --8<-- [start:insert-fixup1]
  /**
   * Insert leaf node {@code n} to {@code p}, then fixup
   *
   * @param p parent of node which will be inserted
   * @param n node which will be inserted
   * @param dir direction of n, 0: left; 1: right
   */
  void insert_fixup_leaf(pointer p, pointer n, bool dir) {
    n->red = p;
    insert_leaf(p, n, dir);
    // Fix double red
    // --8<-- [end:insert-fixup1]
    // --8<-- [start:insert-aux1]
    while (is_red(p = n->fa)) {
      bool p_dir = p->child_dir();
      auto g = p->fa, u = g->ch[!p_dir];
      // --8<-- [end:insert-aux1]
      // --8<-- [start:insert-case1]
      // Case 1: both p and u are red
      //      g              [g]
      //     / \             / \
      //   [p] [u]   ==>    p   u
      //   /               /
      // [n]             [n]
      if (is_red(u)) {
        p->red = u->red = false;
        g->red = true;
        n = g;
        continue;
      }
      // --8<-- [end:insert-case1]
      // --8<-- [start:insert-case2]
      // p is red and u is black
      // Case 2: dir of n is different with dir of p
      //    g              g
      //   / \            / \
      // [p]  u   ==>   [n]  u
      //   \            /
      //   [n]        [p]
      if (n->child_dir() != p_dir) rotate(p, p_dir), std::swap(n, p);
      // --8<-- [end:insert-case2]
      // --8<-- [start:insert-case3]
      // Case 3: p is red, u is black and dir of n is same as dir of p
      //      g             p
      //     / \           / \
      //   [p]  u   ==>  [n] [g]
      //   /                   \
      // [n]                    u
      p->red = false, g->red = true;
      rotate(g, !p_dir);
      // --8<-- [end:insert-case3]
      // --8<-- [start:insert-aux2]
    }
    // --8<-- [end:insert-aux2]
    // --8<-- [start:insert-fixup2]
    // Post process: color root black
    root->red = false;
  }

  // --8<-- [end:insert-fixup2]
  // --8<-- [start:delete-fixup1]
  /**
   * Erase node {@code n}, then fixup
   *
   * @param n node which will be deleted, must have no more than 2 child
   */
  void erase_fixup_branch_or_leaf(pointer n) {
    bool n_dir = n == root ? false : n->child_dir();
    erase_branch_or_leaf(n);
    auto p = n->fa;
    if (!p) {  // n is root
      if (root) root->red = false;
      return;
    } else {
      auto s = p->ch[n_dir];
      if (s) {  // n has 1 child
        // n must be black and s must be red, so we need to color s black
        s->red = false;
        return;
      }
    }
    // n is not root but leaf with black color, need to be fixup
    // --8<-- [end:delete-fixup1]
    // --8<-- [start:delete-aux1]
    while (p && !n->red) {
      auto s = p->ch[!n_dir];
      // --8<-- [end:delete-aux1]
      // --8<-- [start:delete-case1]
      // Case 1: s is red
      //    p               s
      //   / \             / \
      // |n| [s]   ==>   [p]  d
      //     / \         / \
      //    c   d      |n|  c
      if (is_red(s)) {
        s->red = false, p->red = true;
        rotate(p, n_dir);
        s = p->ch[!n_dir];
      }
      // --8<-- [end:delete-case1]
      // --8<-- [start:delete-aux2]
      // s must be black
      auto c = s->ch[n_dir], d = s->ch[!n_dir];
      // --8<-- [end:delete-aux2]
      // --8<-- [start:delete-case2]
      // Case 2: both c and d are black
      //   {p}          {p}
      //   / \          / \
      // |n|  s   ==> |n| [s]
      //     / \          / \
      //    c   d        c   d
      // p will be colored black in the end
      if (!is_red(c) && !is_red(d)) {
        s->red = true;
        n = p;
        goto end_erase_fixup;
      }
      // --8<-- [end:delete-case2]
      // --8<-- [start:delete-case3]
      // Case 3: c is red and d is black
      //   {p}          {p}
      //   / \          / \
      // |n|  s   ==> |n|  c
      //     / \            \
      //   [c]  d           [s]
      //                      \
      //                       d
      if (!is_red(d)) {
        c->red = false, s->red = true;
        rotate(s, !n_dir);
        s = p->ch[!n_dir], c = s->ch[n_dir], d = s->ch[!n_dir];
      }
      // --8<-- [end:delete-case3]
      // --8<-- [start:delete-case4]
      // Case 4: d is red
      //   {p}            {s}
      //   / \            / \
      // |n|  s   ==>    p   d
      //     / \        / \
      //   {c} [d]    |n| {c}
      s->red = p->red, p->red = d->red = false;
      rotate(p, n_dir), n = root;
      // --8<-- [end:delete-case4]
      // --8<-- [start:delete-aux3]
    end_erase_fixup:
      p = n->fa;
      if (!p) break;
      n_dir = n->child_dir();
    }
    // --8<-- [end:delete-aux3]
    // --8<-- [start:delete-fixup2]
    // Post process: see case 2 & case 4
    n->red = false;
  }

  // --8<-- [end:delete-fixup2]
  // --8<-- [start:class-node2]
};

// --8<-- [end:class-node2]
#pragma GCC diagnostic warning "-Wcomment"
#include <iostream>
#include <numeric>
#include <vector>

template <bool P6136>  // == false: P3369, == true: P6136
struct IO_luogu_P3369_P6136 {
  int last_ans = 0;
  std::size_t n, m;
  std::vector<int> a;
  std::vector<int> ans_list;

  void init() {
    std::cin >> n;
    if (!P6136) {
      m = n;
      return;
    }
    std::cin >> m;
    a.resize(n);
    for (auto &i : a) std::cin >> i;
  }

  int opt() {
    int x;
    std::cin >> x;
    return x;
  }

  int x() {
    int x;
    std::cin >> x;
    return P6136 ? x ^ last_ans : x;
  }

  void print(int ans) { ans_list.push_back(last_ans = ans); }

  void print_total_ans() {
    if (P6136)
      std::cout << std::accumulate(ans_list.begin(), ans_list.end(), 0,
                                   std::bit_xor<int>{})
                << '\n';
    else
      for (auto &&i : ans_list) std::cout << i << '\n';
  }
};

// Set this template parameter to false for the Luogu P3369 ordinary balanced-tree template.
IO_luogu_P3369_P6136<true> io;

int main() {
  std::cin.tie(nullptr)->sync_with_stdio(false);
  io.init();
  std::size_t n = io.n, m = io.m;
  rb_tree<std::pair<int, int>> bt;
  int cnt = 0;
  for (auto i : io.a) bt.insert(std::make_pair(i, cnt++));
  for (int i = 0, opt, x; (std::size_t)i < m; ++i) {
    opt = io.opt(), x = io.x();
    switch (opt) {
      case 1:
        bt.insert({x, cnt++});
        break;
      case 2:
        bt.erase(bt.lower_bound({x, 0}));
        break;
      case 3:
        io.print((int)bt.order_of_key({x, 0}) + 1);
        break;
      case 4:
        io.print(bt.find_by_order((uint32_t)x - 1)->data.first);
        break;
      case 6:
        io.print(bt.upper_bound({x, n + m})->data.first);
        break;
      case 5:
        auto it = bt.lower_bound({x, 0});
        io.print((it ? bt.prev(it) : bt.rightmost(bt.root))->data.first);
        break;
    }
  }
  io.print_total_ans();
  return 0;
}

Relationship with 2-3-4 trees

A 2-3-4 tree is a B-tree of order 4. Like general B-trees, it supports search, insertion, and deletion in $O(\log n)$ time. Its nodes come in three types—2-nodes, 3-nodes, and 4-nodes—containing one, two, and three data elements, respectively. All leaves are at the same depth (the bottom level), and all data is stored in sorted order.

2-3-4 trees and red-black trees are isomorphic: every red-black tree corresponds to a unique 2-3-4 tree. Insertion and deletion in a 2-3-4 tree cause node expansion, splitting, and merging, corresponding to recoloring and rotations in a red-black tree. The figure below shows the red-black-tree nodes corresponding to the 2-nodes, 3-nodes, and 4-nodes of a 2-3-4 tree. Notice that a 3-node corresponds to two cases in a red-black tree, with the red node leaning left or right, so one red-black tree may correspond to multiple 2-3-4 trees.

2-3-4-tree-rbt-1

The figure below shows a red-black tree and its corresponding 2-3-4 tree. Move the red nodes in the red-black tree up to the left and right sides of their parent to form a B-tree node, yielding the corresponding 2-3-4 tree. The number of red-black-tree nodes equals the number of nodes in the 2-3-4 tree.

2-3-4-tree-rbt

Comparing with 2-3-4 trees is a useful way to understand red-black-tree insertion and deletion.⁵

Use in real-world engineering projects

Red-black trees are currently among the most efficient general-purpose in-memory balanced trees in industry, so they are widely used in engineering projects. Several practical examples are listed below together with source-code links for comparison and study.

Linux

Source code:

linux/lib/rbtree.c

All red-black-tree operations in Linux are implemented iteratively for efficiency, while extensive comments maintain code readability. Readers are strongly encouraged to study the implementation. Red-black trees are used widely in the Linux kernel; only a few classic cases are listed here.

CFS scheduling of non-real-time tasks

After stable Linux kernels moved beyond 2.6.24, they used the new CFS scheduler. All runnable non-real-time processes are maintained in a red-black tree keyed by virtual runtime, enabling fairer and more efficient scheduling. CFS discarded the active/expired arrays and dynamic priority calculation; it no longer tracks task sleep time or distinguishes interactive tasks. Instead, scheduling uses a time-based red-black-tree key to choose the next task, with priority determined from each task's CPU-time usage.
epoll

epoll stands for event poll. It is Linux's implementation of I/O multiplexing, an improvement over the original poll/select. Linux uses a red-black tree to store file descriptors for epoll.

Nginx

Source code:

Nginx implements user-space timers with a red-black tree. All timer nodes are maintained in one red-black tree. On each worker-process loop, nginx calls ngx_process_events_and_timers, which in turn calls ngx_event_expire_timers. That function repeatedly removes the smallest time value from the red-black tree, checks whether it has expired, and runs its callback until the removed node is no longer expired.

There are many public analyses of nginx's red-black-tree source code; readers can search for them independently.

C++

Source code:

GNU libstdc++
- libstdc++-v3/include/bits/stl_tree.h
- libstdc++-v3/src/c++98/tree.cc
In addition, libstdc++ provides <ext/rb_tree> in __gnu_cxx::rb_tree. It inherits from std::_Rb_tree and can be regarded as a type alias exposed for external use. Note that this header is not part of the C++ standard, so its use is not recommended unless necessary.

libstdc++ also provides a red-black tree in pb_ds.
LLVM libcxx
- libcxx/include/__tree
Microsoft STL
- stl/inc/xtree

The internal data structures of std::set and std::map in most STLs are red-black trees, including the implementations mentioned above. However, the C++ standard does not require std::set or std::map to use red-black trees, so engineering code should not depend directly on the internal data structures of std::set and std::map.

OpenJDK

Source code:

Both TreeMap and TreeSet in the JDK use red-black trees as their underlying data structure. Since JDK 1.8, when a bucket's linked-list length in the internal hash table of HashMap exceeds 8, it is also automatically converted into a red-black tree to improve lookup efficiency.

References

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022).Introduction to algorithms. MIT press.
Red-Black Tree - Wikipedia
Red-Black Tree Visualization

Footnotes

L. J. Guibas and R. Sedgewick, "A dichromatic framework for balanced trees,"19th Annual Symposium on Foundations of Computer Science (sfcs 1978), Ann Arbor, MI, USA, 1978, pp. 8-21, doi:10.1109/SFCS.1978.3. ↩
https://en.wikipedia.org/wiki/Red–black_tree#cite_note-Cormen2009-18 ↩
https://en.wikipedia.org/wiki/Red–black_tree#cite_note-Mehlhorn2008-17 ↩
https://en.wikipedia.org/wiki/Red–black_tree#cite_note-Algs4-16: 432–447 ↩
This blog post provides a detailed description. ↩