Implementing Red-Black Tree in Go — Part 2: The Delete Operation

We figured out how the search and insert operation works in the red-black tree in the first part. In this part, we figure out how the delete operation works. The delete operation is more complicated than the insert operation.

The Delete Operation

The delete operation as well as the insert operation ensures O(log(n)) time complexity. First, we must implement an auxiliary transplant method that transplants y’s node to x’s node place.

func (tree *Tree[K, V]) transplant(x *TreeNode[K, V], y *TreeNode[K, V]) {
	if x.parent == tree.leaf {
		tree.root = y
	} else if x == x.parent.left {
		x.parent.left = y
	} else {
		x.parent.right = y
	}

	y.parent = x.parent
}

The delete operation is similar to the delete operation in the binary search tree but has several differences. We have to keep the original color of the deleted node. If the deleted node is red, we don’t violate any properties of the red-black tree, but if the deleted node is black, we can violate the red-black properties.

1. We might violate the first property: the root is black, if a transplanted node is red, and the deleted node is black.

   
   

2. We might violate the third property: there cannot be two neighboring red nodes if the parent of the deleted node is red and the transplanted node is red.

   
   

3. We will violate the fifth property: having the same number of black nodes from the root to each leaf.

We must run the auxiliary method to restore the red-black properties.

The algorithm for deleting a node in a red-black tree is as follows.

1. We need to declare a variable that will store the color of the node to be deleted.

2. If the node has no children or only one child, we can transplant this node or leaf in case the node has no children to the node to be deleted. If the color of the node to be deleted is black, we need to run the deleteFixup helper method.

3. If the node to be deleted has two children, it is necessary to find a successor of this node. The successor of the node is the leftmost node of its right child. It is essential to save the color of the descendant to a variable, as there may be violations there after the transplantation.

If the successor is not the right child of the node being deleted, we need to transplant the right subtree of the successor to the successor. Then we must transplant the successor into the node to be deleted and set the color of the node to be deleted.

Then we must run the method deleteFixup if it is required.

func (tree *Tree[K, V]) Delete(key K) {
	x := tree.lookup(key)

	if x == tree.leaf {
		return
	}

	var y *TreeNode[K, V]
	originalColor := x.color

    
	if x.left == tree.leaf { 
		y = x.right
		tree.transplant(x, x.right)
	} else if x.right == tree.leaf {
		y = x.left
		tree.transplant(x, x.left)
	} else {
		successor := tree.leftmost(x.right)
		originalColor = successor.color
    
		y = successor.right

		if successor != x.right {
			tree.transplant(successor, successor.right)
			successor.right = x.right
			successor.right.parent = successor
		} else {
			y.parent = successor
		}

		tree.transplant(x, successor)
		successor.left = x.left
		successor.left.parent = successor
		successor.color = x.color
	}

	tree.len--

	if originalColor == black {
		tree.deleteFixup(y)
	}
}

4 cases are used to rebalance the red-black tree after deleting the node.

1. Case one occurs when the sibling of the node is red. We must exchange the color of the current node’s parent and the current node’s sibling and rotate the node’s parent to the left if the node belongs to a left subtree, or rotate to the right if the node belongs to the right subtree and then updating the sibling.

   

   
   

2. Case two occurs when both sibling’s children have the black color. The sibling is also black. We must change the color of the sibling to red and leave the current node. If the node’s parent is red, the cycle terminates.

   

   
   

3. Case 3 occurs when both the sibling and its right child have the black color, and the left child has the red color. Need to exchange colors of the sibling’s left child and sibling and rotate the sibling to the right if the node belongs to the left subtree, and rotate to the left if the node belongs to the right subtree and update the sibling. Then we go to the fourth case.

   

4. Case 4 occurs when the right child of the sibling is red and the sibling has a black color. We must change the color of the sibling’s right child to black, and change the current node’s parent to black.

Then we must rotate the node’s parent to the left if the node belongs to the left subtree, or rotate to the right if the node belongs to the right subtree. Then we set the current node as the root tree.

func (tree *Tree[K, V]) deleteFixup(x *TreeNode[K, V]) {
	for x != tree.root && x.color == black {
		if x == x.parent.left {
			y := x.parent.right

			if y.color == red {
				y.color = black
				x.parent.color = red
				tree.leftRotate(x.parent)
				y = x.parent.right
			}

			if y.left.color == black && y.right.color == black {
				y.color = red
				x = x.parent
			} else {

				if y.right.color == black {
					y.left.color = black
					y.color = red
					tree.rightRotate(y)
					y = x.parent.right
				}

				y.color = x.parent.color
				x.parent.color = black
				y.right.color = black
				tree.leftRotate(x.parent)
				x = tree.root
			}
		} else {
			y := x.parent.left

			if y.color == red {
				y.color = black
				x.parent.color = red
				tree.rightRotate(x.parent)
				y = x.parent.left
			}

			if y.left.color == black && y.right.color == black {
				y.color = red
				x = x.parent
			} else {

				if y.left.color == black {
					y.right.color = black
					y.color = red
					tree.leftRotate(y)
					y = x.parent.left
				}

				y.color = x.parent.color
				x.parent.color = black
				x.left.color = black
				tree.rightRotate(x.parent)
				x = tree.root
			}
		}
	}
	tree.root.color = black
}

I hope it is now more clear how node deleting works in the red-black tree.