Red-Black Tree: Colour in Place of Most Rotations

A red-black tree is a binary search tree with one additional piece of information stored at every node: a colour, either red or black. That colour is not decorative. It is a compact balancing mechanism that allows the tree to remain approximately balanced while avoiding a rotation after every structural change.

The central idea is straightforward. Preserve the binary-search-tree ordering, then use colour rules to control how long a root-to-leaf path can become. When insertion or deletion temporarily violates one of those rules, the tree repairs itself through a small combination of recolouring and rotation.

The main situations covered in this article are:

the five red-black properties;
recolouring when a red uncle is present;
LL, RR, LR, and RL rotations when the uncle is black;
the temporary double-black condition created by deleting a black node.

The goal is not to make every path exactly the same length. Instead, the rules prevent one path from becoming excessively longer than another. As a result, searching, inserting, and deleting remain logarithmic in the worst case.

1. The underlying binary search tree

Before considering colours, a red-black tree is an ordinary binary search tree. For every node with key $k$ :

keys in its left subtree are smaller than $k$ ;
keys in its right subtree are larger than $k$ ;
the same rule applies recursively to every subtree.

For example, a tree containing the keys $10$ , $5$ , and $15$ may have $10$ at the root, $5$ as its left child, and $15$ as its right child. The colours add balancing information, but they do not change the ordering rule.

A rotation must therefore preserve the in-order sequence of keys. If an in-order traversal before a rotation produces the sequence $5, 10, 15$ , the traversal afterward must produce exactly the same sequence. The shape changes, but the sorted order does not.

This distinction is useful when studying repairs:

recolouring changes metadata but does not change the shape;
rotation changes the shape but preserves binary-search-tree ordering.

A correct implementation must maintain both kinds of invariants. A tree may still produce sorted output even when its colours are invalid, so checking only the in-order sequence is not enough.

2. The five red-black properties

A red-black tree is valid when it satisfies five standard properties. Presentations sometimes number these rules differently, but the required ideas are the same.

Property 1: Every node has a colour

Each node is either red or black. The colour is part of the node's state and is examined during insertion and deletion repair.

A newly inserted ordinary node is commonly coloured red. This choice is useful because adding a red node does not immediately increase the number of black nodes on paths from the root. Adding a black node would create a black-height imbalance as soon as it was inserted.

The new red node can still create a red-red conflict with its parent. That conflict is repaired afterward.

Property 2: The root is black

The root must be black. If a repair temporarily makes the root red, recolouring the root black restores this property.

The root rule provides a stable boundary for repair. In an insertion sequence, a recolouring conflict may move upward through several ancestors, but it must eventually stop at the root. Making the root black is often the final step.

Property 3: Every external leaf is black

The missing children below ordinary nodes are treated as black leaves, often called NIL leaves or sentinel leaves. These leaves may be conceptual, or an implementation may represent them with a shared sentinel object.

This rule matters because paths are counted all the way to leaves. Treating absent children as black makes the black-height rule precise for nodes with one or no ordinary children.

For example, if an ordinary leaf has no children, it still has two black NIL children conceptually. Those endpoints are not red, and they are included when comparing the black counts of paths.

Property 4: A red node cannot have a red child

If a node is red, both of its children must be black. Equivalently, red nodes may not be adjacent along an edge.

This is the property most directly affected when a red node is inserted beneath a red parent. The resulting red-red conflict must be repaired. The repair may recolour the parent and its sibling, or it may rotate and recolour the nodes around the conflict.

Property 5: Every path from a node to its descendant leaves contains the same number of black nodes

For every node, all paths from that node down to its descendant NIL leaves must contain the same number of black nodes. This count is called the black-height of the node. Definitions differ on whether the starting node itself is included, but either convention works if it is used consistently.

Suppose one path from a node contains two black nodes before reaching a NIL leaf. Every other path below that node must contain two black nodes as well. Red nodes do not increase this count, which is why they can add some height without directly disturbing black-height equality.

