[자료구조] 레드 블랙 트리(RedBlackTree)

 
알고리즘을 풀 때 map을 많이 사용해 왔는데, 이걸 구현하는게 레드 블랙 트리라는 사실은 알고 있었다. 
하지만, 색을 지정하고 균형 트리를 이룬다는 것 외에 정확한 개념을 모르고 있기도 했고, STL을 구현하면서 C++ 실력을 올리기 위해 map STL을 잡았는데, 레드 블랙 트리를 모르고 map 자료구조를 구현할 수 없기 때문에 한 번 알아보기로 했다.
 
*약간의 써칭 + 위키피디아 레드 블랙 트리를 참고해서 정리, 구현한 글입니다. 오류나 질문은 환영입니다! 

레드-블랙 트리 - 위키백과, 우리 모두의 백과사전

 
 

레드 블랙 트리

이진 트리의 특수한 형태로, 컴퓨터 공학 분야에서 숫자 등의 비교 가능한 자료를 정리하는 데 쓰이는 자료구조.

C++의 MAP에서 사용되고 있다. (+unordered_map은 해쉬)

장점
이 전의 포스팅에서 "이진 트리"에 대해 설명했었다.
그 때, 이진트리의 주의해야할 점 하나가 자칫하면, 한쪽으로만 트리가 치우쳐져 O(N)이라는 최악의 시간복잡도가 나올 수 있다는 것이었는데, 레드블랙트리는 이 문제점을 해결할 수 있는 트리이다. 
 
즉, 삽입, 삭제, 검색 시 최악의 경우에도 일정한 실행 시간을 보장한다 (O(logN))
 

---

특성

레드 블랙 트리는 이진탐색 트리이다

 
레드 블랙 트리는 이진 탐색 트리에 추가적인 조건을 만족하는 형태이다.

1. 노드는 레드 혹은 블랙 중 하나이다.

2. 루트 노드는 블랙이다.

3. 모든 리프 노드들(NIL)은 블랙이다
*레드 블랙 트리의 마지막은 NULL 값을 가진 블랙의 노드들이다(NIL)

4. 레드 노드의 자식노드 양쪽은 언제나 모두 블랙이다. (즉, 레드 노드는 연달아 나타날 수 없으며, 블랙 노드만이 레드 노드의 부모가 될 수 있다.)

5. 어떤 노드로부터 시작되어 그에 속한 하위 리프노드에 도달하는 모든 경로에는 리프 노드를 제외하면 모두 같은 개수의 블랙노드가 있다.

 
4번과 5번의 조건에 의해서, 레드 블랙 트리의 가장 중요한 특성

루트 노드부터 가장 먼 잎노드 경로까지의 거리가, 가장 가까운 잎 노드 경로까지의 거리의 두배보다 항상 작다.
 
이 조건에 의해서 최악의 경우에도 일정한 시간 복잡도를 갖게 된다.
 
4번 조건에 의해서 루트 노드부터 리프노드까지의 간선의 개수(h(x)) 중에 (블랙-레드-블랙-레드-블랙) 계속 반복되는 경우가 블랙의 최소 개수 일 것이고 무슨 일이 있어도 경로 중 블랙 노드의 개수(bh(x))는 그 보다 많다.
bh(x) >= h(x)/2
 
그럼, 노드 x를 임의의 root로 하는 임의의 subtree는 적어도 2^bh(x)-1개의 내부 노드를 포함하고 있다.
따라서
n개 내부 노드를 갖는 레드블랙의 높이는 2log(n+1) => O(logN)이 된다. 
 
궁금할 사람들을 위해 정리
N = 2^bh(x)-1 
N+1 = 2^bh(x) 
bh(x) = log(N+1) (bh(x) >= h(x)/2)
h(x) <= 2log(N+1)
 

---

레드 블랙 트리의 구현

레드 이진 트리의 특성을 만족하기 위해 이진탐색트리에 "회전"을 추가해줘야 한다.
 
따라서, 본격적으로 레드 블랙 트리를 구현하기 전에 "회전"을 알아보자.

회전 (왼쪽, 오른쪽)

 
회전이란 말 그대로 타깃 노드를 기준으로 주위 노드들과 함께 (반시계 방향, 시계 방향) 회전하는 것이다.

