[자료구조] 레드 블랙 트리 — Developer

레드 블랙 트리는 균형 이진 탐색 트리로 탐색, 삽입, 삭제 모두 시간 복잡도가 O(logn)입니다. C++ STL의 set, multiset, map, multimap이 이 레드 블랙 트리를 이용해 구현되어 있습니다.

출처: 위키피디아

레드 블랙 트리가 균형을 유지하는 비결

레드 블랙 트리는 아래의 규칙을 지킴으로써 균형을 유지합니다.

모든 노드는 빨간색 또는 검은색의 색을 가진다.
루트 노드는 검은색이다.
잎 노드(NIL)는 검은색이다. (NIL : null leaf, 데이터를 갖지 않고 트리의 끝을 나타내는 더미 노드)
빨간 노드의 자식은 모두 검은색이다, 하지만 검은색 노드의 자식이 빨강일 필요는 없다.
루트 노드에서 모든 잎 노드 사이에 있는 검은색 노드의 수는 모두 동일하다.

레드 블랙 트리의 기본 연산

회전

회전은 부모-자식 노드의 위치를 서로 바꾸는 연산입니다. 방향에 따라 우회전, 좌회전으로 나뉩니다. 우회전은 왼쪽 자식과 부모의 위치를 교환하는 것을 말하고, 좌회전은 오른쪽 자식과 부모의 위치를 교환하는 것을 말합니다.

5와 8이 교환하는 예

단순히 부모-자식 노드의 위치만 바꾸면 이진 탐색 트리의 조건마저도 무너지게 되므로 자식 노드를 처리해줘야 합니다. 위의 예시의 경우

노드 6이 노드 8의 왼쪽 자식으로 왔습니다.
노드 6이 다시 노드 5의 오른쪽 자식이 됐습니다.

아래는 우회전을 구현한 함수입니다.

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; 

	// 부모가 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;
	}
}

레드 블랙 트리의 노드 삽입

레드 블랙 트리에 새 노드가 삽입되고 나면 이 노드를 빨간색으로 칠한 다음 양쪽 자식에 NIL 노드를 연결해야 합니다. 위의 규칙 중 “4. 빨간 노드의 자식들은 모두 검은색이다” 는 위반될 수 있습니다.

부모 노드가 할아버지 노드의 왼쪽 자식일 때 규칙을 위반하는 세 가지 경우는 다음과 같습니다.

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

1. 삼촌도 빨간색인 경우

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

이 작업으로 인해 다시 규칙을 위반할 수 있으므로 할아버지 노드를 새로 삽입한 노드로 간주하고 다시 처음부터 규칙을 위반하는 3가지 경우를 따져봐야 합니다.

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

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

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

부모 노드를 검은색, 할아버지 노드를 빨간색으로 칠한 다음 할아버지 노드를 오른쪽으로 회전시킵니다.

레드 블랙 트리의 노드 삭제

레드 블랙 트리의 삭제 연산은 기본적으로 이진 탐색 트리의 삭제 연산을 그대로 사용합니다. 다만 검은색 노드를 삭제하는 경우 4, 5번 규칙을 위반할 수 있으므로 이중 흑색이라는 개념을 도입해 해결하게 됩니다.

이중흑색 노드를 처리하는 방법은 이중흑색 노드의 형제와 조카들의 상태에 따라 모두 네 가지 경우로 나뉩니다. 다음은 이중흑색 노드가 부모 노드의 왼쪽 자식인 경우에 한합니다. 오른쪽 자식의 경우 왼/오만 바꾸면 됩니다.

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

1. 형제가 빨간색인 경우

먼저 형제를 검은색, 부모를 빨간색으로 칠하고 부모를 기준으로 좌회전합니다. 그 뒤로는 2번 케이스로 바뀌어, 2-A, 2-B, 2-C 케이스에 따라 처리하면 됩니다.

2-A. 형제가 검은색이고 형제의 양쪽 자식이 모두 검은색인 경우

형제 노드만 빨간색으로 칠한 다음, 이중흑색 노드가 갖고 있던 두 개의 검은색 중 하나를 부모 노드에게 넘겨주면 됩니다. 그 뒤에 부모 노드의 검은색 노드 처리는 다시 4가지 경우에 따라 처리합니다.

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

형제 노드를 빨간색으로 칠하고 왼쪽 자식을 검은색으로 칠한 다음, 형제 노드를 기준으로 우회전을 수행합니다. 그 뒤 2-C의 경우로 넘어가면 됩니다.

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

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

마지막으로 아래 사이트를 사용하면 직접 레드 블랙 트리를 만들 수 있습니다.

https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

Red/Black Tree Visualization

www.cs.usfca.edu

출처 : 뇌를 자극하는 알고리즘 책, https://hyunipad.tistory.com/15, https://code-lab1.com/red-black-tree/, https://velog.io/@main_door/레드블랙트리, https://riveroverflow.tistory.com/entry/자료구조-4-7-레드-블랙-트리의-삭제Deletion-in-Red-Black-Tree

티스토리툴바