The last two properties provide the balancing effect. No path may contain consecutive red nodes, and every path must contain the same black count. A path can contain extra red levels, but it cannot accumulate arbitrarily many of them.

3. Why colour can replace many rotations

An ordinary binary search tree can become tall when keys arrive in an unfortunate order. For example, inserting increasing keys can produce a chain that resembles a linked list. Searching that tree then takes linear time in the number of nodes.

A balancing algorithm must prevent this chain from growing unchecked. One possible response is to rotate frequently. A red-black tree has another option: recolouring.

Consider a local family consisting of a grandparent, a parent, an uncle, and a newly inserted node. If the parent and uncle are both red while the grandparent is black, recolouring can make the parent and uncle black and the grandparent red. The local red-red conflict disappears without changing the local shape.

The grandparent may now conflict with its own red parent. In that case, the same reasoning is applied one level higher. Recolouring can therefore move a possible conflict toward the root. A rotation is needed when the uncle is black and the local arrangement cannot be repaired by symmetric colour changes alone.

This is the meaning of colour in place of most rotations. The tree still rotates in important cases, but many insertion repairs are handled by changing colours rather than changing pointers.

Recolouring is especially useful because it preserves every parent-child relationship in the local subtree. It changes only node metadata. Rotation is more structurally involved because it changes which node is above another, even though it preserves the in-order key sequence.

4. Insertion: the initial situation

Insertion begins like ordinary binary-search-tree insertion. Compare the new key with the current node and move left or right until the correct empty position is found. The new ordinary node is then attached there.

The new node is coloured red, and its missing children are black NIL leaves. Several simple cases can finish immediately:

if the new node is the root, recolour it black;
if its parent is black, no red-red conflict exists;
if its parent is red, repair is required.

The interesting case occurs when the new node and its parent are both red. The repair examines three structural relationships:

the current node, usually the newly inserted node or a node reached after recolouring;
its parent;
its grandparent and the grandparent's other child, called the uncle.

The uncle determines the broad repair strategy. A red uncle leads to recolouring. A black uncle leads to one of four rotation patterns: LL, RR, LR, or RL.

The names describe the directions from the grandparent to the parent and from the parent to the current node. LL means left child followed by left child. RR means right followed by right. LR means left followed by right. RL means right followed by left.

5. Insertion with a red uncle: recolouring

Suppose a black grandparent has a red parent and a red uncle. The newly inserted node is red, so the parent and the new node form a red-red edge. The uncle is red as well.

The usual repair is:

colour the parent black;
colour the uncle black;
colour the grandparent red;
continue repairing from the grandparent if it now has a red parent;
ensure that the root is black when the upward repair finishes.

The black-height reasoning is important. Before the repair, the grandparent's two child subtrees have matching black-height. Turning both red children black adds one black node to every path through each child, so the two sides remain equal. Turning the grandparent red prevents the grandparent itself from adding an extra black node above those paths.

A small conceptual example looks like this:

        G(B)
       /    \\
    P(R)    U(R)
    /
  N(R)

After recolouring:

        G(R)
       /    \\
    P(B)    U(B)
    /
  N(R)

The red-red conflict between $P$ and $N$ has disappeared. The possible new conflict is between $G$ and its own parent, so repair may continue upward. No rotation was required in this local step.

If $G$ is the root, recolouring it black restores the root property. If $G$ is not the root, the algorithm examines its relationship with its parent in the same way.

6. Insertion with a black uncle

When the uncle is black, recolouring both sides in the same way does not solve the shape of the red-red conflict. A rotation moves a suitable node upward and restores a valid local arrangement of colours.

The four patterns are mirror pairs:

LL and RR are straight-line cases;
LR and RL are zigzag cases.

The exact pointer assignments depend on the implementation, but the structural goals are consistent. A rotation preserves in-order key order, places a useful node nearer the top of the local subtree, and assigns colours so that the red-red violation disappears while black-height remains equal.

6.1 LL case

The LL case occurs when the parent is the grandparent's left child and the current node is the parent's left child:

        G(B)
       /
    P(R)
    /
  N(R)

