레드 블랙 트리 (Red black tree)

이번에는 레드 블랙 트리를 정리해 보도록 하자.

 

사실 알고리즘보단 자료구조에 가까운 느낌이다.

 

그래도 C++ stl에서 사용하고 있어서 한 번쯤은 구현해볼 가치가 있다.

 

 

이름에서 알 수 있듯이 트리(tree)를 기반으로 한다.

 

이진트리(binary tree)에서 최악의 구조가 발생하지 않도록 여러 규칙들을 걸어 놓았다.

 

먼저 규칙들을 살펴보자. (출처는 위키백과 : https://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Properties)

 

[규칙 1] Each node is either red or black. (노드는 레드 혹은 블랙 중의 하나이다.)

 

[규칙 2] The root is black. (루트 노드는 블랙이다.)

 

[규칙 3] All leaves (NIL) are black. (모든 리프 노드(NIL)들은 블랙이다.)

 

[규칙 4] If a node is red, then both its children are black. (레드 노드의 자식 노드들은 언제나 블랙이다.)

 

[규칙 5] Every path from a given node to any of its descendant NIL nodes contains the same number of black nodes. (어떤 노드로부터 시작되어 리프 노드에 도달하는 모든 경로에는 모두 같은 개수의 블랙 노드가 있다.)

 

 

위의 규칙들을 위반할 수 있는 상황은 노드를 삽입하거나 삭제했을 때이다.

 

그래서 규칙을 위반하지 않도록 하는 방법이 있는데

 

먼저 왼쪽 회전과 오른쪽 회전이라는 개념을 알고 가자.

 

• 왼쪽 회전 (Left rotation)

[그림 1]

 

[그림 1]과 같이 1번 노드가 루트 노드인 트리가 있다고 하자.

 

1번 노드가 루트 노드인 트리일 수 있고 서브 트리(subtree) 일 수도 있다.

 

우리가 왼쪽 회전을 수행할 타깃 노드는 1번 노드이다.

 

왼쪽 회전은 말 그대로 타깃 노드 기준으로 주위 노드들과 함께 반시계 방향으로 회전하는 것을 의미한다.

 

회전 후 모습은 아래 [그림 2]와 같다.

 

[그림 2]

 

루트 노드였던 1번 노드가 왼쪽으로 내려가고

 

원래 오른쪽 자식이었던 3번 노드가 루트 노드로 올라오게 된다.

 

그리고 3번 노드의 왼쪽 자식이었던 4번 노드를 1번 노드의 오른쪽 자식으로 붙여준다.

 

코드로 표현하면 다음과 같다.

 

void RedBlackTree::leftRotate(Node* node)
{
	if (_nil == node || _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;
}

 

오른쪽 회전도 위와 똑같은 방법이지만 한 번 확인하고 넘어가자.

 

• 오른쪽 회전 (Right rotation)

[그림 3]

 

마찬가지로 회전을 수행할 타깃 노드는 1번 노드이다.

 

이번에는 4번 노드가 2번 노드의 오른쪽 자식임을 주의하자.

 

회전 후 모습은 아래 [그림 4]와 같다.

 

[그림 4]

 

루트 노드였던 1번 노드가 오른쪽으로 내려가고

 

원래 왼쪽 자식이었던 2번 노드가 루트 노드로 올라오게 된다.

 

그리고 2번 노드의 오른쪽 자식이었던 4번 노드를 1번 노드의 왼쪽 자식으로 붙여준다.

 

코드로 표현하면 다음과 같다.

 

void RedBlackTree::rightRotate(Node* node)
{
	if (_nil == node || _nil == node->_left)
		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->_left == node)
			node->_parent->_left = temp;
		else
			node->_parent->_right = temp;
	}
	node->_parent = temp;
	if (_root == node)
		_root = temp;
}

 

 

이제 본격적으로 노드 삽입과 삭제 과정에 대해서 알아보자.

 

• 노드 삽입

노드 삽입은 기존의 이진트리의 노드 삽입 과정 이후에 추가 작업이 필요하다.

 

