How to delete a node in a red-black tree

A red-black tree is a type of self-balancing binary tree. This Answer covers deletion in a red-black tree using Python.

Note: To read more about red-black trees, visit here.

Deletion

Deletion in a red-black tree is similar to a BST, except for one added step. If, after deletion, a red-black property is disrupted, the tree has to be recolored or rotated.

The process is as follows:

  1. First, we find the node that we want to delete.

  2. In case it is a leaf node, we just replace it with None. Otherwise, we replace it with a leaf node, which must be a child with the minimum value. Then, we set it to None.

  3. If the color properties are violated, we rebalance and recolor the tree.

The original tree
The tree after deleting 7

Code example

Let's look at some code to see how it works.

class Node:
    def __init__(self, value, color=RED):
        self.value = value
        self.left = None
        self.right = None
        self.parent = None
        self.color = color
class RedBlackTree:
    def __init__(self):
        self.root = None
        self.none = Node(0, BLACK)
    
    def _min(self, node):
        while node.left != self.none:
            node = node.left
        return node
    
    def delete(self, val):
        return self._delete(self.root, val)
    
    def _delete(self, node, val):
        temp = self.none
        while node != self.none:
            if node.value == val:
                temp = node
            if node.value <= val:
                node = node.right
            else:
                node = node.left
        if temp == self.none:
            return False
        temp2 = temp
        temp2_original_color = temp2.color
        if temp.left == self.none:
            temp3 = temp.right
            self._rbt ( temp , temp.right )
        elif (temp.right == self.none):
            temp3 = temp.left
            self._rbt ( temp , temp.left )
        else:
            temp2 = self.minimum ( temp.right )
            temp2_original_color = temp2.color
            temp3 = temp2.right
            if temp2.parent == temp:
                temp3.parent = temp2
            else:
                self._rbt ( temp2 , temp2.right )
                temp2.right = temp.right
                temp2.right.parent = temp2
            self._rbt ( temp , temp2 )
            temp2.left = temp.left
            temp2.left.parent = temp2
            temp2.color = temp.color
        if temp2_original_color == BLACK:
            self._fixDelete( temp3 )
    
    def _rbt(self, x, y):
        if not x.parent:
            self.root = y
        elif x == x.parent.left:
            x.parent.left = y
        else:
            x.parent.right = y
        y.parent = x.parent
    
    def _fixDelete(self, node):
        while node != self.root and node.color == BLACK:
            if node == node.parent.left:
                temp = node.parent.right
                if temp.color == RED:
                    temp.color = BLACK
                    node.parent.color = RED
                    self.leftRotate(node.parent)
                    temp = node.parent.right
                if temp.left.color == BLACK and temp.right.color == BLACK:
                    temp.color = RED
                    node = node.parent
                else:
                    if temp.right.color == BLACK:
                        temp.left.color = BLACK
                        temp.color = RED
                        self.rightRotate(temp)
                        temp = node.parent.right
                    temp.color = node.parent.color
                    node.parent.color = BLACK
                    temp.right.color = BLACK
                    self.leftRotate(node.parent)
                    node = self.root
            else:
                temp = node.parent.left
                if temp.color == RED:
                    temp.color = BLACK
                    node.parent.color = RED
                    self.rightRotate(node.parent)
                    temp = node.parent.left
                if temp.right.color == BLACK and temp.right.color == BLACK:
                    temp.color = RED
                    node = node.parent
                else:
                    if temp.left.color == BLACK:
                        temp.right.color = BLACK
                        temp.color = RED
                        self.leftRotate(temp)
                        temp = node.parent.left
                    temp.color = node.parent.color
                    node.parent.color = BLACK
                    temp.left.color = BLACK
                    self.rightRotate(node.parent)
                    node = node.root
        node.color = BLACK
    def leftRotate(self, node):
        right_child = node.right
        node.right = right_child.left
        if right_child.left != self.none:
            right_child.left.parent = node
        if not node.parent:
            self.root = right_child
        elif node.parent.left == node:
            node.parent.left = right_child
        else:
            node.parent.right = right_child
        
        right_child.parent = node.parent
        right_child.left = node
        node.parent = right_child
    
    def rightRotate(self, node):
        left_child = node.left
        node.left = left_child.right
        if left_child.right != self.none:
            left_child.right.parent = node
        
        if not node.parent:
            self.root = left_child
        elif node.parent.left == node:
            node.parent.left = left_child
        else:
            node.parent.right = left_child
        
        left_child.parent = node.parent
        left_child.right = node
        node.parent = left_child
tree = RedBlackTree()
tree.root = Node(10, BLACK)
tree.root.left = Node(5, BLACK)
tree.root.left.parent = tree.root
tree.root.right = Node(20, BLACK)
tree.root.right.parent = tree.root
tree.root.left.left = Node(1, BLACK)
tree.root.left.left.parent = tree.root.left
tree.root.left.right = Node(7, BLACK)
tree.root.left.right.parent = tree.root.left
tree.root.right.left = Node(15, BLACK)
tree.root.right.left.parent = tree.root.right
tree.root.right.right = Node(30, BLACK)
tree.root.right.right.parent = tree.root.right
tree.root.right.right.right = tree.none
tree.root.right.right.left = tree.none
tree.root.right.left.right = tree.none
tree.root.right.left.left = tree.none
tree.root.left.right.right = tree.none
tree.root.left.right.left = tree.none
tree.root.left.left.left = tree.none
tree.root.left.left.right = tree.none
tree.delete(7) # delete the tree
print("         ", tree.root.value, tree.root.color)
print("         /        \\")
print("    ", tree.root.left.value, tree.root.left.color, "  ", tree.root.right.value, tree.root.right.color)
print("    /          /        \\")
print("", tree.root.left.left.value, tree.root.left.left.color, "   ", tree.root.right.left.value, tree.root.right.left.color, "   ", tree.root.right.right.value, tree.root.right.right.color)

Explanation

  • Lines 1–7: We define a Node class that stores one node of the red-black tree.

  • Lines 19–20: We define a delete() function that calls the _delete() helper function.

  • Lines 22–60: The _delete() function first goes through the tree to find the node. It then deletes the node and checks if any properties are violated. If they are, it calls the _fixDelete() function.

  • Lines 71–115: The fixDelete() function rebalances and recolors the tree. It starts at the deleted node, and then goes up to the root until the tree is balanced again.

  • Lines 151–180: We create a tree, call the delete() function on it, and print the resulting red-black tree.

Free Resources

Copyright ©2026 Educative, Inc. All rights reserved