11.5.1 Step 1: Search

There's nothing new in searching an RTAVL tree for a node to delete. We use p to search the tree, and push its chain of parent nodes onto stack pa[] along with the directions da[] moved down from them, including the pseudo-root node at the top.

432. <Step 1: Search RTAVL tree for item to delete 432> =
k = 1;
da[0] = 0;
pa[0] = (struct rtavl_node *) &tree->rtavl_root;
p = tree->rtavl_root;
if (p == NULL)
  return NULL;

for (;;) 
  {
    int cmp, dir;

    cmp = tree->rtavl_compare (item, p->rtavl_data, tree->rtavl_param);
    if (cmp == 0)
      break;

    dir = cmp > 0;
    if (dir == 0) 
      {
        if (p->rtavl_link[0] == NULL)
          return NULL;
      } 
    else /* dir == 1 */ 
      {
        if (p->rtavl_rtag == RTAVL_THREAD)
          return NULL;
      }

    pa[k] = p;
    da[k++] = dir;
    p = p->rtavl_link[dir];
  }
tree->rtavl_count--;
item = p->rtavl_data;

This code is included in 431 and 470.