일단 NIL 노드는 레드 블랙 트리의 성질을 유지시키기 위해 존재하는 데이터가 없는 껍데기 노드이다.

 

그래서 NIL 노드의 자식으로 새로운 노드를 삽입하는 것이 아니라

 

기존의 NIL 노드를 없애고 새로 삽입하는 노드로 대체하고 새로 삽입한 노드의 자식 노드들로 NIL 노드를 추가한다.

 

여기서 실제 NIL 노드는 다수개 존재하는 것이 아니라 딱 1개로 생성하여

 

NIL 노드가 필요한 여러 노드들이 다 같이 참조하는 형식으로 구현한다.

 

그래서 새로운 노드를 삽입했다고 하자.

 

그리고 그 노드는 레드로 한다.

 

여기서 규칙들을 검사해보자.

 

삽입한 노드는 레드이므로 [규칙 1]을 따르고 있다.

 

자식 노드들이 블랙 노드인 NIL 노드들이므로 [규칙 3]은 명확히 따르지만 [규칙 4]는 따르는 듯(?)하다.

 

그리고 레드 노드의 삽입 자체는 [규칙 5]를 위반하지 않는다.

 

하지만 [규칙 4]를 위반할 수 있는 두 가지 경우가 존재한다.

 

첫 번째로 삽입한 노드가 루트 노드가 되는 경우 [규칙 2]를 위반한다.

 

이 경우는 단순하게 루트 노드를 블랙으로 바꿔주면 된다.

 

두 번째는 삽입한 노드의 부모 노드가 레드인 경우이다.

 

여기서 부모 노드의 형제 노드인 삼촌(Uncle) 노드의 색상에 따라 해야 할 작업이 나뉜다.

 

참고로 부모 노드가 레드이면 부모 노드가 루트 노드일 수 없다. ([규칙 2])

 

1. 삼촌 노드가 레드

 

부모 노드와 삼촌 노드를 블랙으로 바꿔준다.

 

그리고 조부모(부모의 부모) 노드를 레드로 바꿔준다.

 

만약 조부모 노드의 부모 노드가 레드일 경우

 

조부모 노드를 새로 삽입한 노드로 취급하여 규칙들을 다시 검사한다.

 

즉 반복적으로 조상 노드들을 타고 올라가면서 부모 노드가 블랙일 때까지 작업을 반복한다.

 

루트 노드는 블랙이므로 언젠가는 멈추게 되어 있다.

 

그림으로 표현하면 다음과 같다.

 

[그림 5] 삼촌 노드가 레드 before

 

노드 이니셜을 정리하면 다음과 같다.

 

1) G : Grandparent node (조부모 노드)

 

2) P : Parent node (부모 노드)

 

3) U : Uncle node (삼촌 노드)

 

4) I : Inserted node (삽입된 노드)

 

5) N : Nil node (NIL 노드)

 

[그림 6] 삼촌 노드가 레드 after

 

[그림 6]과 같이 작업했을 때 조부모의 부모 노드가 블랙이라고 가정하고 규칙들을 검사해보자.

 

조부모 노드와 조부모의 자식들 노드의 색상을 교환하는 것이므로 [규칙 5]를 위반하는 일은 없다.

 

다른 규칙들은 한눈에 만족되는 것을 확인할 수 있다.

 

2. 삼촌 노드가 블랙

 

이 경우 먼저 살펴봐야 할 부분은 부모 노드와 삽입한 노드의 위치 관계이다.

 

일단 부모 노드와 삽입한 노드를 일직선상에 위치하도록 해야 한다.

 

이 말이 무슨 말이냐면

 

부모 노드가 조부모 노드의 왼쪽 자식이라면 삽입한 노드도 부모 노드의 왼쪽 자식으로 맞춰줘야 한다.

 

반대로 부모 노드가 조부모 노드의 오른쪽 자식이라면 삽입한 노드도 부모 노드의 오른쪽 자식으로 맞춰야 한다.

 

그럼 위의 두 경우가 발생하는 모습은 아래와 같다.

 

