Build the Forest in Python Series: Red-Black Tree

This article continues the Build the Forest in Python Series. From the Binary Search Tree: Analysis, we know the tree height is the critical factor of binary search tree's performance. This article and the following article will implement one variant of the binary search tree that will keep the trees in balance: Red-Black Tree.

Project Setup

Follow the same style and assumption as other articles in the Build the Forest in Series, the implementation assumes Python 3.9 or newer. This article adds two modules to our project: red_black_tree.py for the red-black tree implementation and test_red_black_tree.py for its unit tests. After adding these two files, our project layout becomes the following:

forest-python
├── forest
│   ├── __init__.py
│   ├── binary_trees
│   │   ├── __init__.py
│   │   ├── binary_search_tree.py
│   │   ├── double_threaded_binary_tree.py
│   │   ├── red_black_tree.py
│   │   ├── single_threaded_binary_trees.py
│   │   └── traversal.py
│   └── tree_exceptions.py
└── tests
    ├── __init__.py
    ├── conftest.py
    ├── test_binary_search_tree.py
    ├── test_double_threaded_binary_tree.py
    ├── test_red_black_tree.py
    ├── test_single_threaded_binary_trees.py
    └── test_traversal.py

(The complete code is available at forest-python.)

What is a Red-Black Tree?

A red-black tree variates the binary search tree with the self-balancing ability, and its node has one extra attribute: color, which can be either red or black. In addition to the binary-search-tree-property, a red-black tree also satisfies the following red-black-tree-property:

• Every node is either red or black.
• The root is black.
• Every leaf is black.
• If a node is red, then both of its children are black.
• All the path of each node from the node to leaves contains the same number of black nodes.

The red-black tree ensures that no path is twice longer than other paths by constraining the node colors on any simple path from a node to its descendent leaves. In other words, a red-black tree is approximately balanced.

A typical red-black tree looks like the picture below:

A leaf node of a tree data structure usually refers to a node that does not have any child. However, we use NIL to indicate leaves for the red-black tree, and they are always black. Besides, leaf nodes do not hold any data and mainly for maintaining the red-black-tree-property purpose.

We use black height to indicate the number of black nodes from a node to the leaves (exclude the node if the node is black). The following picture shows the black height for each node.

Next to each node is the black height for the node, and the leaf nodes (NIL) have black height zero.

Build Red-Black Tree

As we did in the previous trees, this section will walk through the implementation and discuss some thoughts behind the implementation choices.

Since all the leaves are NIL and the root's parent can also point to NIL, when we implement a red-black tree, we can define one NIL node and let the root's parent and all the nodes supported to point to a NIL node point to the NIL node. So, the red-black tree shown in the previous section becomes the following:

This way simplifies the implementation and saves space (i.e., only need one NIL node instance in the implementation).

For simplicity, the NIL node will be omitted in the rest of the article, so the red-black tree above will look like the following (but in the implementation, the NIL node must be there; otherwise, it will violate the red-black-tree-property).

Node

The red-black tree node is like the binary search tree node, but has one more attribute – color.

Since the color must be either red or black, we can define it as an enum class.

import enum

class Color(enum.Enum):
    RED = enum.auto()
    BLACK = enum.auto()

Why Use an Enum?

According to PEP-435, "An enumeration is a set of symbolic names bound to unique, constant values. Within an enumeration, the values can be compared by identity, and the enumeration itself can be iterated over." It makes sense that we define the color attribute as an enum class because its value (red or black) is constant, and we can identify the color attribute and compare it. Also, an enum class provides more robust type safety. If we don't use an enum, we could define the color attributes as constant strings. However, the type checking tools (e.g., mypy) will not be able to check if a value is the color attribute or a regular string. The other alternative is to define the color attribute as a regular class or a dataclass like this:

@dataclass
class Color:
    RED: str = "red"
    BLACK: str = "black"

This method still has some drawbacks. For example, the underline type is still a string. We can compare it with any strings. Besides, a class is mutable. In other words, we can modify the Color class at runtime that contradicts the color's definition. Therefore, using an enum to define the color attributes makes the most sense. It increases the type safety and simplifies the implementation.

Red-Black Tree Node

Like the other binary tree nodes, we utilize the dataclass to define the red-black tree node.

from dataclasses import dataclass

@dataclass
class Node:
    """Red-Black Tree non-leaf node definition."""

    key: Any
    data: Any
    left: Union["Node", Leaf] = Leaf()
    right: Union["Node", Leaf] = Leaf()
    parent: Union["Node", Leaf] = Leaf()
    color: Color = Color.RED

