10.3 Search

A right-threaded tree is inherently asymmetric, so many of the algorithms on it will necessarily be asymmetric as well. The search function is the simplest demonstration of this. For descent to the left, we test for a null left child with rtbst_link[0]; for descent to the right, we test for a right thread with rtbst_rtag. Otherwise, the code is familiar:

378. <RTBST search function 378> =
void *
rtbst_find (const struct rtbst_table *tree, const void *item) 
{
  const struct rtbst_node *p;
  int dir;

  assert (tree != NULL && item != NULL);

  if (tree->rtbst_root == NULL)
    return NULL;

  for (p = tree->rtbst_root; ; p = p->rtbst_link[dir]) 
    {
      int cmp = tree->rtbst_compare (item, p->rtbst_data, tree->rtbst_param);
      if (cmp == 0)
        return p->rtbst_data;
      dir = cmp > 0;

      if (dir == 0) 
        {
          if (p->rtbst_link[0] == NULL)
            return NULL;
        } 
      else /* dir == 1 */ 
        {
          if (p->rtbst_rtag == RTBST_THREAD)
            return NULL;
        }
    }
}

This code is included in 377, 420, and 457.