12.3.1 Steps 1 and 2: Search and Insert

The process of search and insertion proceeds as usual. Stack pa[], with pa[k - 1] at top of stack, records the parents of the node p currently under consideration, with corresponding stack da[] indicating the direction moved. We use the standard code for insertion into an RTBST. When the loop exits, p is the node under which a new node should be inserted on side dir.

```457. <Step 1: Search RTRB tree for insertion point 457> =
da[0] = 0;
pa[0] = (struct rtrb_node *) &tree->rtrb_root;
k = 1;
if (tree->rtrb_root != NULL)
for (p = tree->rtrb_root; ; p = p->rtrb_link[dir])     {
int cmp = tree->rtrb_compare (item, p->rtrb_data, tree->rtrb_param);
if (cmp == 0)
return &p->rtrb_data;

pa[k] = p;
da[k++] = dir = cmp > 0;

if (dir == 0)         {
break;
}       else /* dir == 1 */         {
break;
}
}
else   {
p = (struct rtrb_node *) &tree->rtrb_root;
dir = 0;
}
```

This code is included in 456.

```458. <Step 2: Insert RTRB node 458> =
n = tree->rtrb_alloc->libavl_malloc (tree->rtrb_alloc, sizeof *n);
if (n == NULL)
return NULL;

tree->rtrb_count++;
n->rtrb_data = item;
if (dir == 0)   {
if (tree->rtrb_root != NULL)