레드 블랙 트리의 삽입

레드 블랙 트리는 삽입과 삭제가 주된 연산이다.

 

레드 블랙 트리의 삽입 연산은 기본적으로 이진 트리의 연산 방식을 따른다.

 

이후 레드 블랙 트리의 규칙을 준수하고있는지 체크하는 알고리즘에 의해 자체적으로 밸런싱 작업을 수행한다.

 

삽입 연산은 이진 트리에서 처럼 null이 나올때 까지 데이터의 크기를 비교하며 알맞은 노드의 자리를 찾아낸다.

 

여기서 다른 점은 레드 블랙 트리는 null이 아니라 nil 이라는 특수한 노드를 가르키는 곳이 마지막 노드이다.

 

새로운 노드가 들어갈 자리를 찾았으면 전체 트리를 검사해야한다. 이때 새로운 노드는 항상 레드 노드이다.

 

블랙 노드를 추가하는 방법도 있겠지만 레드 노드를 추가하는 것이 더 편리할 것이라 생각된다.

 

레드 노드를 추가하면 부모가 레드 노드인지만 확인하면 되기 때문이다.

만약 부모가 레드 노드라면 다음과 같은 상황을 생각해 볼 수 있다.

부모 노드가 왼쪽 노드인 경우

   부모의 형제 노드 즉, 삼촌 노드도 레드인 경우

   삼촌 노드가 블랙이면서 새로운 노드가 왼쪽 노드인 경우

   삼촌 노드가 블랙이면서 새로운 노드가 오른쪽 노드인 경우

부모 노드가 오른쪽 노드인 경우

   부모의 형제 노드 즉, 삼촌 노드도 레드인 경우

   삼촌 노드가 블랙이면서 새로운 노드가 왼쪽 노드인 경우

   삼촌 노드가 블랙이면서 새로운 노드가 오른쪽 노드인 경우

 

6가지 경우이다. 우선 부모 노드가 왼쪽 노드인 경우를 기준으로 작성한 뒤 왼쪽 오른쪽만 바꿔서 복사하면 된다.

삼촌 노드도 레드면 간단한 방법은 삼촌 노드와 부모 노드를 블랙으로 바꾸는 것이다.

색을 바꿀때는 다른 트리들의 경로의 블랙의 개수를 고려해야하는데 거기까지 생각하면 너무 머리아파진다.

 

그래서 할아버지 노드의 블랙을 부모 노드와 삼촌 노드에 나눠주면 전체 블랙 개수의 변화없이 

 

수정할 수 있다. (할아버지 노드는 무조건 블랙임 부모노드가 레드라면)

 

하지만 이 경우 할아버지 노드가 레드로 되면서 다시 레드-레드 상황이 발생할 수 있다

 

그래서 할아버지 노드를 기준으로 다시 규칙을 체크하게 된다.

 

그럼 다음과 같은 연산을 수행하면된다.

 

삼촌 노드를 블랙으로 칠한다.

부모 노드를 블랙으로 칠한다.

부모의 부모노드 즉, 할아버지 노드를 레드로 칠한다.

할아버지 노드를 새 노드로 간주하여 다시 체크한다.

 

4줄의 코드만 작성하면 된다.

다음으로 삼촌 노드가 블랙인 경우

삼촌 노드가 블랙이면 앞의 상황과 같이 할아버지 노드의 블랙을 부모 노드에게 준다.

 

그럼 삼촌 노드 라인의 블랙이 전체적으로 1 감소하게된다. 규칙 위반

 

이 경우 할아버지 노드를 기준으로 우회전 하게 되면 

 

부모 노드가 할아버지 노드의 위치에 가면서 전체 블랙 수도 맞고 레드-레드도 해결하게 된다.

 

하지만 이때 새 노드의 위치가 중요해 진다.

 

할아버지 노드를 기준으로

 

새 노드가 왼쪽이면 부모노드의 왼쪽에 그대로 있고

