Red-Black Tree Deletion Explained (Part 2)

Introduction

In the first part we introduced binary trees, their search algorithm, the five properties of red‑black trees, and the operations of recoloring, left‑rotation, and right‑rotation, as well as the five insertion scenarios. This second part focuses on the last operation – deleting a node – which is more complex but can be understood by classifying the different cases.

Red‑Black Tree Deletion

Deletion consists of two steps: locating the node to delete (identical to binary‑tree search) and then removing the node while restoring the tree’s balance. If the node does not exist, the operation ends; otherwise the node is removed and a replacement node is chosen to reconnect the parent and children.

When deleting node D, a suitable replacement must be found; otherwise the links between P, L, and R would break, violating red‑black properties and creating a separate subtree.

Find Node

The search algorithm is the same as in a binary search tree: compare the target key with the current node’s key, move left if smaller, right if larger, and stop when the keys match.

In a binary search tree, start from the root; if the current node is null the search fails, if the key equals the node’s key return the node, otherwise continue left or right based on the comparison.

Replace Node

Recall the binary‑search‑tree properties: all keys in a left subtree are smaller than the parent’s key, and all keys in a right subtree are larger. After deletion we can use either the maximum node of the left subtree or the minimum node of the right subtree as a replacement.

There are three replacement scenarios:

Scenario 1 – the deleted node has no children; it can be removed directly.

Scenario 2 – the deleted node has a single child; the child replaces the deleted node.

Scenario 3 – the deleted node has two children; we replace it with its successor (the minimum node in the right subtree) or predecessor (the maximum node in the left subtree). This article adopts the successor.

Successor: the left‑most (minimum) node in the right subtree. Predecessor: the right‑most (maximum) node in the left subtree.

Node Deletion Cases

Node deletion is reduced to deleting the replacement node, leading to nine distinct cases. The first four cases (Scenario 2) are mirror images of the next four (Scenario 3).

Deletion Scenario 1 – replacement node is red. Deleting it does not affect balance; simply recolor the replacement to the deleted node’s color.

Process: delete node D, find replacement R, set R’s color to D’s color, then replace D with R.

Deletion Scenario 2 – replacement node is black and is the left child of its parent. This splits into four sub‑scenarios:

Scenario 2.1 – sibling is red. Recolor sibling black, parent red, then perform a left rotation on the parent, converting to Scenario 2.4.

Process: set parent P red, sibling S black, rotate left on P, then treat the new configuration as Scenario 2.4.

Scenario 2.2 – sibling is black and its right child is red. Recolor sibling with parent’s color, set the right child black, recolor parent black, then left‑rotate the parent to restore balance.

Process: sibling S takes parent P’s color, SR becomes black, P becomes black, then rotate left on P.

Scenario 2.3 – sibling is black, its left child is red, right child black. Recolor sibling red, left child black, then perform a right rotation on sibling, which converts to Scenario 2.2.

Process: set sibling S red, SL black, rotate right on S, then handle as Scenario 2.2.

Scenario 2.4 – sibling and both of its children are black. Recolor sibling red and move the problem up to the parent.

Process: set sibling S red, treat parent P as the new node to fix, and continue upward.

Scenario 3 – replacement node is black and is the right child of its parent (mirror of Scenario 2). It also contains four sub‑scenarios (3.1‑3.4) analogous to those above, using right‑side rotations and recolorings.

Each sub‑scenario follows the same pattern as its left‑side counterpart, swapping “left” and “right” in the operations.

Deletion and Balancing Code

/**
  * 查找节点 
  * @param key 节点key值
  */
search(key) {
  let node = this.root
  while (node) {
    if (key < node.key) {
      node = node.left
    } else if (key > node.key) {
      node = node.right
    } else {
      break
    }
  }
  return node
}

/**
 * 替换u节点，重置v节点
 * @param u 待删除节点
 * @param v 子节点
 */
const replace = function(u, v) {
  if (!u.parent) {
    // u是根节点，设置v为根节点
    this.root = v
  } else if (u === u.parent.left) {
    // 重置u的父节点的左节点
    u.parent.left = v
  } else {
    // 重置u的父节点的右节点
    u.parent.right = v
  }
  v.parent = u.parent
}

/**
  * 查找node节点的后继节点
  */
findSuccessor(node) {
  while (node.left) {
    node = node.left;
  }
  return node;
}

/**
 * 删除节点
 * @param key 删除节点key值
 */