[case 1] 부모 노드가 조부모 노드의 왼쪽 자식이고 삽입한 노드가 부모 노드의 오른쪽 자식인 경우 [그림 7]

 

[그림 7]

 

[case 2] 부모 노드가 조부모 노드의 오른쪽 자식이고 삽입한 노드가 부모 노드의 왼쪽 자식인 경우 [그림 8]

 

[그림 8]

 

그렇다면 어떻게 부모 노드와 삽입한 노드를 일직선상에 위치시키는가?

 

[case 1]일 때 부모 노드를 기준으로 왼쪽 회전을 한다.

 

[case 2]일 때 부모 노드를 기준으로 오른쪽 회전을 한다.

 

[case 1]에 대해서만 회전 결과를 확인하면 다음과 같다. [그림 9]

 

[그림 9]

 

부모 노드와 삽입한 노드를 일직선상에 위치시켰다.

 

애초에 [그림 10]과 같이 일직선 상에 위치할 수도 있다.

 

[그림 10]

 

[그림 9]와 [그림 10]은 회전 수행 여부에 따라 I와 P의 위치가 다름을 주의하자.

 

그리고 [그림 10]에서 S는 부모 노드의 오른쪽 서브 트리(subtree)를 나타낸다.

 

[case 2]도 마찬가지로 애초에 일직선 상에 위치해 있을 수도 있다. (그림 생략)

 

이제 조부모 노드를 회전시키고 조부모 노드와 부모 노드의 색상을 교환하면 된다.

 

[case 1]의 [그림 10]에 이어서 설명하겠다.

 

조부모 노드를 오른쪽으로 회전시킨다. 그리고 색상을 교환하면 [그림 11]과 같다.

 

[그림 11]

 

[그림 11]에서 S의 위치가 바뀐 것에 주의하자.

 

끝으로 규칙들이, 특히 [규칙 5]를 위반하지 않았는지 확인해보자.

 

먼저 S 쪽은 부모 노드와 조부모 노드의 색상이 바뀐 것뿐이기 때문에 위반하지 않았다.

 

삼촌 노드(U) 쪽도 상위 노드가 하나 추가되긴 하였지만 레드이므로 위반하지 않았다.

 

[case 2]도 마찬가지로 조부모 노드를 왼쪽으로 회전시키면 마찬가지의 결과를 얻을 수 있다.

 

여기까지가 노드 삽입 방법이다.

 

코드로 표현하면 다음과 같다.

 

void RedBlackTree::reconstructionAfterInsertion(Node* node, bool left)
{
	Node* parent = node->_parent;
	while (nullptr != parent && RED == parent->_color)
	{
		// in loop grand parent must exist
		Node* grandParent = parent->_parent;
		bool leftParent = grandParent->_left == parent;
		Node* uncle = leftParent ? grandParent->_right : grandParent->_left;
		if (RED == uncle->_color)
		{
			parent->_color = BLACK;
			uncle->_color = BLACK;
			grandParent->_color = RED;
			node = grandParent;
			parent = grandParent->_parent;
			if (nullptr != parent)
				left = parent->_left == node;
		}
		else
		{
			if ((leftParent && false == left) || (false == leftParent && left))
			{
				leftParent ? leftRotate(parent) : rightRotate(parent);
				parent = node;
				left = !left;
			}

			parent->_color = BLACK;
			grandParent->_color = RED;
			left ? rightRotate(grandParent) : leftRotate(grandParent);
			break;
		}
	}
	_root->_color = BLACK;
}

 

위 코드는 이진트리의 삽입 작업 직후에 호출되는 함수이다.

 

매개 변수는 새로 삽입한 노드와 부모 노드의 왼쪽 자식인지 오른쪽 자식인지의 여부를 나타낸다.

 

while 반복문의 조건은 부모 노드가 존재해야 하며 색상은 레드인 것이다.

 

암묵적으로 조부모도 존재해야 한다는 조건이 따라붙는다. (부모 노드가 레드이므로)

 

