if (p->tavl_tag[1] == TAVL_THREAD) { if (p->tavl_tag[0] == TAVL_CHILD) { struct tavl_node *t = p->tavl_link[0]; while (t->tavl_tag[1] == TAVL_CHILD) t = t->tavl_link[1]; t->tavl_link[1] = p->tavl_link[1]; q->tavl_link[dir] = p->tavl_link[0]; } else { q->tavl_link[dir] = p->tavl_link[dir]; if (q != (struct tavl_node *) &tree->tavl_root) q->tavl_tag[dir] = TAVL_THREAD; } } else { struct tavl_node *r = p->tavl_link[1]; if (r->tavl_tag[0] == TAVL_THREAD) { r->tavl_link[0] = p->tavl_link[0]; r->tavl_tag[0] = p->tavl_tag[0]; if (r->tavl_tag[0] == TAVL_CHILD) { struct tavl_node *t = r->tavl_link[0]; while (t->tavl_tag[1] == TAVL_CHILD) t = t->tavl_link[1]; t->tavl_link[1] = r; } q->tavl_link[dir] = r; r->tavl_balance = p->tavl_balance; q = r; dir = 1; } else { struct tavl_node *s; for (;;) { s = r->tavl_link[0]; if (s->tavl_tag[0] == TAVL_THREAD) break; r = s; } if (s->tavl_tag[1] == TAVL_CHILD) r->tavl_link[0] = s->tavl_link[1]; else { r->tavl_link[0] = s; r->tavl_tag[0] = TAVL_THREAD; } s->tavl_link[0] = p->tavl_link[0]; if (p->tavl_tag[0] == TAVL_CHILD) { struct tavl_node *t = p->tavl_link[0]; while (t->tavl_tag[1] == TAVL_CHILD) t = t->tavl_link[1]; t->tavl_link[1] = s; s->tavl_tag[0] = TAVL_CHILD; } s->tavl_link[1] = p->tavl_link[1]; s->tavl_tag[1] = TAVL_CHILD; q->tavl_link[dir] = s; s->tavl_balance = p->tavl_balance; q = r; dir = 0; } } tree->tavl_alloc->libavl_free (tree->tavl_alloc, p);