위와 같이 1번 노드가 루트인 트리가 있다고 하자.  1번 노드가 루트 노드인 트리일 수도, 서브 트리일수도 있다.
1번 노드를 타깃으로 왼쪽 회전을 수행해보자. (반시계 방향으로 회전)

회전을 수행한 모습은 위와 같다. (3번이 루트노드가 되고, 3번의 왼쪽 서브트리가 1번의 오른쪽으로 간 모습)
 

void RedBlackTree::leftRotate(Node* node) {
	if (node == nil || nil == node->right) return;
	Node* temp = node->right;
	// 기존 오른쪽 서브트리의 왼쪽을 기준 노드 오른쪽 서브트리로
	// 옮긴 서브트리의 부모도 바꿔줌
	node->right = node->right->left;
	if (nil != node->right) node->right->parent = node;
	// 왼쪽을 기준 노드로
	temp->left = node;
	temp->parent = node->parent;
	if (nullptr != node->parent) {
		if (node->parent->left == node)
			node->parent->left = temp;
		else
			node->parent->right = temp;
	}
	node->parent = temp;
	if (root == node)
		root = temp;
}

void RedBlackTree::rightRotate(Node* node) {
	if (node == nil || node->left == nil) return;
	Node* temp = node->left;
	node->left = node->left->right;
	if (nil != node->left) node->left->parent = node;
	temp->right = node;
	temp->parent = node->parent;
	if (nullptr != node->parent) {
		if (node->parent->right == node)
			node->parent->right = temp;
		else
			node->parent->left = temp;
	}
	node->parent = temp;
	if (root = node)
		root = temp;

}

 

삽입(Insertion)

 
1. 단순 이진 탐색 트리와 마찬가지로 노드를 삽입하고 색을 붉은색으로 정하는 것에서 시작한다. 
2. "삼촌 노드" 에 따라 색이 달라진다. (삼촌 노드 : 같은 높이에 있는 옆노드의 부모 노드)

• 특성 3 : 모든 리프 노드들은 검은색이다
• 특성 4 : 적생 노드의 모든 자식은 검은색이다. 
• 특성 5: 어떤 노드로부터 시작되어 리프 노드에 도달하는 모든 경로에는 같은 개수의 블랙 노드가 있다. 

case 1.  N이라고 하는 새로운 노드가 트리의 시작(root)에 위치한다. => N은 검은색이다.

 

case 2. 새로운 노드의 부모 노드가 검은색이라면, 4번 특징은 유효하다. 새로운 노드 N의 자식 노드를 블랙 노드로 만들어 5번 속성도 유지한다.

 

case 3. 부모 노드와 삼촌 노드가 모두 붉은색이라면, 5번째 속성을 유지하기 위해 둘을 검은색으로 바꾸고 할아버지 노드를 붉은색으로 바꾼다. -> 2,3번 속성 만족을 위해 재귀적으로 적용한다.

case 4. 부모 노드가 붉은데 삼촌 노드가 검은색일 경우 N과 P의 역할 변경을 위한 왼쪽 회전. 

 

case 5. 부모 노드가 할아버지 노드의 왼쪽 노드에 붉고, 삼촌 노드가 검은색, 새로운 노드가 왼쪽 자식 노드일 경우 할아버지에 대해 오른쪽 회전. 

 
[삽입 구현]

void RedBlackTree::leftRotate(Node* node) {
	if (node == nil || nil == node->right) return;
	Node* temp = node->right;
	// 기존 오른쪽 서브트리의 왼쪽을 기준 노드 오른쪽 서브트리로
	// 옮긴 서브트리의 부모도 바꿔줌
	node->right = node->right->left;
	if (nil != node->right) node->right->parent = node;
	// 왼쪽을 기준 노드로
	temp->left = node;
	temp->parent = node->parent;
	if (nullptr != node->parent) {
		if (node->parent->left == node)
			node->parent->left = temp;
		else
			node->parent->right = temp;
	}
	node->parent = temp;
	if (root == node)
		root = temp;
}

void RedBlackTree::rightRotate(Node* node) {
	if (node == nil || node->left == nil) return;
	Node* temp = node->left;
	node->left = node->left->right;
	if (nil != node->left) node->left->parent = node;
	temp->right = node;
	temp->parent = node->parent;
	if (nullptr != node->parent) {
		if (node->parent->right == node)
			node->parent->right = temp;
		else
			node->parent->left = temp;
	}
	node->parent = temp;
	if (root = node)
		root = temp;

}