그다음으로 삼촌 노드를 찾고 부모 노드가 조부모 노드의 왼쪽 자식인지 오른쪽 자식인지를 구별한다.

 

삼촌 노드의 색상에 따라 위에서 설명했던 대로 작업을 수행하는 것을 확인할 수 있다.

 

함수를 빠져나가기 전에 루트 노드를 블랙으로 바꿔주는 것도 확인할 수 있다.

 

이제 노드 삭제 작업을 알아보자.

 

• 노드 삭제

노드 삭제도 마찬가지로 이진트리의 노드 삭제 작업 이후에 추가 작업이 필요하다.

 

레드 블랙 트리에서 노드 삭제가 노드 삽입 작업보다 복잡하다고 말하지만

 

결국엔 여러 경우로 더 나뉘고 해 줄 작업이 각각 존재한다는 것뿐이다.

 

노드 삭제 작업에 들어가기 전에 몇 가지 확인을 하고 넘어가자.

 

기존의 이진트리에서 노드 삭제 작업은 노드 삽입 작업과 다르게 어느 노드에서든 일어날 수 있다.

 

(앞서 노드 삽입 작업은 항상 리프 노드에서만 일어났었다.)

 

그리고 노드 삭제 후 해당 노드의 후임자(successor)를 구하는 작업도 한다.

 

삭제한 노드의 자식 노드가 둘 다 존재할 경우 후임자를 구하는 방식은 두 가지가 있는데

 

필자는 왼쪽 서브 트리에서 후임자를 찾는 방식을 사용한다.

 

레드 블랙 트리에서 삭제한 노드 위치로 들어오는 후임자 노드는 문제 되지 않는다.

 

삭제한 노드의 색상으로 바꿔주면 되기 때문이다.

 

문제가 되는 부분은 후임자 노드가 존재했던 곳이다.

 

한 가지 다행인 것은 후임자 노드는 자식 노드가 없거나 한쪽 자식 노드만 존재한다는 것이다.

 

필자의 경우 후임자의 오른쪽 자식 노드가 존재하지 않는다.

 

이제 좀 더 구체적으로 알아보자.

 

후임자 노드가 레드라면 후임자의 자식 노드를 후임자의 부모 노드에 그냥 붙여주면 된다.

 

후임자 노드가 블랙이고 후임자의 자식 노드가 레드라면

 

후임자의 자식 노드를 블랙으로 바꾸고 후임자의 부모 노드에 붙여주면 된다.

 

위의 두 경우 모두 [규칙 5]를 위반하지 않는다.

 

후임자 노드와 후임자의 자식 노드가 모두 블랙이면 [규칙 5]를 위반하게 된다.

 

후임자의 자식 노드 쪽으로 블랙 노드의 개수가 부족하게 되기 때문이다.

 

그래서 살펴봐야 할 노드들은 부모, 형제, 조카 노드들이다.

 

여러 경우들을 차례차례 짚고 넘어가자. 총 5가지 경우가 있다.

 

[case 1] 부모 노드가 레드이고 형제, 조카 노드들이 블랙인 경우 [그림 12]

 

[그림 12]

 

먼저 노드의 이니셜을 정리하면 다음과 같다.

 

1) P : Parent node (부모 노드)

 

2) C : Child node (자식 노드)

 

3) S : Sibling node (형제 노드)

 

4) N1 : Nephew 1 node (조카 1 노드)

 

5) N2 : Nephew 2 node (조카 2 노드)

 

앞서 설명한 후임자 노드의 자리를 메꾼 후임자의 자식 노드가 그림의 자식 노드(C)이다.

 

자식 노드는 NIL이든 NIL이 아니든 상관없다.

 

[case 1]부터 [case 5]까지 모두 자식 노드가 부모 노드의 왼쪽에 있는 모습을 나타냈지만

 

그 반대 모습일 수도 있다. (C 노드가 오른쪽에 있고 형제와 조카 노드들이 왼쪽에 있을 수 있다.)

 

