A redblack tree is a selfbalancing binary search tree where each node has an extra bit representing color, either red or black. By constraining how nodes are colored during insertions and deletions, redblack trees ensure the tree remains approximately balanced during all operations, allowing for O(log n) search, insert, and delete.
Redblack trees are important data structures widely used in languages like Java and C++. Here we will examine how to implement insertion, deletion, and balancing logic to construct a fully functional redblack tree in Python.
Table of Contents
Open Table of Contents
Overview of RedBlack Trees
Redblack trees are binary search trees that add the extra constraint of node coloring in order to ensure the tree remains balanced during operations. Here are some key properties of redblack trees:
 Every node is colored red or black.
 The root node is always black.
 All leaf nodes are black with NULL child pointers.
 Both children of every red node are black.
 Every path from a node to any of its descendant leaf nodes contains the same number of black nodes.
By constraining coloring during insertions and deletions, redblack trees ensure the maximum height of the tree (number of black nodes on any roottoleaf path) does not exceed 2log(n+1) where n is the number of nodes. This guarantees O(log n) worstcase performance for search, insert, and delete operations.
The balance of redblack trees comes from how coloring changes during insertions and deletions. Specific balancing rules are followed that require certain coloring operations and tree rotations to retain the blackheight property of the tree.
RedBlack Tree Node Implementation
We will implement a redblack tree node class that extends the typical binary search tree node structure by adding a color attribute:
class RBNode:
def __init__(self, value, color='red'):
self.value = value
self.color = color
self.left = None
self.right = None
self.parent = None
Each node contains the standard value
, left
, and right
attributes to represent the data value and links to children nodes.
The color
attribute tracks if the node is ‘red’ or ‘black’. New nodes added during insertion are colored red by default.
The parent
attribute is helpful for tracking parent nodes when doing rotations and color changes.
Implementing RedBlack Tree Insertion
We will first examine the algorithm for inserting new nodes into the redblack tree. This must follow specific rules to ensure the tree remains balanced.
The steps for insertion are:
 Perform standard BST insertion, adding the node as a red leaf node.
 Fix redblack properties if needed through color changes and rotations.
Standard BST Insertion
Insertion begins by adding the new node with a red color as a standard BST insertion:
def insert(self, value):
# Regular BST insert
new_node = RBNode(value)
if self.root is None:
# Handle empty tree
self.root = new_node
else:
curr_node = self.root
while True:
if value < curr_node.value:
if curr_node.left is None:
curr_node.left = new_node
new_node.parent = curr_node
break
else:
curr_node = curr_node.left
else:
if curr_node.right is None:
curr_node.right = new_node
new_node.parent = curr_node
break
else:
curr_node = curr_node.right
This follows the standard recursive BST insertion logic, descending the tree and adding the new node with the given value once we reach a leaf node.
The new node is initially added with a red color.
Fixing RedBlack Properties
After regular BST insertion, we may have violated redblack tree properties. There are two main redblack tree invariants that must be maintained after insertion:
 No red node can have a red child (so red nodes must have black children).
 All paths from a node to descendant leaves must contain the same number of black nodes.
There are specific cases that can occur after adding a red child that violate these invariants:
Case 1: If the parent is black, tree is still valid.
If the parent of the new red node is black, both properties are satisfied. Nothing needs to be done since rules are not violated.
Case 2: If parent is red, we have a red violation.
If the parent is red, this means there is now a red node with a red child, violating property 1. To fix this, there are subcases:

Case 2a: If parent’s sibling is red  Recolor the parent and sibling to black, and grandparent to red. This maintains a valid tree, but grandparent may now be red, so recursively check it.

