6.4 Insertion |

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

**Search**for the location to insert the new item.**Insert**the item.**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:

199. <RB item insertion function 199> =void**rb_probe(structrb_table*tree,void*item)

{ <rb_probe() local variables 200> <Step 1: Search RB tree for insertion point 201> <Step 2: Insert RB node 202> <Step 3: Rebalance after RB insertion 203>return&n->rb_data; }

This code is included in 198.

200. <rb_probe() local variables 200> =structrb_node*pa[RB_MAX_HEIGHT]; /* Nodes on stack. */unsignedcharda[RB_MAX_HEIGHT]; /* Directions moved from stack nodes. */intk; /* Stack height. */structrb_node*p; /* Traverses tree looking for insertion point. */structrb_node*n; /* Newly inserted node. */assert(tree!=NULL&&item!=NULL);

This code is included in 34, 199, and 212.

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