Leaf Node

As mentioned in the red-black tree definition, we use NIL to indicate the leaf node, and it can be defined as simple as the following:

from dataclasses import dataclass

@dataclass
class Leaf:
    color = Color.BLACK

Class Overview

Like other types of binary trees in the Build the Forest project, the red-black tree class has similar functionalities.

class RBTree:

    def __init__(self) -> None:
        self._NIL: Leaf = Leaf()
        self.root: Union[Node, Leaf] = self._NIL

    def __repr__(self) -> str:
        """Provie the tree representation to visualize its layout."""
        if (self.root is None) or (self.root == self._NIL):
            return "empty tree"
        return (
            f"{type(self)}, root={self.root}, "
            f"tree_height={str(self.get_height(self.root))}"
        )

    def search(self, key: Any) -> Optional[Node]:
        …

    def insert(self, key: Any, data: Any) -> None:
        …

    def delete(self, key: Any) -> None:
        …

    @staticmethod
    def get_leftmost(node: Node) -> Node:
        …

    @staticmethod
    def get_rightmost(node: Node) -> Node:
        …

    @staticmethod
    def get_successor(node: Node) -> Union[Node, Leaf]:
        …

    @staticmethod
    def get_predecessor(node: Node) -> Union[Node, Leaf]:
        …

    @staticmethod
    def get_height(node: Union[Leaf, Node]) -> int:
        …

    def inorder_traverse(self) -> traversal.Pairs:
        …

    def preorder_traverse(self) -> traversal.Pairs:
        …

    def postorder_traverse(self) -> traversal.Pairs:
        …

    def _transplant(
        self, deleting_node: Node, replacing_node: Union[Node, Leaf]
    ) -> None:
        …

    def _left_rotate(self, node_x: Node) -> None:
        …

    def _right_rotate(self, node_x: Node) -> None:
        …

    def _insert_fixup(self, fixing_node: Node) -> None:
        …

    def _delete_fixup(self, fixing_node: Union[Leaf, Node]) -> None:
        …

Note that besides the common methods of all the binary trees, the RBTree class has some additional methods. _left_rotate(), _right_rotate(), _insert_fixup() and _delete_fixup() are the helper functions to maintain the red-black-tree-property after insertion and deletion. Both insert and delete operations modify the tree; therefore, the operations may violate the red-black-tree-property. That's why we need these functions.

The leaf node is NIL, so the traversal routines (use None to determine if reach a leaf node) from Binary Tree Traversal do not work with the RBTree class (need to use Leaf to determine if reach a leaf node). Therefore, the RBTree class needs to provide its traversal routines.

Insert

Because the insert operation modifies the red-black tree, the result may violate the red-black-tree-property (This is also true for deletion).  To restore the red-black-tree-property, we need to change some nodes' color and also update the red-black tree formation. The method to update a binary tree's formation is called rotation. The technique of fixing the violated red-black-tree-property comes from Introduction to Algorithms, and the idea of the red-black tree insertion can be summarized as the following:

1. Insert the new node with the color red in the same way as the binary search tree insertion: find the proper location (i.e., the parent of the new node) to insert the new node by walking through the tree from the root and comparing the new node's key with each node's key along the way.
2. Fix the broken red-black-tree-property by rotations and coloring.

Since the new node is red, we can violate the red-black-tree-property – if a node is red, then both of its children are black, and we can fix the violation after the insertion.

We can implement the red-black tree insertion in a similar way to the normal binary search tree insertion.

def insert(self, key: Any, data: Any) -> None:
    # Color the new node as red.
    new_node = Node(key=key, data=data, color=Color.RED)
    parent: Union[Node, Leaf] = self._NIL
    current: Union[Node, Leaf] = self.root
    while isinstance(current, Node):  # Look for the insert location
        parent = current
        if new_node.key < current.key:
            current = current.left
        elif new_node.key > current.key:
            current = current.right
        else:
            raise tree_exceptions.DuplicateKeyError(key=new_node.key)
    new_node.parent = parent
    # If the parent is a Leaf, set the new node to be the root.
    if isinstance(parent, Leaf):
        new_node.color = Color.BLACK
        self.root = new_node
    else:
        if new_node.key < parent.key:
            parent.left = new_node
        else:
            parent.right = new_node

        # After the insertion, fix the broken red-black-tree-property.
        self._insert_fixup(new_node)

