if (p->rtavl_rtag == RTAVL_THREAD) { if (p->rtavl_link[0] != NULL) { struct rtavl_node *t = p->rtavl_link[0]; while (t->rtavl_rtag == RTAVL_CHILD) t = t->rtavl_link[1]; t->rtavl_link[1] = p->rtavl_link[1]; pa[k - 1]->rtavl_link[da[k - 1]] = p->rtavl_link[0]; } else { pa[k - 1]->rtavl_link[da[k - 1]] = p->rtavl_link[da[k - 1]]; if (da[k - 1] == 1) pa[k - 1]->rtavl_rtag = RTAVL_THREAD; } } else { struct rtavl_node *r = p->rtavl_link[1]; if (r->rtavl_link[0] == NULL) { r->rtavl_link[0] = p->rtavl_link[0]; if (r->rtavl_link[0] != NULL) { struct rtavl_node *t = r->rtavl_link[0]; while (t->rtavl_rtag == RTAVL_CHILD) t = t->rtavl_link[1]; t->rtavl_link[1] = r; } pa[k - 1]->rtavl_link[da[k - 1]] = r; r->rtavl_balance = p->rtavl_balance; da[k] = 1; pa[k++] = r; } else { struct rtavl_node *s; int j = k++; for (;;) { da[k] = 0; pa[k++] = r; s = r->rtavl_link[0]; if (s->rtavl_link[0] == NULL) break; r = s; } da[j] = 1; pa[j] = pa[j - 1]->rtavl_link[da[j - 1]] = s; if (s->rtavl_rtag == RTAVL_CHILD) r->rtavl_link[0] = s->rtavl_link[1]; else r->rtavl_link[0] = NULL; if (p->rtavl_link[0] != NULL) { struct rtavl_node *t = p->rtavl_link[0]; while (t->rtavl_rtag == RTAVL_CHILD) t = t->rtavl_link[1]; t->rtavl_link[1] = s; } s->rtavl_link[0] = p->rtavl_link[0]; s->rtavl_link[1] = p->rtavl_link[1]; s->rtavl_rtag = RTAVL_CHILD; s->rtavl_balance = p->rtavl_balance; } } tree->rtavl_alloc->libavl_free (tree->rtavl_alloc, p);