This article and the following article in this series implements one variant of the binary search tree that will keep trees in balance: 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 string
s. 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
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
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:
- 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. - 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:
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):
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 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
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
if isinstance(node_y, Leaf):
raise RuntimeError("Invalid left rotate")
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 isinstance(node_x.parent, Leaf):
self.root = node_y
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
if isinstance(node_y, Leaf):
raise RuntimeError("Invalid right rotate")
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 isinstance(node_x.parent, Leaf):
self.root = node_y
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:
- Every node is either red or black (cannot be broken).
- The root is black.
- Every leaf is black (cannot be broken since every new node's child point to the
Leaf
)
. - 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 (a.k.a. black height).
For the 5th 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:
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:
if fixing_node == fixing_node.parent.right:
fixing_node = fixing_node.parent
self._left_rotate(fixing_node)
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:
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:
if fixing_node == fixing_node.parent.left:
fixing_node = fixing_node.parent
self._right_rotate(fixing_node)
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.
- Walk through the tree from the root and compare the key with each node's key along the tree walk.
- If a key matches, we found the node.
- 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:
return current
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.
- Find the
node
to be deleted (deleting_node
). - Keep the
color
of the deleting_node
. - 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. - 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
. - 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
if isinstance(deleting_node.left, Leaf):
replacing_node = deleting_node.right
self._transplant(
deleting_node=deleting_node, replacing_node=replacing_node
)
if original_color == Color.BLACK:
if isinstance(replacing_node, Node):
self._delete_fixup(fixing_node=replacing_node)
elif isinstance(deleting_node.right, Leaf):
replacing_node = deleting_node.left
self._transplant(
deleting_node=deleting_node, replacing_node=replacing_node
)
if original_color == Color.BLACK:
self._delete_fixup(fixing_node=replacing_node)
else:
replacing_node = self.get_leftmost(deleting_node.right)
original_color = replacing_node.color
replacing_replacement = replacing_node.right
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
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:
- Every node is either
red
or black
. - The root is
black
. - Every leaf is
black
(cannot be broken since every new node's child point to the Leaf
). - 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 (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:
- Find the leftmost node (
replacing_node
) as the node to replace the deleting_node
from the right subtree of the deleting_node
. - Take the
replacing_node
out by performing the transplant
operation. - Set the
replacing_node
as the new root of the right subtree of the deleting_node
. - Perform the
transplant
operation to replace the deleting_node
with the subtree rooted of the replacing_node. - 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:
- The deleting node is
red
, and it has less than two children. - 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
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
if (sibling.left.color == Color.BLACK) and (
sibling.right.color == Color.BLACK
):
sibling.color = Color.RED
fixing_node = fixing_node.parent
else:
if sibling.right.color == Color.BLACK:
sibling.left.color = Color.BLACK
sibling.color = Color.RED
self._right_rotate(node_x=sibling)
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)
fixing_node = self.root
else:
sibling = fixing_node.parent.left
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
if (sibling.right.color == Color.BLACK) and (
sibling.left.color == Color.BLACK
):
sibling.color = Color.RED
fixing_node = fixing_node.parent
else:
if sibling.left.color == Color.BLACK:
sibling.right.color = Color.BLACK
sibling.color = Color.RED
self._left_rotate(node_x=sibling)
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)
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
def __init__(self) -> None:
self._rbt = red_black_tree.RBTree()
def __setitem__(self, key: Any, value: Any) -> None
self._rbt.insert(key=key, data=value)
def __getitem__(self, key: Any) -> Optional[Any]
node = self._rbt.search(key=key)
if node:
return node.data
return None
def __delitem__(self, key: Any) -> None
self._rbt.delete(key=key)
def __iter__(self) -> traversal.Pairs
return self._rbt.inorder_traverse()
if __name__ == "__main__":
contacts = Map()
contacts["Mark"] = "mark@email.com"
contacts["John"] = "john@email.com"
contacts["Luke"] = "luke@email.com"
print(contacts["Mark"])
del contacts["John"]
print(contacts["John"])
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
- 1st May, 2021: Initial version