Algorithm/Theory

자료 구조 - 레드 블랙 트리

hyunipad 2021. 1. 7. 23:18
반응형

레드 블랙 트리는 불균형하게 성장한 이진 탐색 트리의 단점을 보완한 트리 구조입니다. 레드 블랙 트리가 이진 탐색 트리와 다른 점은 노드를 빨간색, 검은색으로 표시한다는 것입니다. 레드 블랙 트리는 다음과 같은 규칙을 따릅니다.

  1. 모든 노드는 빨간색 아니면 검은색이다.
  2. 루트 노드는 검은색이다.
  3. NIL(잎) 노드는 검은색이다.
  4. 빨간 노드의 자식들은 모두 검은색이다. 하지만 검은색 노드의 자식이 빨간색일 필요는 없다.
  5. 루트 노드에서 모든 NIL(잎) 노드 사이에 있는 검은색 노드의 수는 모두 동일하다. 

NIL 노드는 아무 데이터도 갖고 있지 않은 색깔만 검은색인 노드입니다. 굳이 NIL 노드를 사용하는 이유는 구현을 쉽게 하기 위해서입니다. NIL 노드를 양쪽 자식으로 연결해서 NIL 노드가 잎 노드가 되면 레드 블랙 트리의 규칙 3번을 항상 유지시킬 수 있습니다.

 

C언어에서의 RBTNode의 구조

typedef struct tagRBTNode {
	struct tagRBTNode* Parent;
	struct tagRBTNode* Left;
	struct tagRBTNode* Right;

	enum {RED, BLACK} Color;
	int Data
}RBTNode;

extern RBTNode* Nil;

위의 구조에서 extern RBTNode* Nil; 는 데이터가 존재하지 않기 때문에 저장 공간의 할당하여 사용하는 것은 낭비이기 때문에 전역 변수로 하나만 생성해서 새 노드를 생성할 때마다 동일한 NIL 노드를 사용합니다.

 

레드 블랙 트리의 연산

기본적으로 레드 블랙 트리의 연산은 이진 탐색 트리와 다르지 않습니다. 차이가 있다면 삽입과 삭제 후의 후처리의 차이점이 있습니다. 레드 블랙 트리의 후처리는 회전이라는 연산을 기본으로 합니다. 회전은 방향에 따라 좌회전과 우회전으로 나뉩니다.

 

 

아래는 회전 연산의 코드 예시입니다.

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) { // 부모가 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) {

	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->Right) { 
			Parent->Parent->Right = RightChild;
		}
		else {
			Parent->Parent->Left = RightChild;
		}

		RightChild->Left = Parent;
		Parent->Parent = RightChild;
	}
}

 

 

레드 블랙 트리의 삽입

레드 블랙 트리의 삽입은 다음과 같이 이루어집니다.

  1. 이진 탐색 트리와 같은 알고리즘으로 노드를 삽입한다.
  2. 좌,우 자식 & 색깔 변수 초기화
  3. 리빌딩 메서드를 통해 규칙을 유지한다.
void RBT_InsertNodeHelper(RBTNode** Tree, RBTNode* NewNode) {
	if ((*Tree) == NULL) { // 루트 노드가 널이면 새로운 노드가 루트 노드
		(*Tree) = NewNode;
	}

	if ((*Tree)->Data < NewNode->Data) { //새로운 노드의 데이터가 더 크면
		if ((*Tree)->Right == Nil) { // 오른쪽 비어 있으면
			(*Tree)->Right = NewNode; // 삽입
			NewNode->Parent = (*Tree); // 부모 노드가 루트 노드
		}
		else {
			RBT_InsertNodeHelper(&(*Tree)->Right, NewNode); // 오른쪽으로 재귀하여 빈 노드를 찾아 간다. 
		}
	}

	if ((*Tree)->Data > NewNode->Data) { //새로운 노드의 데이터가 더 작으면
		if ((*Tree)->Left == Nil) { // 왼쪽 비어 있으면
			(*Tree)->Left = NewNode; // 삽입
			NewNode->Parent = (*Tree); // 부모 노드가 루트 노드
		}
		else {
			RBT_InsertNodeHelper(&(*Tree)->Left, NewNode); // 오른쪽으로 재귀하여 빈 노드를 찾아 간다. 
		}
	}
}

void RBT_InsertNode(RBTNode** Tree, RBTNode* NewNode) {
	RBT_InsertNodeHelper(Tree, NewNode);

	NewNode->Color = RED;
	NewNode->Left = Nil;
	NewNode->Right = Nil;

	RBT_REbuildAfterInsert(Tree, NewNode); // 인서트 후에 리빌딩을 통하여 레드블랙트리의 규칙을 유지한다.
}

 

그럼 리빌딩에 대해 살펴보겠습니다.