Case 2b: Parent’s sibling is black  Perform rotations to restructure the tree so the red violation moves up to fix.
The full fixing logic including handling these cases is shown below:
def insert_fix(self, new_node):
# Fix redblack properties if needed
parent = new_node.parent
# Case 1: If parent is black, tree is still valid
if parent is None or parent.color == 'black':
return
# Case 2: If parent is red, have to handle violations
else:
if new_node.uncle() is not None and new_node.uncle().color == 'red':
# Case 2a: Uncle is red, recolor parent, grandparent, uncle
new_node.parent.color = 'black'
new_node.uncle().color = 'black'
new_node.grandparent().color = 'red'
# Recurse up the tree
self.insert_fix(new_node.grandparent())
else:
# Case 2b: Uncle is black (or null), restructure tree
grandparent = new_node.grandparent()
# New node is left child of parent, parent is left of grandparent
if new_node == new_node.parent.left:
if new_node.parent == grandparent.left:
# Leftleft case
self.rotate_right(grandparent)
new_node.parent.color = 'black'
grandparent.color = 'red'
else:
# Leftright case
self.rotate_left(new_node.parent)
self.rotate_right(grandparent)
new_node.color = 'black'
grandparent.color = 'red'
# Mirror cases: parent/new node on right
else:
if new_node.parent == grandparent.right:
# Rightright case
self.rotate_left(grandparent)
new_node.parent.color = 'black'
grandparent.color = 'red'
else:
# Rightleft case
self.rotate_right(new_node.parent)
self.rotate_left(grandparent)
new_node.color = 'black'
grandparent.color = 'red'
This covers all cases that can occur after adding a red child node, ensuring redblack properties are restored through rotations and recoloring.
The full insert method handles both standard insertion and fixing:
def insert(self, value):
# Regular BST insert
new_node = RBNode(value)
# Code for standard insertion...
# Fix redblack properties
self.insert_fix(new_node)
Rotations for Balancing
The insertion fixing logic requires left and right rotations to restructure the tree in certain cases. These operations change the position of nodes to move the red violation upward while maintaining the BST ordering, similar to AVL tree rotations.
Here is an implementation of left and right rotations on a given node:
def rotate_left(self, node):
right_child = node.right
node.right = right_child.left
if right_child.left is not None:
right_child.left.parent = node
right_child.parent = node.parent
if node.parent is None:
# Node is root
self.root = right_child
elif node == node.parent.left:
node.parent.left = right_child
else:
node.parent.right = right_child
right_child.left = node
node.parent = right_child
def rotate_right(self, node):
# Mirror of rotate left
left_child = node.left
node.left = left_child.right
if left_child.right is not None:
left_child.right.parent = node
left_child.parent = node.parent
if node.parent is None:
self.root = left_child
elif node == node.parent.right:
node.parent.right = left_child
else:
node.parent.left = left_child
left_child.right = node
node.parent = left_child
These rotations restructure the nodes such that the rotated node becomes a child while its child becomes the new parent. This moves a red violation upward in the tree.
Deletion in a RedBlack Tree
Implementing deletion in a redblack tree also requires maintaining the coloring invariants after removing nodes.
The steps for deletion are:
 Perform standard BST deletion logic of removing the node and restructuring children.
 Fix any redblack violations through rotations and recoloring.
Standard BST Deletion
We first implement the standard BST node removal process:
def delete(self, value):
node_to_remove = self.search(value)
if node_to_remove is None:
# Value not found, no deletion needed
return
if node_to_remove.left is None:
self._replace_node(node_to_remove, node_to_remove.right)
elif node_to_remove.right is None:
self._replace_node(node_to_remove, node_to_remove.left)
else:
# Node has two children
# Find successor (leftmost of right subtree)
successor = self._find_min(node_to_remove.right)
successor_value = successor.value
self._replace_node(successor, successor.right)
node_to_remove.value = successor_value
# Fix redblack properties if needed
self.delete_fix(node_to_remove)
This follows the same logic as a standard BST deletion. If the node is a leaf, it can simply be removed. If it has one child, that child replaces it. If it has two children, we find its successor in the right subtree and swap their values before deleting the successor leaf node instead.
After removal, we check if redblack properties were violated and call fixup logic.
RedBlack Tree Fixing After Deletion
Similar to insertion, a deletion can break the redblack tree invariants. There are two main cases:
Case 1: Deleted node was black
If the deleted node was black, removing it caused blackheights of paths to diverge, since other paths did not have their black node count reduced.
To balance this, we check the color of the deleted node’s child. If it is red, recolor it black to maintain black heights. If it is black, more complex fixes are needed:
 Case 1a: Red sibling  Rotate to move the red up to parent level. This converts it to one of the other cases.
 Case 1b: Black sibling with black children  Recolor sibling red and propagate the double black up the tree.
 Case 1c: Black sibling with at least 1 red child  Recolor to balance black counts and preserve properties.
