The insertion of a new node into a red-black tree can be a complicated
In order to insert a new element it is mandatory to first determine
the point of insertion. To do this we traverse the tree as if it were
a binary search tree. Nodes less than or equal to the current node
in value cause us to traverse to the left child (whereas nodes greater
than the current node in value cause us to traverse right). As we move
down the tree we perform what is known as a color flip
operation. Every time a black node with two red children is
encountered we make the parent node red and the two children black.
This operation does not change the black height of the tree and helps
ensure easier insertion in most cases. Such a color flip, however,
can produce two red nodes in a row. Recall that two consecutive red
nodes on any path from root to leaf is not allowed in this structure.
If two consecutive red nodes are produced a tree-rebalancing operation
In order to eliminate pairs of consecutive red nodes from a red-black
tree a rotation operation is used. A rotation operation is performed
in a series of steps:
- Make the current node's right child equal to the current node's
right child's left child.
- Make the current node's right child's parent the current node's
- Make the current node's right child's left child the current node.
That's a mouthful. Here's the source code to a rotate left function;
you may find it easier to read:
void rotate_left(node *current_node)
node *child = current_node->right;
/* establish current_node->right link */
current_node->right = child->left;
child->left->parent = current_node;
/* establish child->parent link */
child->parent = current_node->parent;
if (current_node == current_node->parent->left)
current_node->parent->left = child;
current_node->parent->right = child;
root = child;
/* link child and current_node */
child->left = current_node;
current_node->parent = child;
The code for a rotate_right operation is what you would expect and
is given in the full red-black source code in the ensuing section. There
are only a few cases in which two red nodes exist on a path from root to
leaf after a color flip operation. See the code for insert_fix for
a case-by-case study.
When inserting a node in a leaf-with-black-parent situation simply create
a new red node between the parent and leaf. The leaf is now a child of
this new red node and the node you wanted to insert is the other child.
It is not always possible to arrive at a black-leaf, black-parent situation,
though. In this case the node insertion happens the same way (i.e. create
a new red node between the leaf and its parent; insert as children of this
new red node) but the insertion process is followed by an immediate tree
re-balancing as it created two red nodes in a row.
Insertion is a difficult operation to verbalize; the best way to get a
handle on what is going on is to make sure you understand the rules of
a red-black tree, make sure you understand the rotation operation, and
look at the source code below.