새 노드가  오른쪽이면 우회전하면서 할아버지 노드의 왼쪽 노드로 가게된다

 

즉 새 노드가 오른쪽이면 레드 레드 상황이 발생하고 이 경우는 피해야한다.

삼촌 노드가 블랙이면서 새 노드가 오른쪽 노드인 경우

다음과 같이 회전 연산을 통해 새 노드가 왼쪽인 것처럼 바꾼다. 

 

실제로는 새 노드를 왼쪽 노드의 부모 노드로 회전하는 것이다.

 

부모 노드를 왼쪽으로 회전시킨다.

왼쪽으로 회전된 부모 노드를 새 노드로 간주하여 다시 체크한다.

 

2줄만 작성하면된다.

 

이러면 삼촌 노드가 블랙이면서 새 노드가 왼쪽인 경우로 통일 된다.

삼촌 노드가 블랙이면서 새 노드가 왼쪽 노드인 경우

이 때는 위에서 설명 했듯이 부모 노드를 블랙 할아버지 노드를 레드로 칠하고 

 

할아버지 노드를 기준으로 우회전 한다.

 

부모 노드를 블랙으로 칠한다.

할아버지 노드를 레드로 칠한다.

할아버지 노드를 우회전 한다.

 

3줄만 작성하면 된다.

 

그리고 위의 코드를 복사하여 왼쪽 오른쪽을 바꿔 주면 삽입 연산은 완성되게 된다.

 

그리고 부모 노드와 삼촌 노드가 레드인 상황에 의해 루트 노드가 레드인 상황이 발생할 수 있다.

 

그 부분을 처리해 준다.

 

나는 체크 연산 마지막에 항상 루트 노드를 블랙으로 하게 하고 

 

체크 연산의 타겟으로 루트 노드가 들어오면 체크연산을 종료하게 하였다.

 

void RBT::check(NODE* target) {
	// 1. 모든 노드는 레드 or 블랙이다.
	// 2. 루트 노드는 블랙이다.
	// 3. 레드 노드의 자식은 블랙이다. 블랙 노드의 자식은 상관 없음
	// 4. 루트 노드와 리프 노드 사이의 블랙의 개수는 동일하다.
	// 5. 리프 노드는 블랙이다.

	/*
		삽입 연산에서 생각
		1. 부모 노드가 블랙이면 종료
		2. 부모 노드가 레드
			2-1. 삼촌 노드가 레드
			2-2. 삼촌 노드가 블랙
				2-2-1. 새 노드가 왼쪽
				2-2-2. 새 노드가 오른쪽
	*/
	if (!target->parent) {
		return;
	}
	if (target->parent->black == 1) {
		return;
	}
	else {
		NODE* par = target->parent;
		NODE* unc = nullptr;
		//부모 노드가 왼쪽 자식
		if (par->parent->left == par){
			unc = par->parent->right;
			// 삼촌 노드가 레드
			if (unc->black == 0) {
				par->black = 1;
				unc->black = 1;
				par->parent->black = 0;

				check(par->parent);
			}
			// 삼촌 노드가 블랙
			else {
				// 새 노드가 오른쪽 
				if (target == par->right) {
					Lspin(par);
					check(par);
				}
				else {
					par->parent->black = 0;
					par->black = 1;
					Rspin(par->parent);
				}
			}
		}
		// 부모 노드가 오른쪽 자식
		else {
			unc = par->parent->left;
			// 삼촌 노드가 레드
			if (unc->black == 0) {
				par->black = 1;
				unc->black = 1;
				par->parent->black = 0;

				check(par->parent);
			}
			// 삼촌 노드가 블랙
			else {
				// 새 노드가 왼쪽
				if (target == par->left) {
					Rspin(par);
					check(par);
				}
				else {
					par->parent->black = 0;
					par->black = 1;
					Lspin(par->parent);
				}
			}
		}
		
	}
}