한빛미디어

(길게 한 차례 썼었는데, 브라우저 오류로 날라가고, 다시 한번 씁니다 ^^;) 안녕하세요, 박상현입니다.
답변이 늦어 대단히 죄송합니다.

먼저 두 독자분께서 문의하신 이중 흑색 노드의 [형제 노드가 빨간색인 경우]의 예시 그림은 다음과 같이 변경되어야 합니다.


또한, P262의 가장 아래 단락의 설명 중 다음 부분은

"이중 흑색 노드의 형제가 빨간색인 경우에는 먼저 형제를 검은색, 부모를 빨간색으로 칠합니다. 그 다음에는 부모를 기준으로 좌회전하고 이중흑색 노드를 검은색으로 칠하면 뒤처리가 끝납니다. "

다음과 같이 수정되어야 합니다.

"이중 흑색 노드의 형제가 빨간색인 경우에는 먼저 형제를 검은색, 부모를 빨간색으로 칠합니다. 그 다음에는 부모를 기준으로 좌회전합니다.하고 이중흑색 노드를 검은색으로 칠하면 뒤처리가 끝납니다. 이렇게 해도 여전히 이중 흑색 노드는 그대로 남아 있지만, 형제 노드는 검은색 노드로 바뀌어 있습니다. 문제의 유형이 "빨간색 형제"에서 "검은색 형제"로 바뀐 것이죠. 이제부터 이중 흑색 노드는 다음 섹션부터 설명할 2-A, 2-B, 2-C 케이스에 따라 처리를 하면됩니다."


한 가지 더 있습니다. 논리적 오류는 아닌데, 본문의 예제 코드에 불필요한 부분이 있어서요.
RedBlackTree 예제의 RebuildAfterRemove() 함수를 다음과 같이 수정해 주세요.

void RBT_RebuildAfterRemove( RBTNode** Root, RBTNode* Successor )
{
    RBTNode* Sibling = NULL;
 
    while ( Successor->Parent != NULL && Successor->Color == BLACK)
    {
        if ( Successor == Successor->Parent->Left )
        {
			Sibling = Successor->Parent->Right;
            if ( Sibling->Color == RED )
            {
                printf("Sibling(%d) Color is Red.\n", Sibling->Data);
                Sibling->Color = BLACK;
                Successor->Parent->Color = RED;
                RBT_RotateLeft( Root, Successor->Parent );
				/* 아래의 코드는 아무 의미가 없으므로 삭제합니다. */
                /*Sibling = Successor->Parent->Right;*/
            }
            else
            {
                /* 기존의 내용과 동일합니다. */
            }            
        } 
        else
        {
            Sibling = Successor->Parent->Left;
			
            if ( Sibling->Color == RED )
            {
                printf("Sibling(%d) is RED.\n", Sibling->Data);
                Sibling->Color           = BLACK;
                Successor->Parent->Color = RED;
                RBT_RotateRight( Root, Successor->Parent );
                /* 아래의 코드는 아무 의미가 없으므로 삭제합니다. */
				/* Sibling = Successor->Parent->Left; */
            }
            else
            {
               /* 기존의 내용과 동일합니다. */
            }
        }
    }
 
    Successor->Color = BLACK;
}