6.4.1 Step 1: Search |

The first thing to do is to search for the point to insert the new node. In a manner similar to AVL deletion, we keep a stack of nodes tracking the path followed to arrive at the insertion point, so that later we can move up the tree in rebalancing.

201. <Step 1: Search RB tree for insertion point 201> =pa[0] = (structrb_node*) &tree->rb_root;da[0] = 0;k= 1;for(p=tree->rb_root;p!=NULL;p=p->rb_link[da[k- 1]])

{intcmp=tree->rb_compare(item,p->rb_data,tree->rb_param);if(cmp== 0)return&p->rb_data;pa[k] =p;da[k++] =cmp> 0; }