Red-Black Tree - 3

레드 블랙 트리의 노드 삽입

이 전 포스팅에서도 말했지만 이진 탐색을 통해 삽입할 노드를 찾고 여기에 새 노드를 자식 노드로 연결한다는 점에서 레드 블랙 트리와 이진 탐색 트리의 노드 삽입 연산은 많이 비슷합니다. 하지만 다른점이 무엇인지 아시겠죠?

이진 탐색 트리는 노드를 트리 안에 넣어 놓으면 그것으로 연산이 완료되지만, 레드 블랙 트리는 노드 삽입 후 규칙이 무너졌을 경우 규칙들에 맞게 트리를 바로 잡아 주어야합니다.

레드 블랙 트리에 새 노드가 삽입되고 나면 이 노드를 빨간색으로 칠한 다음 양쪽 자식에 NIL 노드를 연결해야합니다. 아래서 볼 코드에서 RBT_InsertNode() 함수는 먼저 이진 탐색을 통해 새 노드를 트리에 삽입(RBT_InsertNodeHelper() 함수)한 다음, 이 노드를 빨간색으로 칠하고 양쪽 자식에 NIL 노드를 연결합니다. 마지막으로 조금 전에 수행한 작업 때문에 무너진 레드 블랙 트리의 규칙을 복구(RBT_RebuildAfterInsert() 함수) 합니다.