A right rotation around $G$ makes $P$ the local subtree root. The usual colour adjustment makes $P$ black and $G$ red:

       P(B)
      /    \\
   N(R)    G(R)

The keys remain in sorted order. If $A$ , $B$ , $C$ , and $D$ represent the surrounding subtrees, the rotation preserves their in-order arrangement. The shape changes, but no key crosses another key in sorted order.

The new local root is black, so the red node beneath it is not adjacent to another red node. The colour change also restores the black count on paths through the local subtree.

6.2 RR case

The RR case is the mirror image. The parent is the grandparent's right child, and the current node is the parent's right child:

  G(B)
      \\
      P(R)
          \\
          N(R)

A left rotation around $G$ makes $P$ the local root. The typical colour adjustment is again to make $P$ black and $G$ red:

       P(B)
      /    \\
   G(R)    N(R)

The RR repair is therefore the mirror of LL. Exchange left with right, and exchange right rotation with left rotation.

6.3 LR case

The LR case is a zigzag. The parent is the grandparent's left child, but the current node is the parent's right child:

        G(B)
       /
    P(R)
        \\
        N(R)

A single rotation around the grandparent is not immediately aligned with the chain. The usual repair first rotates left around $P$ , converting the zigzag into an LL shape:

        G(B)
       /
    N(R)
    /
  P(R)

The LL repair can then be applied: rotate right around $G$ and adjust the colours. The resulting local arrangement has $N$ at the top, with $P$ on the left and $G$ on the right.

The important lesson is that a zigzag case is commonly transformed into a straight-line case before the final rotation. This two-step view is easier to remember than a collection of unrelated pointer diagrams.

6.4 RL case

The RL case is the mirror image of LR. The parent is the grandparent's right child, and the current node is the parent's left child:

  G(B)
      \\
      P(R)
      /
    N(R)

The first step rotates right around $P$ , turning the zigzag into an RR configuration. The second step rotates left around $G$ and adjusts colours. The current node becomes the local subtree root, with the former parent and grandparent below it on opposite sides.

The insertion patterns can be summarised as follows:

LL: left, then left       -> right rotation
RR: right, then right     -> left rotation
LR: left, then right      -> left rotation, then right rotation
RL: right, then left      -> right rotation, then left rotation

For every case, inspect the uncle before choosing a rotation. A red uncle means recolour first. A black uncle means classify the shape.

7. What a rotation preserves

A rotation is a local restructuring operation. It changes parent-child relationships but preserves the binary-search-tree sequence.

Imagine two keys $x$ and $y$ with $x < y$ , together with three ordered subtrees $A$ , $B$ , and $C$ . Before a right rotation, the arrangement may be:

After the rotation:

The in-order sequence is $A$ , then $x$ , then $B$ , then $y$ in both shapes. The rotation does not lose or reorder keys. It only changes which node is higher.

This is why rotations are safe for a binary search tree when implemented correctly. The balancing algorithm can adjust height and colours without abandoning search ordering.

A rotation also has constant local cost. It changes a fixed number of links, so one rotation takes $O(1)$ time. Recolouring a fixed number of nodes also takes $O(1)$ time. The complete operation may still take logarithmic time because repair can move upward through the height of the tree.

8. Insertion repair as a decision process

A useful insertion checklist is:

Insert the key using binary-search-tree ordering.
Colour the new ordinary node red.
If the node is the root, colour it black.
If its parent is black, stop.
If its parent is red, identify the grandparent and uncle.
If the uncle is red, recolour the parent and uncle black, recolour the grandparent red, and continue upward.
If the uncle is black, classify the shape as LL, RR, LR, or RL.
Rotate and recolour according to that shape.
Ensure that the root is black.

This separates two kinds of repair. Recolouring addresses a colour conflict while preserving local shape. Rotation addresses a shape that places the red nodes in a straight-line or zigzag arrangement that cannot be fixed by recolouring alone.

A common mistake is to rotate as soon as a red-red conflict appears. That skips the uncle test. If the uncle is red, recolouring is the simpler and correct local repair.

9. Why deletion is different

