Search

0.2.4.1 Insertion Operation

The insertion of a new node into a red-black tree can be a complicated procedure.

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 must ensue.

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:      

1.

Make the current node's right child equal to the current node's right child's left child.

2.

Make the current node's right child's parent the current node's parent.

3.

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->parent) 
    {
        if (current_node == current_node->parent->left)
            current_node->parent->left = child;
        else
            current_node->parent->right = child;
    } 
    else 
    {
        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.