6.4 Insertion [ToC] [Index]     [Skip Back] [Skip Fwd]     [Prev] [Up] [Next]

The steps for insertion into a red-black tree are similar to those for insertion into an AVL tree:

  1. Search for the location to insert the new item.
  2. Insert the item.
  3. Rebalance the tree as necessary to satisfy the red-black balance condition.

Red-black node colors don't need to be updated in the way that AVL balance factors do, so there is no separate step for updating colors.

Here's the outline of the function, expressed as code: 

197. <RB item insertion function 197> =
void **
rb_probe (struct rb_table *tree, void *item) 
{
  <rb_probe() local variables 198>

  <Step 1: Search RB tree for insertion point 199>
  <Step 2: Insert RB node 200>
  <Step 3: Rebalance after RB insertion 201>

  return &n->rb_data;
}

This code is included in 196. 

198. <rb_probe() local variables 198> =
struct rb_node *pa[RB_MAX_HEIGHT]; /* Nodes on stack. */
unsigned char da[RB_MAX_HEIGHT];   /* Directions moved from stack nodes. */
int k;                             /* Stack height. */

struct rb_node *p; /* Traverses tree looking for insertion point. */
struct rb_node *n; /* Newly inserted node. */

assert (tree != NULL && item != NULL);

This code is included in 33, 197, and 210.

See also:  [Cormen 1990], section 14.3; [Sedgewick 1998], program 13.6.