Deletion can remove a red or black node. Removing a red node is usually less disruptive to black-height because red nodes do not contribute to the black count. Removing a black node can reduce the number of black nodes on every path through one side of a subtree.

That imbalance is represented by a temporary double-black condition. Double black is best understood as a deficit marker: the affected position behaves as though it needs one additional black contribution to match the paths on the other side.

Double black is not a third permanent colour. It is a temporary state used while deletion repair moves the deficit upward or eliminates it through recolouring and rotation.

Deletion must still preserve binary-search-tree ordering. If the deleted node has two ordinary children, an implementation can move its key or position to a suitable neighbouring node before removing a node with at most one ordinary child. The balancing repair is associated with the position where the physical removal occurs.

The important balancing issue is what happens after a black node is physically removed. One side of the parent may then have one fewer black node on every path.

10. The double-black situation

Suppose a black node is removed from one side of a parent. Paths through that side now contain one fewer black node than paths through the other side. The affected child position is marked double black, conceptually carrying a missing black unit.

Repair examines:

the parent of the double-black position;
its sibling;
the sibling's near child;
the sibling's far child.

Near and far are relative to the double-black position. If the double-black position is the left child of the parent, the sibling is on the right. The sibling's near child is its left child, closer to the double-black position, and its far child is its right child. If the double-black position is on the right, the directions reverse.

The cases are mirror-symmetric, just as insertion cases are. Learning one side carefully and reflecting it for the other side reduces the number of independent situations to remember.

11. A red sibling during deletion repair

If the sibling of the double-black position is red, the parent is generally black under the red-black properties. A rotation around the parent changes the sibling into a black-sibling configuration.

For a double-black left child with a red right sibling, the repair rotates left around the parent. The former sibling moves upward, the former parent moves downward, and their colours are exchanged in the standard way. The double-black position remains on the same general side, but the sibling examined in the next step is now black.

This is a preparatory case rather than the final resolution. It converts a red-sibling situation into one of the black-sibling cases. The mirror operation is used when the double-black position is on the right.

The key insight is that colour and rotation can change which local case is visible without changing the in-order key sequence.

12. A black sibling with black children

Suppose the sibling is black and both of the sibling's children are black, including conceptual NIL leaves where appropriate. Recolouring the sibling red removes one black contribution from paths through the sibling side, matching the deficit on the double-black side locally.

The deficit may then move upward to the parent. The parent becomes the new position to examine. If the parent was red, it can often be recoloured black and absorb the deficit, ending the repair. If the parent was black, the double-black condition may continue toward the root.

This case demonstrates that deletion repair, like insertion repair with a red uncle, can propagate upward through recolouring instead of immediately rotating.

If the double-black condition reaches the root, the extra black requirement can be discarded at the root. The upward propagation terminates there, and the tree can satisfy the black-height and root requirements again.

13. A black sibling with a red near child

A black sibling may have a red near child but a black far child. This is not yet the most convenient orientation for the final rotation. The usual repair rotates around the sibling and changes colours so that the red near child moves into the far-child position.

For a double-black left child, the sibling is on the right. Its near child is the sibling's left child, and its far child is the sibling's right child. If the near child is red while the far child is black, a right rotation around the sibling transforms the configuration. After recolouring, the next case has a red far child.

This is similar in spirit to insertion's LR and RL repairs. A preliminary rotation converts an inconvenient orientation into a straight-line orientation. The final repair can then be applied uniformly.

The mirror case applies when the double-black position is on the right: use the corresponding opposite rotation around the sibling.

14. A black sibling with a red far child

The final major deletion configuration has a black sibling with a red far child. This arrangement supports a rotation around the parent that removes the double-black deficit.

For a double-black left child, the sibling is on the right and the far child is the sibling's right child. A left rotation around the parent brings the sibling upward. Colours are then assigned so that the new local subtree has matching black counts, and the far red child becomes black as needed.

The double-black condition is resolved by this local operation. The subtree can be attached back to the rest of the tree without carrying a deficit upward. The mirror case uses a right rotation when the double-black position is on the right.