노드를 삽입 후 위반 가능성이 있는 규칙은 "루트 노드는 검은색이어야 한다"와 "빨간 노드의 자식들은 모두 검은색이다" 두 가지입니다. 그중 "루트 노드는 검은색이어야 한다."는 간단합니다. 그냥 색깔을 바꿔 주기만 하면 됩니다.

 

"빨간 노드의 자식들은 모두 검은색이다" 만 남았습니다.

이 규칙은 새로 삽입한 노드의 부모의 노드색이 빨간색일 때 위반합니다.

이 규칙을 위반할 때는 3가지로 나눠서 리빌딩합니다.

  1. 삼촌도 빨간색인 경우
  2. 삼촌이 검은색이며 새로 삽입한 노드가 부모 노드의 오른쪽 자식인 경우
  3. 삼촌이 검은색이며 새로 삽입한 노드가 부모 노드의 왼쪽 자식인 경우

 

1. 삼촌도 빨간색인 경우

- 이 경우에는 부모 노드와 삼촌 노드를 검은색으로 칠하고, 할아버지 노드를 빨간색으로 칠하면 됩니다. 하지만 이 후속처리를 하고 난 뒤 할아버지의 할아버지 노드가 빨간색이라면 다시 규칙이 위반될 수 있기 때문에 거슬러 올라가 부모 노드가 검은색이거나 루트 노드까지 갔을 때 후속처리가 끝나게 됩니다.

 

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

- 2번, 3번에 경우는 2번에서 왼쪽 회전을 시켜 3번으로 만들어 한번에 후속 처리를 진행합니다.

 

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

- 이 경우에는 아래와 같은 과정으로 진행합니다.

 

 

이 세가지 경우를 모두 담은 코드입니다.

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) { // 1.삼촌 노드가 빨간색인 경우
				X->Parent->Color = BLACK; 
				Uncle->Color = BLACK;
				X->Parent->Parent->Color = RED;
				X = X->Parent->Parent;
			}
			else { // 삼촌 노드가 검은색인 경우
				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) { // 1.삼촌 노드가 빨간색인 경우
				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;
}

 

레드 블랙 트리의 삭제

레드 블랙 트리의 규칙은 다음과 같은 5가지입니다.

  1. 모든 노드는 빨간색 아니면 검은색이다.
  2. 루트 노드는 검은색이다.
  3. NIL(잎) 노드는 검은색이다.
  4. 빨간 노드의 자식들은 모두 검은색이다. 하지만 검은색 노드의 자식이 빨간색일 필요는 없다.
  5. 루트 노드에서 모든 NIL(잎) 노드 사이에 있는 검은색 노드의 수는 모두 동일하다. 

이 중에서 신경 써야 할 부분은 검은색 노드를 삭제했을 때입니다. 빨간색 노드를 삭제하는 경우에는 그냥 삭제해도 규칙에 위반되는 것이 없어 후처리를 할 필요가 없습니다. 하지만 검은색 노드를 삭제한 경우에는 5번의 규칙이 무너지게 됩니다. 이 위반된 규칙은 이중 흑색이라는 개념을 도입해 해결하게 됩니다.

*** 아래의 알고리즘들은 이중 흑색 노드가 부모 노드의 왼쪽 자식 노드일 때입니다. 오른쪽 자식 노드일 때는 코드에서 왼쪽/오른쪽을 모두 반대로 해주면 됩니다.

 

이증 흑색의 개념(C)

이렇게 이중흑색을 만든 다음 이 이중 흑색을 원래대로 되돌리는 후처리를 하면 삭제는 끝이 나게 됩니다.

그 경우에는 총 4가지의 경우가 있습니다.

  1. 형제가 빨간색인 경우
  2. 형제는 검은색이고
    1. 형제의 양쪽 자식이 모두 검은색인 경우
    2. 형제의 왼쪽 자식은 빨간색, 오른쪽 자식은 검은색인 경우
    3. 형제의 오른쪽 자식이 빨간색인 경우

 

하나하나 알아가보겠습니다.

 

1. 형제가 빨간색인 경우

 

먼저 형제를 검은색, 부모를 빨간색으로 칠합니다. 그 후 부모를 기준으로 좌회전합니다. 이 작업을 하면 경우의 수가

2번 케이스로 바뀌고, 2번 케이스에서 설명할 알고리즘 순서대로 다시 후처리를 진행합니다.

형제가 빨간색인 경우

 

2-1. 형제가 검은색이고 형제 자식이 모두 검은색인 경우

 

형제 노드만 빨간색으로 칠한 다음, 이중 흑색 노드가 갖고 있는 검은색 중 하나를 부모 노드에게 넘겨주면 됩니다.

