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;