레드 블랙 트리

// n, n부모, n부모부모 노드로 리스트럭쳐링을 수행한다.  
// 리스트럭쳐링 완료 후의 중간 노드를 반환한다.  
template <class T>  
CRBNode<T> \*CRBTree<T>::\_trirest(RBNode \*n)  
{  
    RBNode    \*l, \*r;  
    RBNode    \*pn, \*ppn;  
    RBNode    \*pppn;  
    RBNode    \*mid;  
 
    ASSERT(n != NULL);  
    ASSERT(n->parent() != NULL);  
    ASSERT(n->parent()->parent() != NULL);  
 
    pn = n->parent();  
    ppn = pn->parent();  
    pppn = ppn->parent();  
 
    // 다음과 같은 두 단계에 걸쳐서 트라이노드 리스트럭쳐링을 한다.  
    //   
    // 1. 세 노드의 링크 기준을 판별하여, 적절하게   
    // 2. 세 노드중 부모노드가 된 mid의 부모를 연결한다.  
 
    // 1단계:  
    // 트라이 노드 리스트럭쳐링에는 총 네가지 경우가 있다.  
 
    if(ppn->left() == pn)  
    {  
 
        if(pn->left() == n)  
        {  
            // 1번 경우  
            //     pp  
            //    /  
            //   p  
            //  /  
            // c  
            ppn->left(pn->right());  
            pn->right(ppn);  
            mid = pn;  
        }  
        else  
        {  
            // 2번 경우  
            //     pp  
            //    /  
            //   p  
            //    \  
            //     c  
 
            l = n->left();  
            r = n->right();  
 
            n->left(pn);  
            n->right(ppn);  
            pn->right(l);  
            ppn->left(r);  
            mid = n;  
        }  
    }  
    else  
    {  
        if(pn->left() == n)  
        {  
            // 3번 경우  
            // pp  
            //  \  
            //   p  
            //  /  
            // c  
 
            l = n->left();  
            r = n->right();  
 
            n->left(ppn);  
            n->right(pn);  
            ppn->right(l);  
            pn->left(r);  
            mid = n;  
        }  
        else  
        {  
            // 4번 경우  
            // pp  
            //  \  
            //   p  
            //    \  
            //     c  
 
            ppn->right(pn->left());  
            pn->left(ppn);  
            mid = pn;  
        }  
    }  
 
    // 2단계:  
    // 이 단계에서는 mid를 기준으로 아래와 같은 형태로  
    // 리스트럭쳐링이 완료되었다.  
    //  
    //       mid  
    //      /   \  
    //    left   right  
    //  
    // 남은 작업은 pp의 부모노드의 링크를 mid로 연결 시켜주는 것이다.  
 
    if(pppn)  
    {  
        // ppp로 부모가 넘어온 경우  
        // ppp의 자식 링크로 mid를 가리키도록 설정한다.  
        if(pppn->right() == ppn)  
            pppn->right(mid);  
        else  
            pppn->left(mid);  
    }  
    else  
    {  
        // ppp가 없는 경우 pp가 루트 였으므로  
        // mid를 루트로 변경해 준다.  
        \_set\_root(mid);  
    }  
 
    return mid;  
}