Red-Black Tree - 2

레드 블랙 트리의 기본 연산

레드 블랙 트리는 이진 탐색 트리입니다. 그렇기 때문에 레드 블랙 트리에서의 탐색은 이진 탐색 트리에서처럼 이진 탐색을 그대로 사용하면 됩니다. 이 내용은 전 글에서 설명을 했었었죠. 문제는 삽입과 삭제입니다. 노드를 트리에 삽입을 하거나 삭제를 할 때 이진 트리처럼 해버리면 레드 블랙 트리의 규칙이 무너지기 때문입니다.

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

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

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

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

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

전 글에서 보았던 레드 블랙 트리의 규칙입니다.

이렇게 레드 블랙 트리에 노드를 그냥 삽입이나 삭제를 하게되면 규칙이 무너지게 되는데 이를 위 5가지 규칙에 맞게끔 바로 잡아주어야합니다. 이점이 바로 레드 블랙 트리의 핵심입니다.

결론적으로 말하면 레드 블랙 트리에 노드가 삽입이나 삭제가 될 때에는 보통 이진 트리와 똑같지만 삽입이나 삭제 후 무너진 규칙을 바로 잡아주는 연산(뒤처리)을 해야한다는 것입니다. 이것을 뒤처리 작업이라고 하겠습니다.

회전

이러한 뒤처리 작업을 하기 전에 알아야할 내용이 있습니다. 바로 레드 블랙 트리의 기초 초식인 '회전(Rotate)' 입니다. 회전은 부모-자식 노드의 위치를 서로 바꾸는 연산을 뜻합니다. 회전은 방향에 따라 우회전(Right-Rotate)과 좌회전(Left-Rotate)로 나뉩니다.

우회전 : 왼쪽 자식 노드와 부모의 위치를 교환하는 것

좌회전 : 오른쪽 자식 노드와 부모의 위치를 교환하는 것

부모의 입장에서 보았을 때 우회전 좌회전 인 것 같습니다..;;

이처럼 됩니다.

위 과정은 생각보다 간단하지가 않습니다. 이진 탐색 트리의 특성상 왼쪽 자식 노드는 부모 노드보다 작고, 오른쪽 자식 노드는 부모노드보다 커야하는데 단순히 부모-자식 노드의 위치만 바꾸면 레드 블랙 트리가 아닌 아진 탐색 트리의 조건마저도 무너지게 됩니다. 이러한 문제를 일으키지 않으려면 다음과 같이 자식 노드를 처리해 주어야합니다.

우회전을 할 때에는 왼쪽 자식 노드의 오른쪽 자식 노드를 부모 노드의 왼쪽 자식으로 연결해야합니다.

좌회전을 할 때에는 오른쪽 자식 노드의 왼쪽 자식 노드를 부모 노드의 오른쪽 자식으로 연결해야합니다.

아래는 위 설명을 그대로 실천한 코드입니다. ( 책 예제코드를 그대로 따라쳤습니다. )

void RBT_RotateRight( PRBTNode* Root, PRBTNode Parent ) //************************************ // 오른쪽 회전 함수 // Returns: void // // Parameter: PRBTNode * Root 자식 노드(부모노드 기준 왼쪽) // Parameter: PRBTNode Parent 부모노드 //************************************ { PRBTNode LeftChild = Parent->Left; // 왼쪽 자식 노드의 오른쪽 자식 노드를 부모 노드의 왼쪽 자식으로 등록 Parent->Left = LeftChild->Right; if( LeftChild->Right != Nil ) LeftChild->Right->Parent = Parent; LeftChild->Parent = Parent->Parent; // 부모가 NULL 이라면 이 노드는 Root 이다. // 이 경우에는 왼쪽 자식을 Root 노드로 만들어 회전시킨다. if( Parent->Parent == NULL ) *Root = LeftChild; else { // 왼쪽 자식 노드를 부모 노드가 있던 곳(할아버지의 자식 노드)에 위치시킨다. if( Parent == Parent->Parent->Left ) Parent->Parent->Left = LeftChild; else Parent->Parent->Right = LeftChild; } LeftChild->Right = Parent; Parent->Parent = LeftChild; } void RBT_RotateLeft( RBTNode** Root, RBTNode* Parent ) //************************************ // 왼쪽 회전 함수 // Returns: void // // Parameter: PRBTNode * Root 자식 노드(부모노드 기준 오른쪽) // Parameter: PRBTNode Parent 부모노드 //************************************ { RBTNode* RightChild = Parent->Right; Parent->Right = RightChild->Left; if ( RightChild->Left != Nil ) RightChild->Left->Parent = Parent; RightChild->Parent = Parent->Parent; if ( Parent->Parent == NULL ) (*Root) = RightChild; else { if ( Parent == Parent->Parent->Left ) Parent->Parent->Left = RightChild; else Parent->Parent->Right = RightChild; } RightChild->Left = Parent; Parent->Parent = RightChild; }

코드만 쭉 보면 잘 이해가 안갈 수도 있는데 결국 위 설명처럼 회전을 하게 됩니다. 전 잘 이해가 안가서 코드를 따라가면서 종이에 직접 그려봤네요 ㅎㅎ

이제 이러한 회전을 가지고 노드의 삽입과 삭제를 알아보겠습니다.