Case 2: Deleted node was red
If the deleted node was red, since red nodes do not add to the black height of paths we know heights remain valid.
Here is the full deletion fixup logic:
def delete_fix(self, x):
# Start fixes from parent since x is gone
x_parent = x.parent
if x.color == 'red':
# Case 2: If x was red, tree is still valid
return
if x_parent is None:
# Case 1: x was black, but was root
# Set new root to black
self.root.color = 'black'
return
# Case 1: x was black
if x.sibling().color == 'red':
# Case 1a: Sibling is red
x_parent.color = 'red'
x.sibling().color = 'black'
if x == x_parent.left:
self.rotate_left(x_parent)
else:
self.rotate_right(x_parent)
# Fix double black at x_parent
self.delete_fix(x_parent)
def delete_fix(self, x):
if x.color == 'red':
# Color flip
x.color = 'black'
return
if x.parent is None:
# Reached root, all blackheights fixed
return
if x.sibling().color == 'black':
# Case 1b and 1c
if (x.sibling().left is not None and x.sibling().left.color == 'red') or (x.sibling().right is not None and x.sibling().right.color == 'red'):
# Case 1c: At least 1 red child
if x.sibling().left is not None and x.sibling().left.color == 'red':
if x == x.parent.left:
self.rotate_right(x.sibling())
x.sibling().color = x.parent.color
x.parent.color = 'black'
else:
x.sibling().left.color = x.parent.color
x.parent.color = 'black'
self.rotate_right(x.sibling())
self.rotate_left(x.parent)
else:
if x == x.parent.left:
x.sibling().right.color = x.parent.color
x.parent.color = 'black'
self.rotate_left(x.sibling())
self.rotate_right(x.parent)
else:
self.rotate_left(x.sibling())
x.sibling().color = x.parent.color
x.parent.color = 'black'
else:
# Case 1b: All black children
x.sibling().color = 'red'
if x.parent.color == 'black':
self.delete_fix(x.parent)
else:
x.parent.color = 'black'
# Pass double black node up tree
self.delete_fix(x.parent)
This comprehensive fixing logic handles all cases after deletion to restore redblack properties. The tree remains balanced after any insertion or deletion.
Full Deletion Method
Combining the standard deletion and fixing logic, the full delete method is:
def delete(self, value):
# Standard deletion
node_to_remove = self.search(value)
# Delete node cases
# Fix redblack properties
self.delete_fix(node_to_remove)
Complete RedBlack Tree in Python
Putting everything together, here is an implementation of a complete functional redblack tree in Python:
import sys
class RBNode:
# RedBlack Tree Node class
def __init__(self, value, color='red'):
...
# Required helper methods and properties
def grandparent(self): ...
def sibling(self): ...
def uncle(self): ...
class RedBlackTree:
def __init__(self):
self.root = None
def search(self, value):
# Search logic
def insert(self, value):
# Regular insertion
new_node = RBNode(value)
# Insert fixing
self.insert_fix(new_node)
def insert_fix(self, new_node):
# Full insert fix logic
def delete(self, value):
# Standard deletion
node_to_remove = self.search(value)
# Delete node cases
# Fix redblack properties
self.delete_fix(node_to_remove)
def delete_fix(self, x):
# Full delete fix logic
# Rotation methods
def rotate_left(self, node):
...
def rotate_right(self, node):
...
This provides a full implementation of a redblack tree data structure in Python. The key additions to a standard BST are the color tracking, the insertion fix and deletion fix logic, and the left/right rotations used to rebalance during insertions and deletions.
Applications of RedBlack Trees
Redblack trees are used extensively in various systems and libraries where balanced search trees are required. Some example applications include:

Implementing Map/Set data structures  In languages like C++ and Java, the
std::map
andHashSet
classes use redblack trees internally for sorting keys and providing O(log n) operations. 
Compiler symbol tables  To store identifiers in programming languages for quick lookup time during compilation.

Networking and routing algorithms  To store routing table info while allowing fast route lookups and updates.

Scheduling algorithms  The Linux Completely Fair Scheduler uses redblack trees to store dynamic process info sorted by priority.

Floating point arithmetic  The binary exponent can be stored in a redblack tree for fast floating point math operations.

Scientific computing  Fast O(log n) ordered set operations provided by redblack trees are useful for problems like computational geometry and mesh generation.
For these applications, redblack trees provide optimal O(log n) performance for search, insert, and delete while maintaining balanced tree height through their unique coloring algorithm. This makes them one of the most effective balanced binary search tree structures.