Node* RedBlackTree::grandparent(Node * node) {
	if ((node) && node->parent != nullptr) {
		return node->parent->parent;
	}
	else
		return nullptr;
}
Node* RedBlackTree::uncle(Node* node) {
	Node* g = grandparent(node);
	if (g == nullptr)
		return nullptr;
	else
		return node->parent == g->left ? g->right : g->left;
}

void RedBlackTree::Case5(Node* node) {
	Node* g = grandparent(node);
	node->parent->color = BLACK;
	g->color = RED;
	if (node == node->parent->left)
		rightRotate(g);
	else
		leftRotate(g);
}

void RedBlackTree::Change_Tree(Node* node) {
	Node* u = uncle(node), *g;

	//case 1. 내가 루트 노드
	if (node->parent == nullptr) {
		node->color = BLACK;
		root = node;
	}
	// case 2. 내 부모 노드가 검은색 -> 조건 만족
	else if (node->parent&&node->parent->color == BLACK) {
		return;
	}
	//case 3. 부모 노드와 삼촌 노드가 모드 붉은색
	// 1) P, U를 검은색으로 변경
	// 2) G를 붉은색으로 변경 -> 2번,4번 속성을 만족하지 않는다면
	// 3) 재귀적으로 작업.
	else if (u && u->color == RED) {
		node->parent->color = BLACK;
		u->color = BLACK;
		g = grandparent(node);
		g->color = RED;
		//조부모에 대한 root 연산을 계속한다. 서브트리 자체를 삽입시키는듯.
		Change_Tree(g);
	}
	//case 4. P: 붉은색+G의 왼쪽 자식, U: 검은색 
	// N: P의 오른쪽 자식 
	// N과 P의 역할을 변경해야 한다.(왼쪽 회전) 
	// 부모 노드 였던 P는 case5에서 처리한다. -> 4번쨰 속성 
	//  
	else if((node==node->parent->right)&&(node->parent==g->left)){
		leftRotate(node->parent);
		node = node->left;
		Case5(node);
	}
	else if ((node == node->parent->left) && (node->parent == g->right)) {
		rightRotate(node->parent);
		node = node->right;
		Case5(node);
	}
	//case 5. P : 붉은색, U : 검은색 
	// N : P의 왼쪽 자식 노드, P : G의 왼쪽 자식 노드
	// 오른쪽 회전
}

 
 

삭제

 
이진검색트리에서 두 개의 non-leaf 자식 노드를 가진 노드 X를 삭제할 땐, X의 왼쪽 서브트리에서 최대값 or 오른쪽 서브트리에서 최솟값을 갖는 노드 Y를 찾고, X에 Y 값을 복사했다. 
 
이때, Y가 갖는 non-leaf 자식 노드는 1개이다. ( 2개라면 y의 최솟값, 최댓값이 될 수 없다.)
위키피디아에 나와있는 설명을 그림으로 설명.
 

//형제 노드를 찾는다. 
Node* RedBlackTree::sibling(Node * node) {
	if (node == node->parent->left) {
		return node->parent->right;
	}
	else
		return node->parent->left;
}

//리프노드 판별
int is_leaf(Node* node) {
	if (node->parent && !node->right && !node->left)
		return 1;
	else
		return 0;
}

void RedBlackTree::Replace_Node(Node* node, Node* child) {
	// 앞에서 n의 부모가 NULL이 되는 경우를 DELETE_CASE에 오지 않게 미리 처리해준다. 
	// child? 
	child->parent = node->parent;
	if (node->parent&&node->parent->left == node)
		node->parent->left = child;
	if (node->parent && node->parent->right == node)
		node->parent->right = child;
}

이제 삭제하고 트리를 재구성 하는 과정을 구현해보자. 
 

CASE1. N이 새로운 루트가 될 때, 이 경우는 더 할 게 없다. 우리는 모든 경로에서 하나의 검은 노드를 삭제했고, 새로운 루트 노드는 검은색이므로 모든 특성 보존. 

 

CASE2. S(형제)가 빨강일 경우, P의 자식인 S가 빨강이므로 P가 검은색임은 명확하다.(red 다음은 무조건 BLACK) 이 경우, P와 S의 색을 바꾸고, P를 회전 시킨다. 