void RBT_InsertNode( RBTNode** Tree, RBTNode* NewNode ) { // 이진 탐색 트리의 노드 삽입을 수행한다. RBT_InsertNodeHelper( Tree, NewNode ); // 삽입된 새 노드를 빨간색으로 칠하고 각각의 자식 노드는 NIL을 연결한다. // NIL 노드는 RBT 구현의 편의를 위해 도입된 개념이라 실제로 데이터를 담는 곳은 아님. NewNode->Color = RED; NewNode->Left = Nil; NewNode->Right = Nil; // 무너진 레드 블랙 트리 규칙을 바로 잡는다. RBT_RebuildAfterInsert( Tree, NewNode ); }

이렇게 말이죠. 위 코드를 보면 새로 삽입된 노드의 왼쪽 오른쪽 자식노드를 각각 NIL노드로 채워주고 주고 있는데 

저 NIL 노드는 

RBTNode* Nil;

이런식으로 전역변수로 선언되어 있으며 그렇기 때문에 매번 새로운 노드가 생길 때마다 NIL 노드를 생성해줄 필요가 없습니다. 만약 매번 새로운 노드가 삽입될 때마다 2개의 NIL노드를 생성한다면 저장 공간의 큰 낭비가 발생되겠지요.

왼쪽은 우리가 머리속으로 이해하고 있으면 되는 그림이고 오른쪽은 실제로 프로그램에서 사용되는 저장공간 그림입니다. 뭐 결국 NIL로 인한 저장공간 걱정은 안해도 된다는 것 입니다.

다시 본론으로 들어와서 삽입 후 무너진 규칙에 대해 다시 복구를 해야되는데 다시 한번 레드 블랙 트리의 규칙을 보겠습니다.

1. 모든 노드는 빨간색 아니면 검은색이다.

2. 루트 노드는 검은색이다.

3. 잎 노드는 검은색이다.

4. 빨간 노드의 자식들은 모두 검은색이다. 하지만 검은색 노드의 자식이 빨간색일 필요는 없다.

5. 루트 노드에서 모든 잎 노드 사이에 있는 검은색 노드의 수는 모두 동일하다.

위 규칙 중에서 모든 노드가 빨간색 또는 검은색이어야 한다는 규칙은 절대 위배될리 없겠죠. 그리고 모든 잎 노드는 모두 검은색이어야 한다는 규칙도 새 노드를 삽입할 때마다 검은색인 NIL 노드를 자식 노드로 붙히기 때문에 위배되지 않습니다. 또 마지막 규칙인 "루트 노드에서 모든 잎 노드 사이에 있는 검은색 노드의 수는 모두 동일하다" 라는 규칙도 새 노드(빨간색)를 삽입할 때에는 부모 노드에 연결되어 있는 NIL 노드(검은색)을 떼어내고 그 자리에 연결을 하므로 역시 위배되지 않습니다.

고로 위 5개의 규칙 중에 무너질 수 있는 규칙은 2,4 번입니다. 하지만 그 중에서도 2번인 "루트 노드는 검은색이다" 라는 규칙은 루트 노드를 무조건 검은색으로 칠하면 되니까 처리가 간단합니다. 그러면 이제 남은 규칙은 4번!!

"빨간 노드의 자식들은 모두 검은색이다"

위 규칙만 처리하면 삽입은 끝나게 됩니다. 쫌 골치아픈데 알아보도록 하죠.

이 규칙이 위반되었다는 것은 삽입한 노드와 부모 노드의 색이 모두 빨간색이라는 사실을 의미합니다. 이 상황은 삽입한 노드의 삼촌(부모 노드의 형제 노드)이 어떠한 색이냐에 따라 그 경우가 세 가지로 다시 나뉘어집니다. 여기서 삼촌 노드는 부모 노드의 둘도 없는 형제 노드입니다. 레드 블랙 트리는 자식 노드가 둘 뿐인 이진 트리니까요.

부모 노드가 할아버지 노드의 왼쪽 자식일 때 4번 규칙을 위반하는 세 가지 경우는 다음과 같습니다. 부모 노드가 할아버지 노드의 오른쪽 자식일 때는 이 규칙에서 왼쪽/오른쪽을 바꿔주면 됩니다.

①. 삼촌도 빨간색인 경우

②. 삼촌이 검은색이며 새로 삽입한 노드가 부모 노드의 오른쪽 자식인 경우

③. 삼촌이 검은색이며 새로 삽입한 노드가 부모 노드의 왼쪽 자식인 경우

위 3가지 경우를 전부 처리해주어야합니다.

① 삼촌도 빨간색인 경우

삼촌도 빨간색인 경우에는 부모 노드와 삼촌 노드를 검은색으로 칠하고, 할아버지 노드를 빨간색으로 칠하면 됩니다.

이와 같이 말이죠. 하지만 이렇게 되면 삼촌이 빨간색인 경우에 대한 후속처리를 끝났지만, 이 작업으로 인해 생긴 부작용이 없는지 살펴봐야합니다. 할아버지 노드를 빨간색으로 칠함으로 인해 4번 규칙이 또 다시 위협받기 때문입니다. 그래서 할아버지 노드를 새로 삽입한 노드로 간주하고 다시 처음부터 4번 규칙을 위반하는 세 가지 경우를 따져봐야합니다.

위 그림을 보면 새로 삽입한 노드 때문에 부모 노드, 삼촌 노드, 할아버지 노드 색을 전부 바꿨는데 할아버지 노드 색을 빨간색으로 바꿈으로 인해 할아버지의 부모 노드와 같은 빨간색이 되버렸습니다. 또 4번 규칙을 위반하게 된 것이지요. 한편, 할아버지 노드의 문제를 해결한다고 하더라도 할아버지의 할아버지가 빨간색이라면 4번 규칙이 또 다시 위협받을 수 있겠죠? 이러한 4번 규칙의 굴레는 계속 족보를 타고 위로 올라가서 부모 노드가 검은색이거나 새로 삽입한(또는 새로 삽입한 것으로 간주한) 노드가 루트여야 비로소 벗을 수 있습니다.

코드는 한꺼번에 보도록하고 두번째 경우를 보겠습니다.

② 삼촌이 검은색이며 새로 삽입한 노드가 부모 노드의 오른쪽 자식인 경우

위 경우는 부모 노드를 왼쪽으로 회전시켜 이 상황을 세 번째 경우의 문제로 바꿉니다.

이번 경우에는 문제의 유형을 바꾼 것이지, 문제가 해결된 것은 아니라는 점을 주의해야 합니다. 문제가 세 번째 경우로 바뀌면서 새로 삽입한 노드 D가 부모가 되고 부모 노드 였던 B가 자식이 되었습니다.

첫 번째 경우를 처리한 다음에 할아버지 노드를 새로 삽입한 노드로 간주했던 것처럼, 이번에는 부모였던 노드를 새로 삽입한 노드로 간주시키고 세 번째 경우의 문제로 현재 상황을 넘깁니다.

③ 삼촌이 검은색이며 새로 삽입한 노드가 부모 노드의 왼쪽 자식인 경우

삼촌이 검은색이고 삽입한 노드가 부모 노드의 왼쪽 자식인 경우에는 부모 노드를 검은색, 할아버지 노드를 빨간색으로 칠한다음 할아버지 노드를 오른쪽으로 회전시킵니다.

이제 위 과정까지 전부 처리하게 되면 4번 규칙이 위반되지 않습니다.

새로 삽입한 노드 B의 부모 D가 검은색이기 때문입니다. D에게 부모가 있었다고 간주해 봅시다. 그 부모 노드의 색이 빨간색이어도 검은색이어도 여전히 4번 규칙은 위반되지 않습니다. 드디어 4번 규칙의 굴레를 벗을 수 있게 된 것입니다.

지금까지 설명한 내용을 코드로 보겠습니다.

void RBT_RebuildAfterInsert( RBTNode** Root, RBTNode* X ) { // "빨간 노드의 자식들은 모두 검은색이다." 라는 규칙이 전부 만족 할 때까지 돎. while( X != (*Root) && X->Parent->Color == RED ) { // 부모 노드가 할아버지 왼쪽 자식인 경우 if( X->Parent == X->Parent->Parent->Left ) { RBTNode* Uncle = X->Parent->Parent->Right; // 삼촌이 빨간색인 경우 if( Uncle->Color == RED ) { X->Parent->Color = BLACK; Uncle->Color = BLACK; X->Parent->Parent->Color = RED; // 할아버지 노드를 기준 노드로 바꿈 X = X->Parent->Parent; } else { // 삼촌이 검은색이고 X가 부모의 오른쪽 자식인 경우 if( X == X->Parent->Right ) { // 부모 노드를 좌회전 시켜 상황 바꿈 X = X->Parent; RBT_RotateLeft( Root, X ); } X->Parent->Color = BLACK; X->Parent->Parent->Color = RED; RBT_RotateRight( Root, X->Parent->Parent ); } } // 부모 노드가 할아버지 오른쪽 자식인 경우 else { RBTNode* Uncle = X->Parent->Parent->Left; if ( Uncle->Color == RED ) { X->Parent->Color = BLACK; Uncle->Color = BLACK; X->Parent->Parent->Color = RED; X = X->Parent->Parent; } else { if ( X == X->Parent->Left ) { X = X->Parent; RBT_RotateRight( Root, X ); } X->Parent->Color = BLACK; X->Parent->Parent->Color = RED; RBT_RotateLeft( Root, X->Parent->Parent ); } } } (*Root)->Color = BLACK; }

코드는 위 세 가지 규칙을 잘 보면서 읽어보면 금방 이해되실 것 입니다.

이제 마지막으로 대망의 삭제가 남았군요.. 다음 포스팅에서 알아보겠습니다.