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:

First, we find the node that we want to delete.
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.
If the color properties are violated, we rebalance and recolor the tree.

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.

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments

How to delete a node in a red-black tree

Deletion

Code example

Explanation