설명은 위의 모습을 토대로 하지만 반대의 모습일 때는 회전만 반대 방향으로 해주면 된다.

 

여기서 질문!

 

형제 노드가 NIL일 수 있을까?

 

한 번 고민해보고 넘어가길 바란다.

 

답은 NIL일 수 없다.

 

위의 5가지 경우까지 오게 된 사유를 상기해보자.

 

후임자 노드와 후임자의 자식 노드가 모두 블랙일 때이다.

 

즉 [규칙 5] 때문에 형제 노드가 NIL이 아님을 보장받는다.

 

이제 [case 1]일 때 수행할 작업을 알아보자.

 

[case 1]은 단순하게 부모 노드와 형제 노드의 색상을 교환하면 된다.

 

자식 노드 쪽은 블랙 노드 개수가 늘어났고 조카 노드들 쪽은 변함이 없다.

 

따라서 [규칙 5]를 위반하지 않게 되었다.

 

작업 후 모습은 [그림 13]과 같다.

 

[그림 13]

 

[case 2] 형제 노드가 블랙이고 멀리 있는 조카 노드가 레드인 경우 [그림 14]

 

[그림 14]

 

레드와 블랙으로 칠해지지 않은 빈 노드는 무슨 색상의 노드가 오든 상관없음을 의미한다.

 

[case 2]는 부모 노드를 왼쪽으로 회전하고 부모 노드와 형제 노드의 색상을 교환한 후

 

멀리 있는 조카의 색상을 블랙으로 바꾼다.

 

작업한 모습은 [그림 15]과 같다.

 

[그림 15]

 

자식 노드 쪽은 블랙 노드가 한 개 늘어났고 조카 노드들 쪽은 변함이 없으므로 [규칙 5]를 위반하지 않았다.

 

[case 3] 형제 노드가 블랙이고 가까이 있는 조카 노드가 레드, 멀리 있는 조카 노드가 블랙인 경우 [그림 16]

 

[그림 16]

 

[case 3]은 형제 노드를 오른쪽으로 회전하고 가까이 있던 조카와 형제 노드의 색상을 교환한다.

 

작업한 모습은 [그림 17]과 같다.

 

[그림 17]

 

[그림 17]의 모습은 [case 2]와 같다.

 

[case 2]에서 했던 작업을 해주면 된다.

 

[case 4] 부모, 형제, 조카 노드들이 모두 블랙인 경우 [그림 18]

 

[그림 18]

 

[case 4]는 형제 노드의 색상을 레드로 바꿔주면

 

자식 노드 쪽으로만 블랙 노드의 개수가 부족했던 문제가

 

부모 노드 쪽으로 블랙 노드의 개수가 부족해지는 것으로 확장된다.

 

즉 자식 노드의 문제가 부모 노드의 문제로 올라가게 된다.

 

앞서 노드 삽입할 때에도 조상 노드로 문제를 올려 보내서 해결했던 것처럼 해결하면 된다.

 

작업한 모습은 [그림 19]와 같다.

 

 

[그림 19]

 

[case 5] 형제 노드가 레드이고 부모, 조카 노드들이 블랙인 경우 [그림 20]

 

[그림 20]

 

[case 5]는 부모 노드를 왼쪽으로 회전하고 부모 노드와 형제 노드의 색상을 교환한다.

 

작업한 모습은 [그림 21]과 같다.

 

[그림 21]

 

여기서 잠시 [규칙 5]를 검사해보자.

 

가까웠던 사촌인 N1 노드 쪽은 변함이 없어서 위반하지 않았다.

 

멀리 있던 사촌인 N2 노드 쪽도 마찬가지이다.

 

하지만 여전히 자식 노드 쪽은 블랙 노드 개수가 부족한 상황이다.

 

이 상황은 부모 노드의 색상이 바뀌고 N1 조카 노드가 형제 노드가 되었다.

 

이는 형제 노드 기준 서브 트리의 규모가 작아진 셈이다.

 

이 상황에서 다시 [case 1]부터 [case 3]까지의 경우를 검사하면 된다.

 

