/* Deletes from |tree| and returns an item matching |item|.
   Returns a null pointer if no matching item found. */
void *
pavl_delete (struct pavl_table *tree, const void *item)
{
  struct pavl_node *p; /* Traverses tree to find node to delete. */
  struct pavl_node *q; /* Parent of |p|. */
  int dir;             /* Side of |q| on which |p| is linked. */

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

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

  p = tree->pavl_root;
  for (;;)
    {
      int cmp = tree->pavl_compare (item, p->pavl_data, tree->pavl_param);
      if (cmp == 0)
        break;

      dir = cmp > 0;
      p = p->pavl_link[dir];
      if (p == NULL)
        return NULL;
    }
  item = p->pavl_data;

  q = p->pavl_parent;
  if (q == NULL)
    {
      q = (struct pavl_node *) &tree->pavl_root;
      dir = 0;
    }

  if (p->pavl_link[1] == NULL)
    {
      q->pavl_link[dir] = p->pavl_link[0];
      if (q->pavl_link[dir] != NULL)
        q->pavl_link[dir]->pavl_parent = p->pavl_parent;
    }
  else
    {
      struct pavl_node *r = p->pavl_link[1];
      if (r->pavl_link[0] == NULL)
        {
          r->pavl_link[0] = p->pavl_link[0];
          q->pavl_link[dir] = r;
          r->pavl_parent = p->pavl_parent;
          if (r->pavl_link[0] != NULL)
            r->pavl_link[0]->pavl_parent = r;
          r->pavl_balance = p->pavl_balance;
          q = r;
          dir = 1;
        }
      else
        {
          struct pavl_node *s = r->pavl_link[0];
          while (s->pavl_link[0] != NULL)
            s = s->pavl_link[0];
          r = s->pavl_parent;
          r->pavl_link[0] = s->pavl_link[1];
          s->pavl_link[0] = p->pavl_link[0];
          s->pavl_link[1] = p->pavl_link[1];
          q->pavl_link[dir] = s;
          if (s->pavl_link[0] != NULL)
            s->pavl_link[0]->pavl_parent = s;
          s->pavl_link[1]->pavl_parent = s;
          s->pavl_parent = p->pavl_parent;
          if (r->pavl_link[0] != NULL)
            r->pavl_link[0]->pavl_parent = r;
          s->pavl_balance = p->pavl_balance;
          q = r;
          dir = 0;
        }
    }
  tree->pavl_alloc->libavl_free (tree->pavl_alloc, p);

  while (q != (struct pavl_node *) &tree->pavl_root)
    {
      struct pavl_node *y = q;

      if (y->pavl_parent != NULL)
        q = y->pavl_parent;
      else
        q = (struct pavl_node *) &tree->pavl_root;

      if (dir == 0)
        {
          dir = q->pavl_link[0] != y;
          y->pavl_balance++;
          if (y->pavl_balance == +1)
            break;
          else if (y->pavl_balance == +2)
            {
              struct pavl_node *x = y->pavl_link[1];
              if (x->pavl_balance == -1)
                {
                  struct pavl_node *w;

                  assert (x->pavl_balance == -1);
                  w = x->pavl_link[0];
                  x->pavl_link[0] = w->pavl_link[1];
                  w->pavl_link[1] = x;
                  y->pavl_link[1] = w->pavl_link[0];
                  w->pavl_link[0] = y;
                  if (w->pavl_balance == +1)
                    x->pavl_balance = 0, y->pavl_balance = -1;
                  else if (w->pavl_balance == 0)
                    x->pavl_balance = y->pavl_balance = 0;
                  else /* |w->pavl_balance == -1| */
                    x->pavl_balance = +1, y->pavl_balance = 0;
                  w->pavl_balance = 0;
                  w->pavl_parent = y->pavl_parent;
                  x->pavl_parent = y->pavl_parent = w;
                  if (x->pavl_link[0] != NULL)
                    x->pavl_link[0]->pavl_parent = x;
                  if (y->pavl_link[1] != NULL)
                    y->pavl_link[1]->pavl_parent = y;
                  q->pavl_link[dir] = w;
                }
              else
                {
                  y->pavl_link[1] = x->pavl_link[0];
                  x->pavl_link[0] = y;
                  x->pavl_parent = y->pavl_parent;
                  y->pavl_parent = x;
                  if (y->pavl_link[1] != NULL)
                    y->pavl_link[1]->pavl_parent = y;
                  q->pavl_link[dir] = x;
                  if (x->pavl_balance == 0)
                    {
                      x->pavl_balance = -1;
                      y->pavl_balance = +1;
                      break;
                    }
                  else
                    {
                      x->pavl_balance = y->pavl_balance = 0;
                      y = x;
                    }
                }
            }
        }
      else
        {
          dir = q->pavl_link[0] != y;
          y->pavl_balance--;
          if (y->pavl_balance == -1)
            break;
          else if (y->pavl_balance == -2)
            {
              struct pavl_node *x = y->pavl_link[0];
              if (x->pavl_balance == +1)
                {
                  struct pavl_node *w;
                  assert (x->pavl_balance == +1);
                  w = x->pavl_link[1];
                  x->pavl_link[1] = w->pavl_link[0];
                  w->pavl_link[0] = x;
                  y->pavl_link[0] = w->pavl_link[1];
                  w->pavl_link[1] = y;
                  if (w->pavl_balance == -1)
                    x->pavl_balance = 0, y->pavl_balance = +1;
                  else if (w->pavl_balance == 0)
                    x->pavl_balance = y->pavl_balance = 0;
                  else /* |w->pavl_balance == +1| */
                    x->pavl_balance = -1, y->pavl_balance = 0;
                  w->pavl_balance = 0;
                  w->pavl_parent = y->pavl_parent;
                  x->pavl_parent = y->pavl_parent = w;
                  if (x->pavl_link[1] != NULL)
                    x->pavl_link[1]->pavl_parent = x;
                  if (y->pavl_link[0] != NULL)
                    y->pavl_link[0]->pavl_parent = y;
                  q->pavl_link[dir] = w;
                }
              else
                {
                  y->pavl_link[0] = x->pavl_link[1];
                  x->pavl_link[1] = y;
                  x->pavl_parent = y->pavl_parent;
                  y->pavl_parent = x;
                  if (y->pavl_link[0] != NULL)
                    y->pavl_link[0]->pavl_parent = y;
                  q->pavl_link[dir] = x;
                  if (x->pavl_balance == 0)
                    {
                      x->pavl_balance = +1;
                      y->pavl_balance = -1;
                      break;
                    }
                  else
                    {
                      x->pavl_balance = y->pavl_balance = 0;
                      y = x;
                    }
                }
            }
        }
    }

  tree->pavl_count--;
  return (void *) item;
}