11.4.1 Steps 1–2: Search and Insert

The basic insertion step itself follows the same steps as <RTBST item insertion function 379> does for a plain RTBST. We do keep track of the directions moved on stack da[] and the last-seen node with nonzero balance factor, in the same way as <Step 1: Search AVL tree for insertion point 150> for unthreaded AVL trees.

```422. <Step 1: Search RTAVL tree for insertion point 422> =
z = (struct rtavl_node *) &tree->rtavl_root;
y = tree->rtavl_root;
if (tree->rtavl_root != NULL)
for (q = z, p = y; ; q = p, p = p->rtavl_link[dir])     {
int cmp = tree->rtavl_compare (item, p->rtavl_data, tree->rtavl_param);
if (cmp == 0)
return &p->rtavl_data;

if (p->rtavl_balance != 0)
z = q, y = p, k = 0;
da[k++] = dir = cmp > 0;

if (dir == 0)         {
if (p->rtavl_link[0] == NULL)
break;
}       else /* dir == 1 */         {
if (p->rtavl_rtag == RTAVL_THREAD)
break;
}
}
else   {
p = (struct rtavl_node *) &tree->rtavl_root;
dir = 0;
}
```

This code is included in 421.

```423. <Step 2: Insert RTAVL node 423> =
n = tree->rtavl_alloc->libavl_malloc (tree->rtavl_alloc, sizeof *n);
if (n == NULL)
return NULL;

tree->rtavl_count++;
n->rtavl_data = item;
if (dir == 0)
else /* dir == 1 */   {
p->rtavl_rtag = RTAVL_CHILD;