해당 subtree에서 특성은 맞춰지더라도 모든 경로에서의 검은 노드의 수가 같지 않다.

 
 

CASE3. P,S, 그리고S의 자식들이 검은색인 경우. 이 경우, 우리는 간단히S를 빨강으로 칠하면 된다.
그러나, P를 지나는 모든 경로들은P를 지나지 않는 모든 경로에 대해 검은 노드를 한 개 적게 지니게 되므로, 특성 5(특정 노드에서부터 leaf로 가는 모든 경로에서 같은 수의 검은 노드를 지난다.)를 위반하게 된다. 이를 바로잡기 위해서, 우리는P에다 case 1부터 시작하는 rebalancing 과정을 수행해야 한다.

 

 
 

CASE 4 S와 S의 자식들은 검은색이지만, P는 빨강인 경우. 이 경우엔 단순히 S와 P의 색을 바꾼다. 

S를 지나는 경로의 검은 노드 개수에 영향을 주지 않지만,N을 지나는 경로에 대해서는 검은 노드의 개수를 1개 증가시킨다. 이는 원래 삭제된 검은 노드의 개수를 보충해준다.

 

 

CASE 5 S가 검정, S의 왼쪽 자식이 빨강, S의 오른쪽 자식이 검정이며, N이 부모의 왼쪽 자식인 경우. S를 오른쪽 회전 시켜 S의 왼쪽 자식이 S의 부모노드이자. N의 새로운 형제 노드가 되도록 한다. S의 색을 부모 노드의 색깔과 바꾼다.

 모든 경로는 여전히 같은 수의 검은 노드수를 가지나, 이제 N이 오른쪽에 붉은 노드를 자식으로 둔 검은색 형제노드를 갖게 되었으므로, 6번째 case로 진행하면 된다.N이나N의 부모노드는 이 변형에 아무런 영향을 받지 않는다. (다시 말하지만,N의 새로운 형제 노드를 6번째 case에서S라고 부르도록 할 것이다.)

 

CASE 5 S가 검은색, S의 오른쪽 자식이 빨강이며, N 이 P의 왼쪽 자식인 경우. 이 경우 우리는 P를 왼쪽으로 회전해서, S가 P와 S의 오른쪽 자식노드의 부모 노드가 되게 하한다. 그리고나서, 우리는 P와 S의 색을 바꾸고, S의 오른쪽 자식노드를 검은색으로 만든다. 

 

 

//형제 노드를 찾는다. 
Node* RedBlackTree::sibling(Node * node) {
	if (node == node->parent->left) {
		return node->parent->right;
	}
	else
		return node->parent->left;
}

//리프노드 판별
int is_leaf(Node* node) {
	if (node->parent && !node->right && !node->left)
		return 1;
	else
		return 0;
}

void RedBlackTree::Replace_Node(Node* node, Node* child) {
	// 앞에서 n의 부모가 NULL이 되는 경우를 DELETE_CASE에 오지 않게 미리 처리해준다. 
	// child? 
	child->parent = node->parent;
	if (node->parent&&node->parent->left == node)
		node->parent->left = child;
	if (node->parent && node->parent->right == node)
		node->parent->right = child;
}

// CASE1 루트노드라면 해줄게 없다. 
void RedBlackTree::Delete_Case1(Node* node) {
	if (node->parent != nullptr)
		Delete_Case2(node);
}