The exact order of pointer updates matters in code. A safe implementation records the relevant parent, sibling, near child, and far child before changing links, then updates colours and parent references consistently. Conceptually, the goal is simple: rotate a suitable red descendant upward and redistribute blackness across the two sides.

15. Why double black is temporary

It can be confusing to describe a node as double black when the five properties say that nodes are red or black. The distinction is that double black is a temporary repair state, not a final node colour.

During deletion, the algorithm allows a local path-count deficit to be represented explicitly. While repair is in progress, the intermediate structure may not satisfy every final property. Each case must do one of the following:

absorb the deficit at a red parent;
move the deficit to a higher black parent;
change the local shape and colours so the deficit disappears; or
reach the root, where the extra requirement can be removed.

The algorithm terminates only after the ordinary red-black properties have been restored. At that point, every ordinary node is red or black, the root is black, red nodes have black children, and every node has equal black-height on all paths to descendant leaves.

16. Comparing insertion and deletion

Insertion usually begins with an extra red node. Its immediate danger is a red-red edge. The repair asks whether the uncle is red or black:

red uncle: recolour and move the possible conflict upward;
black uncle: rotate according to LL, RR, LR, or RL and recolour.

Deletion of a black node usually begins with a black-height deficit. Its temporary representation is double black. The repair asks about the sibling and the sibling's children:

red sibling: rotate and convert to a black-sibling case;
black sibling with black children: recolour the sibling and move the deficit upward;
black sibling with a red near child: rotate the sibling to prepare the final shape;
black sibling with a red far child: rotate around the parent and finish.

Both procedures use the same general toolkit: inspect a small neighbourhood, recolour nodes, rotate locally, and continue upward only when the local operation transfers a problem to the parent.

The difference is the type of imbalance. Insertion primarily creates a red-red conflict. Deletion of a black node primarily creates a black-height deficit.

17. Complexity

Let $n$ be the number of ordinary nodes. The red-black properties bound the tree height by a logarithmic function of $n$ . A standard summary is:

h = O(\\log n)

where $h$ is the height of the tree. A search follows at most one root-to-leaf path, so its running time is:

O(h) = O(\\log n)

Insertion first follows a search path and then performs local repairs that may move upward along that path. Therefore insertion is $O(\\log n)$ . Deletion has the same asymptotic bound because its repair also progresses through a bounded number of local actions per level:

T_{\\text{search}}(n) = O(\\log n), \\qquad T_{\\text{insert}}(n) = O(\\log n), \\qquad T_{\\text{delete}}(n) = O(\\log n)

A single rotation changes a constant number of links, so its cost is $O(1)$ . Recolouring a constant number of nodes is also $O(1)$ . The logarithmic total comes from the possible upward movement through the height of the tree, not from the individual local operations.

The colour information adds only constant storage per node. Each node needs its key, child references, a colour value, and possibly a parent reference. The total structure therefore uses linear space:

S(n) = O(n)

18. Traversals remain ordinary

Red-black balancing does not require a special traversal algorithm. In-order traversal still visits keys in sorted order. Pre-order, post-order, and level-order traversals work as they do for other binary trees.

In-order traversal is especially useful for checking that rotations preserved binary-search-tree ordering. If a sequence of insertions and deletions is correct, the traversal should contain the expected keys in sorted order regardless of the current shape.

A separate validation routine can check the five properties. It should verify that:

every ordinary node has an allowed colour;
the root is black;
NIL leaves are black;
no red node has a red child;
corresponding paths have equal black-height.

This validation is valuable because a tree can have correct sorted order while still violating the balancing rules. For example, a plain unbalanced binary search tree may pass an in-order check perfectly while having a linear height.

19. Practical implementation checks

Several invariants deserve explicit attention when implementing a red-black tree.

Update the root during rotations

Every rotation must update the root when the rotated node was the root. It must also reconnect the rotated subtree to the former grandparent or parent. Forgetting this connection can silently detach part of the tree.

Keep parent and child references consistent