여기서 또다시 질문!

 

조카 노드들이 NIL일 수 있을까?

 

답은 NIL일 수 없다.

 

후임자 노드가 블랙 노드였기 때문에 [규칙 5]에 의하여 NIL이 아님을 보장받는다.

 

여기까지가 노드 삭제 작업이다.

 

코드로 표현하면 다음과 같다.

 

void RedBlackTree::reconstructionAfterDeletion(Node* child, Node* parent)
{
	while (nullptr != parent)
	{
		bool left = parent->_left == child;
		Node* sibling = left ? parent->_right : parent->_left;
		if (RED == parent->_color)
		{
			if (BLACK == sibling->_left->_color && BLACK == sibling->_right->_color)
			{
				// case 1
				// parent : red, sibling : black, sibling left : black, sibling right : black
				sibling->_color = RED;
				parent->_color = BLACK;
				break; 
			}
		}
		else if(BLACK == sibling->_left->_color && BLACK == sibling->_right->_color)
		{
			if (BLACK == sibling->_color)
			{
				// case 4
				// parent : black, sibling : black, sibling left : black, sibling right : black
				sibling->_color = RED;
				child = parent;
				parent = parent->_parent;
				continue; 
			}
			else // RED == sibling->_color
			{
				// case 5
				// parent : black, sibling : red, sibling left : black, sibling right : black
				parent->_color = RED;
				sibling->_color = BLACK;
				if (left)
				{
					leftRotate(parent);
					sibling = parent->_right;
				}
				else
				{
					rightRotate(parent);
					sibling = parent->_left;
				}
				continue;
			}
		}

		if (BLACK == sibling->_color &&
			((left && RED == sibling->_left->_color && BLACK == sibling->_right->_color)
				|| (!left && BLACK == sibling->_left->_color && RED == sibling->_right->_color)))
		{
			// case 3
			// parent : all, sibling : black, sibling left : red, sibling right : black
			if (left)
			{
				rightRotate(sibling);
				parent->_right->_color = BLACK;
				parent->_right->_right->_color = RED;
				sibling = parent->_right;
			}
			else
			{
				leftRotate(sibling);
				parent->_left->_color = BLACK;
				parent->_left->_left->_color = RED;
				sibling->_parent->_left;
			}
		}
		
		if (BLACK == sibling->_color && ((left && RED == sibling->_right->_color) || (!left && RED == sibling->_left->_color)))
		{
			// case 2
			// parent : all, sibling : black, sibling left : all, sibling right : red
			left ? leftRotate(parent) : rightRotate(parent);
			NODE_COLOR temp = parent->_color;
			parent->_color = sibling->_color;
			sibling->_color = temp;
			left ? sibling->_right->_color = BLACK : sibling->_left->_color = BLACK;
			break; 
		}
	}
}

 

위 코드는 이진트리의 삭제 작업 후에 후임자 노드와 후임자의 자식 노드가 블랙일 때 호출되는 함수이다.

 

매개 변수는 후임자 자식 노드와 그 부모 노드이다.

 

while 반복문의 조건은 자식 노드가 루트 노드가 아닐 때까지 반복한다.

 

위에서 설명한 각 case들을 주석으로 나타냈다.

 

자식 노드가 부모 노드의 왼쪽이냐 오른쪽이냐에 따라 회전 방향이 다르다는 점을 주의하자.

 

위 코드에는 없지만 함수 끝나고 루트 노드의 색상을 블랙으로 바꿔주는 부분이 꼭 추가되어야 한다.

 

 

여기까지 레드 블랙 트리에 대한 설명이다.

 

참고 사이트 https://itstory.tk/entry/%EB%A0%88%EB%93%9C%EB%B8%94%EB%9E%99-%ED%8A%B8%EB%A6%ACRed-black-tree

레드블랙 트리(Red-black tree)

참고 서적은 한빛미디어의 "뇌를 자극하는 알고리즘"이다.

 

생각보다 간단하지 않으므로 한 번쯤은 구현해보는 것도 나쁘지 않다.