Introduction

Deletion in a left-leaning red-black tree is harder than insertion because you must avoid descending into a 2-node that cannot safely lose a key. In the top-down 2-3-4 style, the critical extra step is not just one more color flip. It is the inner-child rotation used when borrowing from the sibling. In standard code, that appears as a right rotation on the right child before a left rotation on the current node inside moveRedLeft, with the symmetric case handled in moveRedRight.

Why Deletion Needs More Than Insertion Fixups

Insertion mainly repairs right-leaning reds and consecutive left reds after the recursive call returns. Deletion is different because the algorithm has to prepare the path on the way down.

If you descend into a left child that is a 2-node, you may need to move a red link left first. If you descend into a right child that is a 2-node, you may need to move a red link right first.

That is where the additional rotation logic appears.

The Key Extra Rotation in moveRedLeft

The classic top-down LLRB deletion helper looks like this:

1RED = True
2BLACK = False
3
4
5def is_red(node):
6    return node is not None and node.red == RED
7
8
9def move_red_left(h):
10    flip_colors(h)
11    if is_red(h.right.left):
12        h.right = rotate_right(h.right)
13        h = rotate_left(h)
14        flip_colors(h)
15    return h

The important part is:

h.right = rotate_right(h.right)
h = rotate_left(h)

That is the extra rotation sequence people often miss.

Why is it needed?

Because if h.right.left is red, the sibling has a red child on the "inside." A direct left rotation on h alone would not preserve the left-leaning 2-3-4 correspondence correctly. The right child must first be rotated right so the borrowed red link is positioned correctly, and only then can h rotate left.

The Symmetric Case in moveRedRight

The mirror helper for descending right is usually written as:

1
2def move_red_right(h):
3    flip_colors(h)
4    if is_red(h.left.left):
5        h = rotate_right(h)
6        flip_colors(h)
7    return h

Here the extra logic is simpler because the borrowable red link is already on the outside in the usual left-leaning representation.

So the short answer to the question is:

• in the left-moving case, you need the extra inner-child rotation rotateRight(h.right) before rotateLeft(h)
• in the right-moving case, the symmetric top-down step is rotateRight(h) when h.left.left is red

What Problem This Solves in 2-3-4 Terms

A top-down LLRB simulates 2-nodes, 3-nodes, and 4-nodes using red links. During deletion, you want to avoid arriving at a leaf position where the node to delete lives inside a 2-node with no red sibling to borrow from.

The moveRedLeft and moveRedRight helpers push a red link toward the side you are descending into. The extra rotation handles the case where the sibling can lend a key, but the red link is one level too far inward.

In 2-3-4 language, it is the difference between:

• a sibling that can lend directly
• a sibling that must first be restructured so the lendable key is exposed

Full Balancing Still Happens After Deletion

After the actual delete step, the tree is usually repaired on the way back up with the normal balancing routine.

Typical cleanup logic:

1
2def balance(h):
3    if is_red(h.right):
4        h = rotate_left(h)
5    if is_red(h.left) and is_red(h.left.left):
6        h = rotate_right(h)
7    if is_red(h.left) and is_red(h.right):
8        flip_colors(h)
9    return h

So the additional deletion rotation does not replace ordinary balancing. It supplements it during the top-down descent.

Why Single-Rotation Explanations Are Incomplete

A common simplified explanation says "just rotate to fix imbalance during deletion." That is too vague to be useful.

The important detail is where the red child sits:

• if the borrowable red link is on the inside of the sibling, you need the extra preparatory rotation first
• if it is already on the outside, the top-down fix is simpler

That is why the rotateRight(h.right) step is the memorable extra piece in moveRedLeft.

Common Pitfalls

The biggest mistake is omitting the inner-child rotation from moveRedLeft. The tree may still compile and even pass simple tests, but deletion eventually violates left-leaning or black-height invariants.

Another mistake is treating top-down deletion as if the same local rules from insertion are enough. They are not. Deletion has to prepare the path before reaching the leaf.

Developers also sometimes forget that the deletion helpers and the post-delete balance step are both required. One without the other is incomplete.

Finally, be careful when translating between 2-3-4 tree language and LLRB code. The conceptual operation is borrowing or merging, but the binary-tree implementation expresses it through rotations and color flips.

Summary

• Top-down LLRB deletion needs more than ordinary insertion-style rotations.
• The important extra step is the inner-child rotation inside moveRedLeft.
• In code, that appears as rotateRight(h.right) before rotateLeft(h).
• The symmetric right-side case is handled in moveRedRight.
• These steps let the descent avoid deleting from an unprepared 2-node while preserving 2-3-4 correspondence.