If a node becomes a child of another node, its parent reference must be updated. If a subtree changes sides during a rotation, both the link from the parent and the link from the moved subtree must be changed.

Handle NIL leaves consistently

If a shared black sentinel is used, operations should not accidentally recolour the sentinel or treat it as an ordinary key-bearing node. All comparisons and child accesses should follow one consistent representation.

Force the root to black

The root should be made black after insertion repair and after deletion repair. Even if the local cases appear correct, this final step protects the root property.

Distinguish logical deletion from physical removal

When deleting a node with two children, the requested key may be moved before a simpler node is physically removed. The balancing repair is attached to the physical removal position, not necessarily to the original node object associated with the requested key.

Test mirror cases

Every LL case should have an RR counterpart, and every LR case should have an RL counterpart. The same principle applies to deletion: left-side double-black cases should be tested with their right-side reflections.

Small tests that isolate one case are easier to debug than large random sequences. After each test, check both the sorted traversal and every red-black property.

20. A visual memory aid

For insertion, focus on the path from grandparent to current node:

LL: left, then left       -> right rotation
RR: right, then right     -> left rotation
LR: left, then right      -> left rotation, then right rotation
RL: right, then left      -> right rotation, then left rotation

The first rotation in a zigzag case removes the bend. The second rotation repairs the resulting straight-line case.

For insertion, always inspect the uncle before choosing a rotation. A red uncle means colour first. A black uncle means classify the shape.

For deletion, focus on the sibling of the double-black position:

red sibling                   -> rotate to obtain a black sibling
black sibling, black children  -> recolour and move upward
black sibling, red near child -> rotate sibling to prepare
black sibling, red far child  -> rotate parent and finish

The exact side determines whether the rotation is left or right, but the logical sequence is the same.

21. The main conceptual takeaway

A red-black tree does not maintain perfect symmetry. Some paths can be longer than others, and red nodes deliberately allow a path to contain extra levels. What the tree controls is the amount of imbalance.

The five properties establish that control system:

colours are limited to red and black;
the root and NIL leaves are black;
red nodes cannot touch red children;
every node has equal black-height to all descendant leaves.

Insertion usually introduces a red node and may create a red-red conflict. A red uncle allows recolouring, which often moves the issue upward without changing the shape. A black uncle requires a local rotation pattern: LL, RR, LR, or RL.

Deletion of a black node may create a black-height deficit. Double black records that deficit while the algorithm examines the sibling, near child, and far child. Recolouring may move the deficit upward, while rotations and recolouring together can eliminate it locally.

The result is a binary search tree whose ordering remains intact and whose height remains logarithmic. The balancing is achieved not by rotating after every change, but by choosing between colour changes and rotations according to the local configuration.

That is the practical meaning of the title: colour takes the place of most rotations. Recolouring handles many local conflicts cheaply, while rotations are reserved for the configurations where the shape itself must change.

1. The underlying binary search tree​

2. The five red-black properties​

Property 1: Every node has a colour​

Property 2: The root is black​

Property 3: Every external leaf is black​

Property 4: A red node cannot have a red child​

Property 5: Every path from a node to its descendant leaves contains the same number of black nodes​

3. Why colour can replace many rotations​

4. Insertion: the initial situation​

5. Insertion with a red uncle: recolouring​

6. Insertion with a black uncle​

6.1 LL case​

6.2 RR case​

6.3 LR case​

6.4 RL case​

7. What a rotation preserves​

8. Insertion repair as a decision process​

9. Why deletion is different​

10. The double-black situation​

11. A red sibling during deletion repair​

12. A black sibling with black children​

13. A black sibling with a red near child​

14. A black sibling with a red far child​

15. Why double black is temporary​

16. Comparing insertion and deletion​

17. Complexity​

18. Traversals remain ordinary​

19. Practical implementation checks​

Update the root during rotations​

Keep parent and child references consistent​

Handle NIL leaves consistently​

Force the root to black​

Distinguish logical deletion from physical removal​

Test mirror cases​

20. A visual memory aid​

21. The main conceptual takeaway​