/* Deletes from |tree| and returns an item matching |item|.
   Returns a null pointer if no matching item found. */
void *
rtbst_delete (struct rtbst_table *tree, const void *item)
{
  struct rtbst_node *p;        /* Node to delete. */
  struct rtbst_node *q;        /* Parent of |p|. */
  int dir;              /* Index into |q->rtbst_link[]| that leads to |p|. */

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

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

  p = tree->rtbst_root;
  q = (struct rtbst_node *) &tree->rtbst_root;
  dir = 0;
  if (p == NULL)
    return NULL;

  for (;;)
    {
      int cmp = tree->rtbst_compare (item, p->rtbst_data, tree->rtbst_param);
      if (cmp == 0)
        break;

      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;
        }

      q = p;
      p = p->rtbst_link[dir];
    }
  item = p->rtbst_data;

  if (p->rtbst_link[0] == NULL)
    {
      if (p->rtbst_rtag == RTBST_CHILD)
        {
          q->rtbst_link[dir] = p->rtbst_link[1];
        }
      else
        {
          q->rtbst_link[dir] = p->rtbst_link[dir];
          if (dir == 1)
            q->rtbst_rtag = RTBST_THREAD;
        }
    }
  else
    {
      struct rtbst_node *r = p->rtbst_link[0];
      if (r->rtbst_rtag == RTBST_THREAD)
        {
          r->rtbst_link[1] = p->rtbst_link[1];
          r->rtbst_rtag = p->rtbst_rtag;
          q->rtbst_link[dir] = r;
        }
      else
        {
          struct rtbst_node *s;

          for (;;)
            {
              s = r->rtbst_link[1];
              if (s->rtbst_rtag == RTBST_THREAD)
                break;

              r = s;
            }

          if (s->rtbst_link[0] != NULL)
            r->rtbst_link[1] = s->rtbst_link[0];
          else
            {
              r->rtbst_link[1] = s;
              r->rtbst_rtag = RTBST_THREAD;
            }

          s->rtbst_link[0] = p->rtbst_link[0];
          s->rtbst_link[1] = p->rtbst_link[1];
          s->rtbst_rtag = p->rtbst_rtag;

          q->rtbst_link[dir] = s;
        }
    }

  tree->rtbst_alloc->libavl_free (tree->rtbst_alloc, p);
  tree->rtbst_count--;
  return (void *) item;
}