struct rtavl_node *x = y->rtavl_link[1]; assert (x != NULL); if (x->rtavl_balance == -1) { struct rtavl_node *w; assert (x->rtavl_balance == -1); w = x->rtavl_link[0]; x->rtavl_link[0] = w->rtavl_link[1]; w->rtavl_link[1] = x; y->rtavl_link[1] = w->rtavl_link[0]; w->rtavl_link[0] = 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 (y->rtavl_link[1] == NULL) { y->rtavl_rtag = RTAVL_THREAD; y->rtavl_link[1] = w; } if (w->rtavl_rtag == RTAVL_THREAD) { x->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[1] = x->rtavl_link[0]; x->rtavl_link[0] = y; x->rtavl_balance = -1; y->rtavl_balance = +1; break; } else /* |x->rtavl_balance == +1| */ { if (x->rtavl_link[0] != NULL) y->rtavl_link[1] = x->rtavl_link[0]; else y->rtavl_rtag = RTAVL_THREAD; x->rtavl_link[0] = y; y->rtavl_balance = x->rtavl_balance = 0; } }