[자료구조] 레드 블랙 트리(Red Black Tree) - 코딩밥상
레드 블렉 트리란?
앞서 공부한 것처럼 순수한 이진 탐색 트리는 가지들이 불균형하게 자라는 경우가 많고 이는 이진 탐색 트리의 높이를 높여서 검색 효율을 심각하게 저하시키기 때문에 문제가 됩니다.
데이터가 아무리 많이 입력되어도 이진 탐색 트리가 균형 있게 성장해서 그 높이가 최소한으로 유지되도록 하는 특별한 이진 탐색 트리가 바로 레드 블렉 트리입니다.
그 방법으로 노드를 빨간색과 검은색으로 구분하여 이러한 이름이 붙여진 것입니다.
이 특별한 트리의 구조체 먼저 알아보자면,
typedef struct tagRBTNode{
struct tagRBTNode* Parent;
struct tagRBTNode* Left;
struct tagRBTNode* Right;
enum {RED, BlACK} Color;
ElementType Data;
} RBTNode;Color필드 뿐만 아니라 이진 트리의 노드에 없던 Parent포인터도 있습니다. 이는 삽입과 삭제 연산을 수행할 때 사용됩니다.
그림을 보면 잎 노드가 모두 NIL로 표시되어 있습니다. NIL노드는 아무 데이터를 갖지 않지만 색깔만 검은색 더미 노드입니다.
이를 센티넬(Sentinel) 노드라고 하는데, 레드 블렉 트리 구현을 용이하게 만들기 위해서 이렇게 구현합니다.
원래의 잎 노드들에 검은색이든 빨간ㄴ색이든 NIL노드를 양쪽 자식으로 연결하면 '모든 잎 노드는 검은색이다'라는 규칙 하나는 항상 지킬 수 있게 때문입니다. 후에 구현하는 과정에서 더욱 체감 할 수 있을 것입니다.
레드 블랙 트리의 구현 규칙
- 모든 노드는 빨간색이거나 검은색이다.
- 뿌리 노드는 검은색이다.
- 잎 노드는 검은색이다.
- 빨간색 노드의 자식은 모두 검은색이다.(검은색 노드는 빨간색과 검은색을 모두 자식으로 가질 수 있다.)
- 뿌리 노드와 모든 잎 노드 사이에 있는 검은색 노드의 수는 모두 동일하다.
기본 연산 및 구현
레드 블랙 트리는 이진 탐색 트리입니다. 따라서 탐색 알고리즘은 이진 탐색 트리와 거의 동일 하지만 어떤 노드를 삽입하거나 삭제하면 레드 블랙 트리의 규칙을 위반하는 상황이 생기기 때문에 삽입과 삭제 이후의 '뒤처리' 과정이 주된 필요합니다.
회전 연산
레드 블랙 트리 연산의 기초 초식은 바로 이 '회전(Rotation)'연산 입니다. 이는 부모와 자식 노드의 위치를 서로 바꾸는 연산입니다.
회전 방향에 따라 왼쪽 자식과 부모의 위치를 바꾸면 '우회전' 오른쪽 자식과 부모의 위치를 바꾸면 '좌회전'으로 나뉩니다.
단순히 부모와 자식 노드의 위치만 바꾸면 이진 탐색 조건마저 무너뜨리게 되기에 다음과 같이 자식 노드를 처리해줘야 합니다.
- 우회전 할 때는 왼쪽 자식 노드의 오른쪽 자식 노드를 부모 노드의 왼쪽 자식으로 연결
- 좌회전 할 때는 오른쪽 자식 노드의 왼쪽 자식 노드를 부모 노드의 오른쪽 자식으로 연결
void RBT_RotateRight(RBTNode** Root, RBTNode* Parent){
RBTNode* LeftChild = Parent->Left; //왼쪽 자식 노드의 오른쪽 자식 노드를 부모 노드의 왼쪽 자식으로 등록
Parent->Left = LeftChild->Right;
if(LeftChild->Right != Nil){
LeftChild->Right->Parent = Parent;
}
LeftChild->Parent = Parent->Parent; //왼쪽 자식 노드를 부모 노드로 바꿈
if(Parent->Parent == NULL) //루트 노드를 회전시키는 경우
(*Root) == LeftChild;
else{
if(Parent == Parent->Parent->Left){ //바꾸는 부모 노드가 할아버지 노드의 왼쪽 or 오른쪽 자식이었을 경우 나뉨
Parent->Parent->Left = LeftChild;
}
else
Parent->Parent->Right = LeftChild;
}
LeftChild->Right = Parent;
Parent->Parent = LeftChild;
}우회전의 경우
먼저 왼쪽 노드의 오른쪽 자식과 부모 노드를 연결하고,
왼쪽 노드를 부모노드의 부모 노드와 연결을 새로 해줍니다.
좌회전의 경우는 우회전의 경우와 왼쪽 오른쪽만 반대로 해주면 동작하게 됩니다.
노드 삽입 연산
이진 탐색으로 삽일할 장소를 찾고 새 노드를 자식 노드로 연결한다는 점까지 일반적인 이진 탐색 트리의 노드 삽입과 같지만 레드 블랙 트리는 노드 삽입 후에 무너졌을지도 모르는 규칙들을 살펴봐야 합니다. '뒤처리 과정'을 해줘야 하는 것이죠.
레드 블랙 트리에 새 노드를 삽입하면 삽입하는 노드를 빨간색으로 칠한 다음 NIL 노드를 이 노드의 양쪽 자식으로 연결해야 합니다.
void RBT_InsertNode(RBTNode** Tree, RBTNode* NewNode){
BST_InsertNode(Tree, NewNode); //이진 탐색 트리의 노드 삽입(탐색 후 노드 삽입)
NewNode->Color = RED; //삽입 노드는 빨간색으로, 자식 노드는 더미 노드에 연결
NewNode->Left = Nil; //여기서 Nil을 항상 생성해 주는 것이 아니라 더미 노드 하나에 연결하는 방식
NewNode->Right = Nil;
RBT_RebuildAfterInsert(Tree,NewNode);
}노드 삽입 후 Rebuilding 과정에서 생각할 부분이 조금 있습니다.
위반 될 수 있는 규칙은 '뿌리 노드는 검은색이어야 한다'와 '빨간색 노드의 자식들은 모두 검은색이다' 두 가지인데,
'뿌리 노드는 검은색이어야 한다'는 규칙은 뿌리 노드를 무조건 검은색으로 칠해주면 뒤처리가 끝납니다.
나머지 규칙인 '빨간색 노드의 자식들은 모두 검은색이다' 조건에 대하여 생각할 부분이 있는데,
이 규칙이 위반되었다면 삽입한 노드와 부모 노드의 색이 모두 빨간색이라는 뜻입니다. 이 상황은 삽입한 노드의 삼촌(부모 노드의 형제 노드)이 어떤 색인가에 따라 다시 세 가지 경우로 나뉩니다.
- 삼촌도 빨간색인 경우
- 삼촌이 검은색이며 새로 삽입한 노드가 부모 노드의 오른쪽 자식인 경우
- 삼촌이 검은색이며 새로 삽입한 노드가 부모 노드의 왼쪽 자식인 경우
-'삼촌도 빨간색인 경우'
부모 노드와 삼촌 노드를 검은색으로 칠하고 할아버지 노드(부모 노드의 부모 노드)를 빨간색으로 칠하면 됩니다.
그 후에 할아버지 노드를 새로 삽입한 노드로 간주하고 다시 처음부터 규칙을 위반하는지 부모 노드가 검은 색이거나 새로 삽입한 노드가 뿌리일 때까지 올라가며 Rebuilding과정을 거쳐야 합니다.
-'삼촌이 검은색이며 새로 삽입한 노드가 부모 노드의 오른쪽 자식인 경우'
부모 노드를 자회전 시켜 부모 노드와 삽입 노드를 바꾸고 삽입 노드의 왼쪽에 기존 부모 노드가 오게 바꿉니다.
이렇게 되면 3번째 상황으로 바뀌게 됩니다. 즉 2번째 상황을 3번째 상황으로 바꿔 해결되는 것입니다.
-'삼촌이 검은색이며 새로 삽입한 노드가 부모 노드의 왼쪽 자식인 경우'
부모 노드를 검은색, 할어버지 노드를 빨간색으로 칠한 다음 할아버지 노드를 우회전시킵니다.
이 연산을 하면 드디어 Rebuilding굴레에서 벗어날 수 있습니다.
void RBT_RebuildAfterInsert(RBTNode** Root, RBTNode* X){
while(X != (*Root) && X->Parent->Color == RED){
if(X->Parent == X->Parent->Parent->Left){ //부모 노드가 왼쪽 자식일 경우
RBTNode* UncleR = X->Parent->Parent->Right;
if(UncleR->Color == RED){ //삼촌도 빨간색인 경우(1번)
X->Parent->Color = BLACK;
UncleR->Color = BLACK;
X->Parent->Parent->Color = RED;
X = X->Parent->Parent;
}
else{
if(X == X->Parent->Right){ //삼촌이 검은색이며 새로 삽입한 노드가 부모 노드의 오른쪽 자식인 경우(2번) -> 3번으로 변환
X = X->Parent;
RBT_RotateLeft(Root, X);
}
X->Parent->Color = BLACK; //삼촌이 검은색이며 새로 삽입한 노드가 부모 노드의 왼쪽 자식인 경우(3번)
X->Parent->Parent->Color = RED;
RBT_RotateRight(Root, X->Parent->Parent);
}
}
else{ //부모 노드가 오른쪽 자식일 경우
//왼쪽 자식의 코드에서 왼쪽과 오른쪽을 바꾸면 됨
RBTNode* UncleL = X->Parent->Parent->Right;
if(UncleL->Color = RED){
X->Parent->Color = BLACK;
UncleL->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);
}
}
}
}
삭제 연산
레드 블랙 트리의 삭제 연산 또한 일반 이진 탐색 트리의 삭제 연산을 뼈대로 두고 레드 블랙 트리의 규칙에 어긋나지 않게 뒷수습을 하는 코드를 덧붙이면 됩니다.
만약 삭제되는 노드가 빨간색일 경우에는 규칙과 무관하기 때문에 뒷수습이 필요 없습니다.
문제는 검은색 노드를 삭제할 때입니다.
검은색 노드를 삭제하면 '뿌리 노드와 모든 잎 노드 사이에 있는 검은색 노드의 수는 모두 동일하다'라는 조건이 먼저 위반됩니다.
이는 삭제되는 검은색 노드를 대신할 노드가 빨간색일 경우 검은색으로 칠해주고 검은색일 경우 '이중 흑색'이라는 특이 노드로 취급합니다.
여기서 이중 흑색이란 검은색의 갯수를 2개로 취급하지만 검은색은 아닌 우리끼리 약속하는 개념적인색 이라고 생각하면 됩니다.
하지만 이중 흑색을 사용하면 '모든 노드는 빨간색이거나 검은색이다'라는 조건을 위반합니다.
다음과 같이 케이스를 나누어 이 조건을 만족시키도록하는 방법을 정리해 보겠습니다.
- 형제가 빨간색인 경우 => 형제를 검은색, 부모를 빨간색으로 칠합니다. 그 후 부모를 기준으로 자식 노드를 좌회전시킵니다. 그렇게 되면 형제가 검은색인 경우로 케이스가 바뀌게 됩니다.
- 형제가 검은색이고
- 형제의 양쪽 자식이 모두 검은색인 경우 => 형제 노드만 빨간색으로 칠한 후 이중 흑색 노드가 갖고 있던 2개의 검은색 중 하나를 부모 노드에게 넘겨줍니다.
- 형제의 왼쪽 자식은 빨간색, 오른쪽 자식은 검은색인 경우 => 형제 노드를 빨간색으로 칠하고 왼쪽 자식을 검은색으로 칠한 다음 형제 노드를 기준으로 우회전합니다.
- 형제의 오른쪽 자식이 빨간색인 경우 => 이중 흑색 노드의 부모 노드가 갖고 있는 색을 형제 노드에 칠합니다. 그 다음에 부모 노드와 형제 노드의 오른쪽 자식 노드를 검은색으로 칠하고 부모 노드를 기준로 좌회전합니다.
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){
Sibling->Color = BLACK;
Successor->Parent->Color = RED;
RBT_RotateLeft(Root, Successor->Parent);
}
else{
if(Sibling->Left->Color == BLACK && Sibling->Right->Color == BLACK){
Sibling->Color = RED;
Successor = Successor->Parent;
}
else{
if(Sibling->Left->Color == RED){
Sibling->Left->Color = BLACK;
Sibling->Color = RED;
RBT_RotateRight(Root, Sibling);
Sibling = Successor->Parent->Right;
}
Sibling->Color = Successor->Parent->Color;
Successor->Parent->Color = BLACK;
Sibling->Right->Color = BLACK;
RBT_RotateLeft(Root, Successor->Parent);
Successor = (*Root);
}
}
}
else{
//이중 흑색 노드가 부모 노드의 오른쪽 자식인 경우
}
}
}
RBTNode* RBT_RemoveNode(RBTNode** Root, ElementType Data){
RBTNode* Removed = NULL;
RBTNode* Successor = NULL;
RBTNode* Target = RBT_SearchNode((*Root), Data);
if(Target == NULL) return NULL;
if(Target->Left == Nil || Target->Right == Nil){
Removed = Target;
}
else{
Removed = RBT_SearchMinNode(Target->Right);
Target->Data = Removed->Data;
}
if(Removed->Left != Nil)
Successor = Removed->Left;
else
Successor = Removed->Right;
Successor->Parent = Removed->Parent;
if(Removed->Parent == NULL)
(*Root) = Successor;
else{
if(Removed == Removed->Parnet->Left)
Removed->Parent->Left = Successor;
else
Removed->Parent->Right = Successor;
}
if(Removed->Color == BLACK)
RBT_RebuildAfterRemove(Root, Successor);
return Removed;
}