//CASE 2임.
void RedBlackTree::Delete_Case2(Node* node) {
	//node는 삭제할 노드의 자식. 
	// 삭제할 노드의 자식의 형제가 
	Node* s = sibling(node);
	
	//RED이면
	if (s->color == RED) {
		// 삭제할 노드의 부모 노드 색상을 RED로 바꿔준다.
		node->parent->color = RED;
		// 형제의 색상은 BLACK
		s->color = BLACK;
		// 그대로 회전. 
		if (node == node->parent->left)
			leftRotate(node->parent);
		else
			rightRotate(node->parent);
	}

	Delete_Case3(node);

}
//CASE3. P,S 그리고 S의 자식들이 검은 경우, 우리는 간단히 S를 빨강으로 칠한다. 
// 그 결과, S를 지나는 모든 경로들은 하나의 검은노드를 적게 갖고 있게 됨
void RedBlackTree::Delete_Case3(Node* node) {
	Node* s = sibling(node);

	if ((node->parent->color == BLACK) &&
		(s->color == BLACK) &&
		(s->left->color == BLACK) &&
		(s->right->color == BLACK)) {
		s->color = RED;
		Delete_Case1(node->parent);
	}
	else
		Delete_Case4(node);
}
//  S와 S의 자식들은 검은색이지만, P는 빨강인 경우. 
// 단순히 S와 P의 색을 바꾸면 된다.
void RedBlackTree::Delete_Case4(Node* node) {
	Node* s = sibling(node);
	// P는 RED. 형제 = BLACK, 형제의 자식들은 BLACK.
	if ((node->parent->color == RED) &&
		(s->color == BLACK) &&
		(s->left->color == BLACK) &&
		(s->right->color == BLACK)) {
		s->color = RED;
		node->parent->color = BLACK;
	}
	else
		Delete_Case5(node);
}

void RedBlackTree::Delete_Case5(Node* node) {
	Node* s = sibling(node);
	if (s->color == BLACK) {
		//빨강을 Node의 부모 노드 오른쪽 자식의 오른쪽 자식으로 두기 위함. 
		// 혹은 Node의 부모 노드 왼쪽 자식의 왼쪽 자식으로 두기 위함.->case 6으로
		if ((node == node->parent->left) &&
			(s->right->color == BLACK) &&
			(s->left->color==RED)) {
			s->color = RED;
			s->left->color = BLACK;
			rightRotate(s);
		}
		else if ((node == node->parent->right) &&
			(s->left->color == BLACK) &&
			(s->right->color == RED)) {
			s->color = RED;
			s->right->color = BLACK;
			leftRotate(s);
		}
	}
	Delete_Case6(node);

}

void RedBlackTree::Delete_Case6(Node* node) {
	Node* s = sibling(node);

	s->color = node->parent->color;
	node->parent->color = BLACK;

	if (node == node->parent->left) {
		s->right->color = BLACK;
		leftRotate(node->parent);
	}
	else {
		s->left->color = BLACK;
		rightRotate(node->parent);
	}
}



// n이 최대 하나의 non-null 자식을 갖고 있다. 
void RedBlackTree::Delete_one_child(Node* node) {
	//리프노드인 child를 찾아서 넣는다. 
	//둘 다 non-leaf라면 node->right.
	Node* child = is_leaf(node->right) ? node->left : node->right;
	//우선, parent에서 node가 있는 자리에 node의 child를 넣는다.
	Replace_Node(node, child);
	//삭제할 노드가 BLACK이면
	// 1) child가 RED인 경우 BLACK으로 변경한다. (5번 조건)
	if (node->color == BLACK) {
		if (child->color == RED)
			child->color = BLACK;
		// 2) child가 BLACK이면 5번 조건을 맞추기 위한 재조정에 들어간다. 
		else {
			Delete_Case1(child);
		}
	}
	//free(node);
}

 
 
 
++ 헤더파일, cpp 파일의 분리 필요
[RBTree를 모두 구현한 코드는 아래 깃헙에서 보실 수 있습니다]
RBTree
 
 
 
 
 

레드-블랙 트리 - 위키백과, 우리 모두의 백과사전

 

---

개인적으로 몰랐던 점
 
위키피디아에 어떤건 statiac void, 어떤건 그냥 void 함수로 적어놓은 걸 볼 수 있었다. 둘다 return을 반환하지 않는 건 동일한데, 다른 점은 무엇일까?
1. static void vs void)
static이 붙으면, 그 함수는 오직 선언된 파일 내에서만 호출 가능하다. 즉, 다른 파일에선 그 함수를 볼 수도, 호출할 수도 없다. => 이러한 방식으로 함수의 성질과 사용범위를 제어해 코드 안정성과 유지보수 성을 높인다.
 
2. struct Node
위키피디아에서는 Node를 구조체로 만들어 주기 떄문에, Node* 가 아닌, struct Node*로 인스턴스를 생성해주는데, 이는 C언어를 기반으로 작성되었기 때문이다. C++의 경우에는 그럴 필요 없다 ㅇㅅㅇ!
그리고 참고로 나는 class로 만들어 줬기 때문에 ㄱㅊ