delete(key) {
  const node = search(key)
  if (!node) {
    return
  }
  let fix
  let color = node.color
  if (!node.left) {
    //左节点为空值
    fix = node.right
    this.replace(node, node.right)
  } else if (!node.right) {
    //右节点为空值
    fix = node.left
    this.replace(node, node.left)
  } else {
    // 左右节点都不为空值
    const successor = this.findSuccessor(node.right)
    // 替换节点的颜色
    color = successor.color
    //后继节点只存在右节点或者两个nil子节点情况
    fix = successor.right
    //如果后继节点是父节点的非直接子节点
    if (successor.parent !== node) {
      this.replace(successor, successor.right)
      successor.right = node.right
      successor.right.parent = successor
    }
    this.replace(node, successor)
    successor.color = node.color
    successor.left = node.left
    successor.left.parent = successor
  }
  if (color === Color.BLACK) {
    this.balanceDeletion(fix)
  }
}

/**
 * 删除节点平衡修正
 * @param node 节点
 */
balanceDeletion(node) {
  while (node !== this.root && node.color === Color.BLACK) {
    if (node === node.parent.left) {
      //兄弟节点
      let sibling = node.parent.right;
      if (sibling.color === Color.RED) {
        // 场景2.1:兄弟节点是红色
        sibling.color = Color.BLACK;
        node.parent.color = Color.RED;
        this.rotateLeft(node.parent);
        sibling = node.parent.right;
      }
      if (sibling.left.color === Color.BLACK && sibling.right.color === Color.BLACK) {
        // 场景2.4: 兄弟节点两个子节点都是黑色
        sibling.color = Color.RED;
        node = node.parent;
        continue;
      } else if (sibling.left.color === Color.RED) {
        // 场景2.3: 兄弟节点的左子节点是黑色，转换到场景2.2.
        sibling.left.color = Color.BLACK;
        sibling.color = Color.RED;
        this.rotateRight(sibling)
        sibling = node.parent.right;
      }
      if (sibling.right.color === Color.RED) {
        //场景2.2：兄弟节点的右节点是红色
        sibling.color = node.parent.color;
        node.parent.color = Color.BLACK;
        sibling.right.color = Color.BLACK;
        this.rotateLeft(node.parent);
        node = this.root;
      }
    } else {
      //节点是父节点的左节点
      let sibling = node.parent.left;
      if (sibling.color === Color.RED) {
        // 场景 3.1：替换节点的兄弟节点是红色
        sibling.color = Color.BLACK;
        node.parent.color = Color.RED;
        this.rotateRight(node.parent);
        sibling = node.parent.left;
      }
      if (sibling.right.color === Color.BLACK && sibling.left.color === Color.BLACK) {
        //场景3.4：替换节点的两个子节点都是黑色
        sibling.color = Color.RED;
        node = node.parent;
        continue;
      } else if (sibling.right.color === Color.RED) {
        // 场景3.3:兄弟节点的右子节点是红色
        sibling.right.color = Color.BLACK;
        sibling.color = Color.RED;
        this.rotateLeft(sibling);
        sibling = node.parent.left;
      }
      if (sibling.left.color === Color.RED) {
        // 场景3.2：兄弟节点的左子节点是红色
        sibling.color = node.parent.color;
        node.parent.color = Color.BLACK;
        sibling.left.color = Color.BLACK;
        this.rotateRight(node.parent);
        node = this.root;
      }
    }
    node.color = Color.BLACK;
  }
}

Red‑Black Tree Applications

Red‑black trees are widely used in Java’s collection framework (HashMap, TreeMap, TreeSet), Nginx’s timer management, Linux virtual‑memory management, and C++ STL.

In the Linux kernel each process has a 4 GB linear virtual address space that is divided into regions. The kernel organizes these regions both as a linked list and as a red‑black tree sorted by address, enabling fast lookup of free regions and rapid retrieval of a specific region during page‑fault handling.

Summary

Deletion reduces to deleting the replacement node. If the replacement is red, removal does not affect balance; if it is black, additional steps such as borrowing from the sibling or recoloring are required.

Red‑black trees guarantee O(log N) worst‑case time for all operations, which is efficient for moderate data sizes that fit in memory. For very large data sets the tree’s depth can cause frequent disk I/O, reducing performance.

For further visual learning, see the “Data Structure Visualizations” site (https://www.cs.usfca.edu/~galles/visualization/Algorithms.html), which includes an interactive red‑black‑tree visualizer.