One difference from the binary search tree is that we use isinstance to check if a node is a normal Node or a Leaf instead of checking if it is None. That's because we have Leaf type for the leaf nodes and Node type for the regular nodes.

Once a new node is inserted into the red-black tree, we need to fix the broken red-black-tree-property. The following subsections will discuss using rotation and coloring to fix the broken red-black tree.

Rotations

The rotation operation is to change the red-black tree formation and also preserve its binary-search-properties. There are two types of rotations: left rotation and right rotation.

Left Rotation

The left rotation transfers the two nodes (x and y in the picture) from the top tree to the bottom tree of the picture and preserves its binary-search-tree-properties.

def _left_rotate(self, node_x: Node) -> None:
    node_y = node_x.right  # Set node y
    if isinstance(node_y, Leaf):  # Node y cannot be a Leaf
        raise RuntimeError("Invalid left rotate")

    # Turn node y's subtree into node x's subtree
    node_x.right = node_y.left
    if isinstance(node_y.left, Node):
        node_y.left.parent = node_x
    node_y.parent = node_x.parent

    # If node's parent is a Leaf, node y becomes the new root.
    if isinstance(node_x.parent, Leaf):
        self.root = node_y
    # Otherwise, update node x's parent.
    elif node_x == node_x.parent.left:
        node_x.parent.left = node_y
    else:
        node_x.parent.right = node_y

    node_y.left = node_x
    node_x.parent = node_y

Note that the node x's right child cannot be a Leaf (i.e., NIL); It makes no sense to rotate a Leaf.

Right Rotation

The right rotation is symmetric to the left rotation and can be implemented as the following:

def _right_rotate(self, node_x: Node) -> None:
    node_y = node_x.left  # Set node y
    if isinstance(node_y, Leaf):  # Node y cannot be a Leaf
        raise RuntimeError("Invalid right rotate")
    # Turn node y's subtree into node x's subtree
    node_x.left = node_y.right
    if isinstance(node_y.right, Node):
        node_y.right.parent = node_x
    node_y.parent = node_x.parent

    # If node's parent is a Leaf, node y becomes the new root.
    if isinstance(node_x.parent, Leaf):
        self.root = node_y
    # Otherwise, update node x's parent.
    elif node_x == node_x.parent.right:
        node_x.parent.right = node_y
    else:
        node_x.parent.left = node_y

    node_y.right = node_x
    node_x.parent = node_y

Fixup

To restore the red-black-tree-property, we need to know which red-black-properties could be broken after an insertion.

The red-black-tree-property:

1. Every node is either red or black (cannot be broken).
2. The root is black.
3. Every leaf is black (cannot be broken since every new node's child point to the Leaf).
4. If a node is red, then both of its children are black.
5. All the path of each node from the node to leaves contains the same number of black nodes (a.k.a. black height).

For the 5^th property, the black height is still the same. The new node (as the color red) replaces a Leaf (NIL), but its children are also Leaf (NIL). Therefore, the black height property holds after the insertion.

Thus, only property 2 and property 4 could be violated due to the color of a new node is red. If the new node's parent is also red, property 4 is broken. Regarding property 2, it could be violated if a new node is the root or the root becomes red while fixing property 4. And we can fix property two by coloring it black at the end of the fixup routine.

Regarding fixing property 4, we can break it down to six cases (two three-case symmetrically). The six cases are determined by the location and color of the new node's parent and the parent's sibling.

	New Node's Parent's Location	New Node's Parent's Sibling's Color	New Node's Location
Case 1	Left child	Red	Does not matter
Case 2	Left child	Black	Right child
Case 3	Left child	Black	Left child
Case 4	Right child	Red	Does not matter
Case 5	Right child	Black	Left child
Case 6	Right child	Black	Right child

Start from the new node (fixing_node).

Case 1

• Change the color of the fixing_node's parent and the parent's sibling to black.
• Change the color of the fixing_node's grandparent to red.
• Move the current location to the fixing_node's grandparent.

Note that the new node's location does not matter. The following picture shows cases 1. The new node (7) is the left child, and 2. The new node (18) is the right child.

Case 2

• Perform the left rotation on the fixing_node's parent (This operation transfer case 2 to case 3).

Case 3

• Change the color of the fixing_node's parent to black
• Change the color of the fixing_node's grandparent to red
• Perform the right rotation on the fixing_node's grandparent

Case 4 (the same as case 1)

• Change the color of the fixing_node's parent and the parent's sibling to black
• Change the color of the fixing_node's grandparent to red
• Move the current location to the fixing_node's grandparent

Case 5

• Perform the right rotation on the fixing_node's parent (This operation transfers case 5 to case 6).

Case 6

• Change the color of the fixing_node's parent to black.
• Change the color of the fixing_node's grandparent to red.

While fixing the broken red-black-tree-property for the fixing_node, the fixing process may cause the fixing_node's parent or grandparent (depends on the case) to violate the red-black-tree-property. When that happens, the fixing_node's parent (or grandparent) becomes the new fixing_node. Then we can solve it according to the six cases. Repeat this step until we reach the root. If the root becomes red (property 2 violated) after the fix operations, we can fix it by coloring the root black.

The picture below demonstrates the complete insertion operation to build a red-black tree.

The implementation of the insertion fixup is shown below:

def _insert_fixup(self, fixing_node: Node) -> None:
    while fixing_node.parent.color == Color.RED:
        if fixing_node.parent == fixing_node.parent.parent.left:
            parent_sibling = fixing_node.parent.parent.right
            if parent_sibling.color == Color.RED:  # Case 1
                fixing_node.parent.color = Color.BLACK
                parent_sibling.color = Color.BLACK
                fixing_node.parent.parent.color = Color.RED
                fixing_node = fixing_node.parent.parent
            else:
                # Case 2
                if fixing_node == fixing_node.parent.right:
                    fixing_node = fixing_node.parent
                    self._left_rotate(fixing_node)
                # Case 3
                fixing_node.parent.color = Color.BLACK
                fixing_node.parent.parent.color = Color.RED
                self._right_rotate(fixing_node.parent.parent)
        else:
            parent_sibling = fixing_node.parent.parent.left
            if parent_sibling.color == Color.RED:  # Case 4
                fixing_node.parent.color = Color.BLACK
                parent_sibling.color = Color.BLACK
                fixing_node.parent.parent.color = Color.RED
                fixing_node = fixing_node.parent.parent
            else:
                # Case 5
                if fixing_node == fixing_node.parent.left:
                    fixing_node = fixing_node.parent
                    self._right_rotate(fixing_node)
                # Case 6
                fixing_node.parent.color = Color.BLACK
                fixing_node.parent.parent.color = Color.RED
                self._left_rotate(fixing_node.parent.parent)

    self.root.color = Color.BLACK

Search

The search operation is similar to the binary search tree, but we use Leaf (NIL) to determine if we reach the leaf.

1. Walk through the tree from the root and compare the key with each node's key along the tree walk.
2. If a key matches, we found the node.
3. If we reach the Leaf, the node does not exist in the tree.

The search is implemented similarly to the binary search tree search function.

def search(self, key: Any) -> Optional[Node]:
    current = self.root

    while isinstance(current, Node):
        if key < current.key:
            current = current.left
        elif key > current.key:
            current = current.right
        else:  # Key found
            return current
    # If the tree is empty (i.e., self.root == Leaf()), still return None.
    return None

Delete

Similar to the red-black tree insertion, the deletion modifies the red-black tree, and the result may violate the red-black-tree-property. Therefore, we need to restore the red-black-tree-property after we delete a node.

The basic idea of the red-black tree deletion is similar to the normal binary search tree. We have a transplant method to replace the subtree rooted at the deleting_node with the subtree rooted at the replacing_node. We also have three basic cases of deletion: no child, only one child, and two children. And, finally, we need to fix the broken red-black-tree-property.

Transplant

The transplant method is modified from the Binary Search Tree, so it works appropriately for a red-black tree. The modification is that we use isinstance to check if a node is a normal Node or a Leaf instead of checking if it is None.

def _transplant(
    self, deleting_node: Node, replacing_node: Union[Node, Leaf]
) -> None:
    if isinstance(deleting_node.parent, Leaf):
        self.root = replacing_node
    elif deleting_node == deleting_node.parent.left:
        deleting_node.parent.left = replacing_node
    else:
        deleting_node.parent.right = replacing_node

    if isinstance(replacing_node, Node):
        replacing_node.parent = deleting_node.parent

The overall delete procedure is like a normal binary search tree with some modifications.

1. Find the node to be deleted (deleting_node).
2. Keep the color of the deleting_node.
3. If the deleting_node has no or only one child, use the transplant method to replace the deleting_node with either NIL or the only one child.
4. If the deleting_node has two children, find the deleting_node's successor as the replacing_node. Keep the color of the replacing_node. Use the transplant method to take out the replacing_node and keep tracing the node to replace the replacing_node, either NIL or the replacing_node's original right child. Use the transplant method to replace the deleting_node with the replacing_node. Color the replacing_node to the color of the deleting_node.
5. Fix the broken red-black-tree-property by changing colors and performing rotations.

Based on the delete procedure above, we can implement the delete method as the following:

def delete(self, key: Any) -> None:
    if (deleting_node := self.search(key=key)) and (
        not isinstance(deleting_node, Leaf)
    ):
        original_color = deleting_node.color

        # Case 1: no children or Case 2a: only one right child
        if isinstance(deleting_node.left, Leaf):
            replacing_node = deleting_node.right
            self._transplant(
                deleting_node=deleting_node, replacing_node=replacing_node
            )
            # Fixup
            if original_color == Color.BLACK:
                if isinstance(replacing_node, Node):
                    self._delete_fixup(fixing_node=replacing_node)

        # Case 2b: only one left child
        elif isinstance(deleting_node.right, Leaf):
            replacing_node = deleting_node.left
            self._transplant(
                deleting_node=deleting_node, replacing_node=replacing_node
            )
            # Fixup
            if original_color == Color.BLACK:
                self._delete_fixup(fixing_node=replacing_node)

        # Case 3: two children
        else:
            replacing_node = self.get_leftmost(deleting_node.right)
            original_color = replacing_node.color
            replacing_replacement = replacing_node.right
            # The replacing node is not the direct child of the deleting node
            if replacing_node.parent != deleting_node:
                self._transplant(replacing_node, replacing_node.right)
                replacing_node.right = deleting_node.right
                replacing_node.right.parent = replacing_node

            self._transplant(deleting_node, replacing_node)
            replacing_node.left = deleting_node.left
            replacing_node.left.parent = replacing_node
            replacing_node.color = deleting_node.color
            # Fixup
            if original_color == Color.BLACK:
                if isinstance(replacing_replacement, Node):
                    self._delete_fixup(fixing_node=replacing_replacement)

Something to mention is that:

• We keep the original color (original_color) of the deleting_node.
• If the node to be deleted has two children, we update the original_color to the node's color (replacing_node).
• At the end of each case, if the original_color is black, it means some red-black-tree-property is broken, and we need to fix them.

Before restoring the violated red-black-tree-property, we need to know which red-black-properties could be broken during the delete routine.

The red-black-tree-property:

1. Every node is either red or black.
2. The root is black.
3. Every leaf is black (cannot be broken since every new node's child point to the Leaf).
4. If a node is red, then both of its children are black.
5. All the path of each node from the node to leaves contains the same number of black nodes (a.k.a. black height).

Case 1: The node to be deleted has no child

If the color of the deleting_node is red, no red-black-tree-property is broken. If the deleting_node's color is black, property 5 is violated.

Case 2: The node to be deleted has only one child

Due to the red-black-tree-property, it is impossible that a red node has only one black child. It is also not possible that a black node has only one black child, either. Therefore, if the deleting_node has only one child, its color must be black, and the color of the replacing_node must be red.

According to the picture above, if the deleting_node is black, property 4 and property 5 can be broken as well as property 2 if the deleting_node is the root.

Case 3: The node to be deleted has two children

In this case, we do the following steps:

1. Find the leftmost node (replacing_node) as the node to replace the deleting_node from the right subtree of the deleting_node.
2. Take the replacing_node out by performing the transplant operation.
3. Set the replacing_node as the new root of the right subtree of the deleting_node.
4. Perform the transplant operation to replace the deleting_node with the subtree rooted of the replacing_node.
5. Color the replacing_node to the color of the deleting_node

After step 5, the color of the replacing_node is the same as the deleting_node, so no red-black-tree-property is broken. The only step that could break the red-black-tree-property is step 2. When we perform the transplant operation on the replacing_node, it ends up being either case 1 or case 2.

The following pictures demonstrate how deleting a node with two children may or may not violate the red-black-tree-property.

The case that the replacing_node is the direct child of the deleting_node.

The case that the replacing_node is black and not the direct child of the deleting_node.

The case that the replacing_node is red and not the direct child of the deleting_node.

Therefore, we can summarize the situation that we need to fix the broken red-black-tree-property:

No Child	If the node to be deleted is black
Only One Child	If the node to be deleted is black
Two Children	If the node (leftmost from the right subtree of the node to be deleted) to replace the deleting node is black

The summary also implies that the red-black-tree-property still holds in the following situations:

1. The deleting node is red, and it has less than two children.
2. The deleting node has two children, and the replacing node is red.

The reasons are:

• No black height changes. Property 5 holds.
• For the first situation, the node to be removed cannot be red if it's the root; for the second situation, the leftmost node cannot be the root. Property 2 holds.
• If the node (either the first or second situation) is red, its parent and child or children cannot be red. So, after removing it or moving it, consecutive red nodes cannot happen. Property 4 holds.

Fixup

To fix the broken red-black-tree-property, we use the idea from Introduction to Algorithms, and the fixup procedure first fixes the property 5 (both black heights of each node from the node to leaves are the same) by introducing the concept of double-black and red-and-black. For the black heights, double-black and red-and-black contribute either 2 or 1, respectively. And we use the following icons to indicate double-black and red-and-black nodes.

When we use the transplant function to replace one node with another node, instead of replacing the node, we keep both node's color, and we use double-black and red-and-black to indicate its color. Therefore, if the node to be deleted has less than two children, after the transplant function, the color of the replacing node becomes either double-black or red-and-black. If the node to be deleted has two children, the color of the leftmost node's replacement becomes either double-black or red-and-black when we use the transplant function to take out the leftmost node of the subtree rooted by the node to be deleted. For the sake of simplicity, we use fixing_node to indicate the node has color either double-black or red-and-black. Note that we don't really color the fixing_node as double-black or red-and-black in the code implementation. We just pretend the fixing_node had one extra black or red.

By doing so, the invalid black heights are solved, and the potential broken cases become the following:

The node to be deleted has no child.

The node to be deleted has only one child.

The node to be deleted has two children.

If the node to be deleted has two children, the node that takes the leftmost node's position breaks the red-black-tree-property.

The replacing_node is the direct child of the deleting_node.

The replacing_node is not the direct child of the deleting_node.

Because the color of the fixing_node is neither red nor black, property 1 is also broken. Now, we need to restore red-black-tree-property 1, 2, and 4.

If the color of the fixing_node is red-and-black, we can fix it by coloring it black. All broken red-black-tree-property are restored.

The remaining broken situation is double-black. The fixup procedure for that can be broken down into four symmetric cases.

The cases are identified by the location of the fixing_node, the color of the fixing_node's sibling, and the color of the sibling's children.

	fixing_node	Sibling's color	Sibling's left child's color	Sibling's right child's color
Case 1	Left child	Red	Does not matter	Does not matter
Case 2	Left child	Black	Black	Black
Case 3	Left child	Black	Red	Black
Case 4	Left child	Black	Black	Red
Case 5	Right child	Red	Does not matter	Does not matter
Case 6	Right child	Black	Black	Black
Case 7	Right child	Black	Black	Red
Case 8	Right child	Black	Red	Black

Start from the fixing_node.

Case 1

• Change the color of the sibling node to black.
• Change the color of the fixing_node's parent to red.
• Perform the left rotation on the fixing_node's parent.
• Update the sibling node (the sibling changes due to the left rotation).
• After the operations above, case 1 transfers to case 2, case 3, or case 4.

Case 2

• Change the sibling's color to red
• Move the fixing_node up, i.e., the new fixing_node becomes the original fixing_node's parent

Case 3

• Change the color of the sibling's left child to black.
• Change the sibling's color to red.
• Perform the right rotation on the sibling node.
• After the operations above, case 3 transfers to case 4.

Case 4

• Change the color of the sibling's color to be the same as the fixing_node's parent
• Change the color of the fixing_node's parent to black
• Change the color of the sibling node's right child to black
• Perform the left rotation on the fixing_nopde's parent
• After the operations above, all violated red-black-tree-property restored.

Case 5

• Change the color of the sibling node to black
• Change the color of the fixing_node's parent to red
• Perform the right rotation on the fixing_node's parent
• Update the sibling node (the sibling changes due to the right rotation)
• After the operations above, case 1 transfers to case 6, case 7, or case 8

Case 6

• Change the sibling's color to red
• Move the fixing_node up, i.e., the new fixing_node becomes the original fixing_node's parent

Case 7

• Change the color of the sibling's right child to black
• Change the sibling's color to red
• Perform the left rotation on the sibling node
• After the operations above, case 7 transfers to case 8

Case 8

• Change the color of the sibling's color to be the same as the fixing_node's parent
• Change the color of the fixing_node's parent to black
• Change the color of the sibling node's left child to black
• Perform the right rotation on the fixing_nopde's parent
• After the operations above, all violated red-black-tree-property restored.

The following implementation summarizes the fixup procedures discussed above.

def _delete_fixup(self, fixing_node: Union[Leaf, Node]) -> None:
    while (fixing_node is not self.root) and (fixing_node.color == Color.BLACK):
        if fixing_node == fixing_node.parent.left:
            sibling = fixing_node.parent.right

            # Case 1: the sibling is red.
            if sibling.color == Color.RED:
                sibling.color == Color.BLACK
                fixing_node.parent.color = Color.RED
                self._left_rotate(fixing_node.parent)
                sibling = fixing_node.parent.right

            # Case 2: the sibling is black and its children are black.
            if (sibling.left.color == Color.BLACK) and (
                sibling.right.color == Color.BLACK
            ):
                sibling.color = Color.RED
                fixing_node = fixing_node.parent  # new fixing node

            # Cases 3 and 4: the sibling is black and one of
            # its child is red and the other is black.
            else:
                # Case 3: the sibling is black and its left child is red.
                if sibling.right.color == Color.BLACK:
                    sibling.left.color = Color.BLACK
                    sibling.color = Color.RED
                    self._right_rotate(node_x=sibling)

                # Case 4: the sibling is black and its right child is red.
                sibling.color = fixing_node.parent.color
                fixing_node.parent.color = Color.BLACK
                sibling.right.color = Color.BLACK
                self._left_rotate(node_x=fixing_node.parent)
                # Once we are here, all the violation has been fixed, so
                # move to the root to terminate the loop.
                fixing_node = self.root
        else:
            sibling = fixing_node.parent.left

            # Case 5: the sibling is red.
            if sibling.color == Color.RED:
                sibling.color == Color.BLACK
                fixing_node.parent.color = Color.RED
                self._right_rotate(node_x=fixing_node.parent)
                sibling = fixing_node.parent.left

            # Case 6: the sibling is black and its children are black.
            if (sibling.right.color == Color.BLACK) and (
                sibling.left.color == Color.BLACK
            ):
                sibling.color = Color.RED
                fixing_node = fixing_node.parent
            else:
                # Case 7: the sibling is black and its right child is red.
                if sibling.left.color == Color.BLACK:
                    sibling.right.color = Color.BLACK
                    sibling.color = Color.RED
                    self._left_rotate(node_x=sibling)
                # Case 8: the sibling is black and its left child is red.
                sibling.color = fixing_node.parent.color
                fixing_node.parent.color = Color.BLACK
                sibling.left.color = Color.BLACK
                self._right_rotate(node_x=fixing_node.parent)
                # Once we are here, all the violation has been fixed, so
                # move to the root to terminate the loop.
                fixing_node = self.root

    fixing_node.color = Color.BLACK

Auxiliary Functions

In addition to the core functions (i.e., insert, search, and delete), the red-black tree could have other useful functions, such as get the leftmost node, get the successor of a node, and get the height of a tree, whose implementations are similar to the binary search tree auxiliary functions but with some modifications.

Get the Height

To calculate the tree height of a red-black tree, we can recursively increment the height by one for each child's height as we did in the binary search tree. If a node has two children, we use the max function to get the bigger height from the children and increase the highest by one. The main difference is that we use isinstance to check if a node has a leaf or not.

@staticmethod
def get_height(node: Union[Leaf, Node]) -> int:
    if isinstance(node, Node):
        if isinstance(node.left, Node) and isinstance(node.right, Node):
            return (
                max(RBTree.get_height(node.left), RBTree.get_height(node.right)) + 1
            )

        if isinstance(node.left, Node):
            return RBTree.get_height(node=node.left) + 1

        if isinstance(node.right, Node):
            return RBTree.get_height(node=node.right) + 1

    return 0

Get the Leftmost and Rightmost Nodes

The red-black tree does the same thing as the binary search tree to get the rightmost node of the given (sub)tree and the leftmost node of the given (sub)tree. Once again, we use isinstance to check if a node is a regular red-black tree node or a leaf.

Leftmost

@staticmethod
def get_leftmost(node: Node) -> Node:
    current_node = node
    while isinstance(current_node.left, Node):
        current_node = current_node.left
    return current_node

Rightmost

@staticmethod
def get_rightmost(node: Node) -> Node:
    current_node = node
    while isinstance(current_node.right, Node):
        current_node = current_node.right
    return current_node

Predecessor and Successor

The red-black tree does the same thing as the binary search tree to get a node's predecessor and successor.

Predecessor

@staticmethod
def get_predecessor(node: Node) -> Union[Node, Leaf]:
    if isinstance(node.left, Node):
        return RBTree.get_rightmost(node=node.left)
    parent = node.parent
    while isinstance(parent, Node) and node == parent.left:
        node = parent
        parent = parent.parent
    return node.parent

Successor

@staticmethod
def get_successor(node: Node) -> Union[Node, Leaf]:
    if isinstance(node.right, Node):
        return RBTree.get_leftmost(node=node.right)
    parent = node.parent
    while isinstance(parent, Node) and node == parent.right:
        node = parent
        parent = parent.parent
    return parent

Traversals

Because of the leaf nodes, we are not able to use the traversal functions we implemented in Binary Tree Traversal. However, the concept of traversal is the same. We only need a simple modification: use isinstance to check if a node is a regular red-black tree node or a leaf.

In-order Traversal

def inorder_traverse(self) -> traversal.Pairs:
    return self._inorder_traverse(node=self.root)

def _inorder_traverse(self, node: Union[Node, Leaf]) -> traversal.Pairs:
    if isinstance(node, Node):
        yield from self._inorder_traverse(node.left)
        yield (node.key, node.data)
        yield from self._inorder_traverse(node.right)

Pre-order Traversal

def preorder_traverse(self) -> traversal.Pairs:
    return self._preorder_traverse(node=self.root)

def _preorder_traverse(self, node: Union[Node, Leaf]) -> traversal.Pairs:
    if isinstance(node, Node):
        yield (node.key, node.data)
        yield from self._preorder_traverse(node.left)
        yield from self._preorder_traverse(node.right)

Post-order Traversal

def postorder_traverse(self) -> traversal.Pairs:
    return self._postorder_traverse(node=self.root)

def _postorder_traverse(self, node: Union[Node, Leaf]) -> traversal.Pairs:
    if isinstance(node, Node):
        yield from self._postorder_traverse(node.left)
        yield from self._postorder_traverse(node.right)
        yield (node.key, node.data)

Note that the return type (traversal.Pairs) is defined at traversal.py from Binary Tree Traversal.

Test

As always, we should have unit tests for our code as much as possible. Here, we use the basic_tree function in conftest.py that we created in Build the Binary Search Tree to test our red-black tree. Check test_red_black_tree.py for the complete unit test.

Analysis

As we discussed at Binary Search Tree: Analysis, we know the operation runtime of the binary search tree is based on the tree height. A red-black tree is a self-balancing binary search tree and has height at most 2 * lg (n+1) = O(lg n), where n is the number of nodes. (The proof can refer to Introduction to Algorithms Lemma 13.1). Therefore, the time complexity of a red-black tree can be summarized in the table below:

Examples

Due to the self-balancing ability, Red-Black Tree is wildly used in software programs, including implement other data structures. For example, the C++ STL map is implemented as a red-black tree. This section uses the red-black tree we implement here to implement a key-value Map.

from typing import Any, Optional

from forest.binary_trees import red_black_tree
from forest.binary_trees import traversal

class Map:
    """Key-value Map implemented using Red-Black Tree."""

    def __init__(self) -> None:
        self._rbt = red_black_tree.RBTree()

    def __setitem__(self, key: Any, value: Any) -> None:
        """Insert (key, value) item into the map."""
        self._rbt.insert(key=key, data=value)

    def __getitem__(self, key: Any) -> Optional[Any]:
        """Get the data by the given key."""
        node = self._rbt.search(key=key)
        if node:
            return node.data
        return None

    def __delitem__(self, key: Any) -> None:
        """Remove a (key, value) pair from the map."""
        self._rbt.delete(key=key)

    def __iter__(self) -> traversal.Pairs:
        """Iterate the data in the map."""
        return self._rbt.inorder_traverse()

if __name__ == "__main__":

    # Initialize the Map instance.
    contacts = Map()

    # Add some items.
    contacts["Mark"] = "mark@email.com"
    contacts["John"] = "john@email.com"
    contacts["Luke"] = "luke@email.com"

    # Retrieve an email
    print(contacts["Mark"])

    # Delete one item.
    del contacts["John"]

    # Check the deleted item.
    print(contacts["John"])  # This will print None

    # Iterate the items.
    for contact in contacts:
        print(contact)

(The complete example is available at rbt_map.py.)

Summary

Although it is complicated to maintain the red-black-tree-property, its self-balancing ability makes the Red-Black Tree having better performance than the binary search tree. In many cases, keep a tree balanced is critical, so the red-black tree's complication is worthwhile. In the following article, we will implement another famous self-balancing tree, AVL Tree.

History

• 1^st May, 2021: Initial version