struct rtavl_node *x = y->rtavl_link[0]; assert (x != NULL); if (x->rtavl_balance == +1) { struct rtavl_node *w; assert (x->rtavl_balance == +1); w = x->rtavl_link[1]; x->rtavl_link[1] = w->rtavl_link[0]; w->rtavl_link[0] = x; y->rtavl_link[0] = w->rtavl_link[1]; w->rtavl_link[1] = y; if (w->rtavl_balance == -1) x->rtavl_balance = 0, y->rtavl_balance = +1; else if (w->rtavl_balance == 0) x->rtavl_balance = y->rtavl_balance = 0; else /* |w->rtavl_balance == +1| */ x->rtavl_balance = -1, y->rtavl_balance = 0; w->rtavl_balance = 0; if (x->rtavl_link[1] == NULL) { x->rtavl_rtag = RTAVL_THREAD; x->rtavl_link[1] = w; } if (w->rtavl_rtag == RTAVL_THREAD) { y->rtavl_link[0] = NULL; w->rtavl_rtag = RTAVL_CHILD; } pa[k - 1]->rtavl_link[da[k - 1]] = w; } else { pa[k - 1]->rtavl_link[da[k - 1]] = x; if (x->rtavl_balance == 0) { y->rtavl_link[0] = x->rtavl_link[1]; x->rtavl_link[1] = y; x->rtavl_balance = +1; y->rtavl_balance = -1; break; } else /* |x->rtavl_balance == -1| */ { if (x->rtavl_rtag == RTAVL_CHILD) y->rtavl_link[0] = x->rtavl_link[1]; else { y->rtavl_link[0] = NULL; x->rtavl_rtag = RTAVL_CHILD; } x->rtavl_link[1] = y; y->rtavl_balance = x->rtavl_balance = 0; } }