그 후에 검은색 노드의 처리는 다시 4가지의 경우에 따라 후처리를 진행합니다.

 

2-2. 형제가 검은색이고 형제의 왼쪽 자식은 빨간색, 오른쪽 자식은 검은색인 경우

 

형제 노드를 빨간색으로 칠하고 왼쪽 자식을 검은색으로 칠한 다음, 형제 노드를 기준으로 우회전합니다. 그렇다면 2-2의 경우가 2-3의 경우로 바뀌게 됩니다.

 

2-3. 형제가 검은색이고 형제의 오른쪽 자식이 빨간색인 경우

 

이중 흑색 노드의 부모 노드가 갖고 있는 색을 형제 노드에 칠합니다. 그다음 부모 노드와 형제 노드의 오른쪽 자식 노드를 검은색으로 칠하고 부모 노드를 기준으로 좌회전 후 루트 노드에게 검은색으로 넘기고 이중 흑색을 없애주면 상황은 끝이 나게 됩니다.

형제가 검은색이고 형제의 오른쪽 자식이 빨간색인 경우

 

아래는 이 알고리즘들을 코드로 옮긴 예시입니다.

RBTNode* RBT_SearchNode(RBTNode* Tree, int Target) {
	if (Tree == Nil)
		return NULL;

	if (Tree->Data > Target) {
		return RBT_SearchNode(Tree->Left, Target);
	}
	else if(Tree->Data < Target){
		return RBT_SearchNode(Tree->Right, Target);
	}
	else {
		return Tree;
	}
}

RBTNode* RBT_SearchMinNode(RBTNode* Tree) {
	if (Tree == Nil) {
		return Nil;
	}

	if (Tree->Left == Nil) {
		return Tree;
	}
	else {
		return RBT_SearchMinNode(Tree->Left);
	}
		
}

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;
			// 1. 형제가 빨간색인 경우
			if (Sibling->Color == RED) {
				Sibling->Color = BLACK;
				Successor->Parent->Color = RED;
				RBT_RotateLeft(Root, Successor->Parent);
			}
			//2. 형제가 검은색인 경우
			else {
				// 2-1. 형제의 양쪽 자식이 모두 검은색인 경우
				if (Sibling->Left->Color == BLACK && Sibling->Right->Color == BLACK) {
					Sibling->Color = RED;
					Successor = Successor->Parent;
				}
				// 2-2. 왼쪽 자식이 빨간색인 경우
				else {
					if (Sibling->Left->Color == RED) {
						Sibling->Left->Color = BLACK;
						Sibling->Color = RED;

						RBT_RotateRight(Root, Sibling);
						Sibling = Successor->Parent->Right;
					}
					// 2-3. 오른쪽 자식이 빨간색인 경우
					Sibling->Color = Successor->Parent->Color;
					Successor->Parent->Color = BLACK;
					Sibling->Right->Color = BLACK;
					RBT_RotateLeft(Root, Successor->Parent);
					Successor = (*Root);
				}
			}
		}
		else { // 이중흑색 노드가 오른쪽 자식일때
			Sibling = Successor->Parent->Left;
			// 1. 형제가 빨간색인 경우
			if (Sibling->Color == RED) {
				Sibling->Color = BLACK;
				Successor->Parent->Color = RED;
				RBT_RotateRight(Root, Successor->Parent);
			}
			//2. 형제가 검은색인 경우
			else {
				// 2-1. 형제의 양쪽 자식이 모두 검은색인 경우
				if (Sibling->Right->Color == BLACK && Sibling->Left->Color == BLACK) {
					Sibling->Color = RED;
					Successor = Successor->Parent;
				}
				// 2-2. 오른쪽 자식이 빨간색인 경우
				else {
					if (Sibling->Right->Color == RED) {
						Sibling->Right->Color = BLACK;
						Sibling->Color = RED;

						RBT_RotateLeft(Root, Sibling);
						Sibling = Successor->Parent->Left;
					}
					// 2-3. 오른쪽 자식이 빨간색인 경우
					Sibling->Color = Successor->Parent->Color;
					Successor->Parent->Color = BLACK;
					Sibling->Right->Color = BLACK;
					RBT_RotateRight(Root, Successor->Parent);
					Successor = (*Root);
				}
			}
		}
	}
}

RBTNode* RBT_RemoveNode(RBTNode** Root, int 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->Parent->Left) {
			Removed->Parent->Left = Successor;
		}
		else {
			Removed->Parent->Right = Successor;
		}
	}

	if (Removed->Color == BLACK) // 삭제한 노드가 검은색인 경우 이중흑색이기 때문에 처리를 위해 리빌딩 함수 호출
		RBT_RebuildAfterRemove(Root, Successor);

	return Removed;
}

출처 : 뇌를 자극하는 알고리즘

반응형
저작자표시