[알고리즘] 레드 블랙 트리 - 2.삭제

레드 블랙 트리에서 삭제할 때 빨간색 노드일 때는 문제가 없지만 검정색 노드일 경우 문제가 발생한다.

검정색 노드를 삭제하면 레드 블랙 트리의 원칙인 어떤 노드로부터 그에 속한 하위 리프 노드에 도달하는

경로에는 모두 같은 개수의 블랙 노드를 만난다는 원칙에 위배되기 때문이다.

검정색 노드를 삭제하고 그 자리의 nil 노드를 black으로 설정하는데 nil 노드는 검정색 노드이므로 

이를 Double Black 상태라고 한다. Double Black 상태에서는 폭탄 돌리기를 시작하는데 Red 노드를 만날 때 

까지 이리저리 건네준다. 그래서 폭탄 돌리기하면서 분기로 나누어진다. 

 

Case 1. 루트 노드가 Double Black일 때

삭제할 검정색 노드를 그냥 삭제하면 된다.

 

Case 2. Double Black의 형제가 Red일 때 

부모와 형제를 바꾸고 Double Black 노드 방향으로 Rotate한다. 

그리고 여기서 또 세분화 된다.

 

// [Case1]
	while (x != _root && x->color == Color::Black)
	{
		//      [p(B)]
		// [x(DB)]  [s(R)]

		//      [p(R)]
		// [x(DB)]  [s(B)]
		//         [1]

		//	    [s(B)]
		//      [p(R)]
		// [x(DB)]  [1] 
		if (x == x->parent->left)
		{
			// [Case2]
			Node* s = x->parent->right;
			if (s->color == Color::Red)
			{
				s->color = Color::Black;
				x->parent->color = Color::Red;
				LeftRotate(x->parent);
				s = x->parent->right; // [1]
			}

 

Case 3. Double Black의 형제가 Black && 형제의 양쪽 자식이 모두 Black일 때 

Double Black의 Black을 부모에게 이전한다. 부모가 Red면 Black, Black이면 Double Black이 된다. 

형제는 Red가 되고 부모를 대상으로 이어서 실행한다.

 

// [Case3]
			if (s->left->color == Color::Black && s->right->color == Color::Black)
			{
				s->color = Color::Red;
				x = x->parent;
			}

 

Case 4. Double Black의 형제가 Black && 형제의 near 자식 = Red && 형제의 far 자식 = Black일 때 

near = Black, 형제 =  Red로 바꿔치기 해주고 far 방향으로 Rotate , 그 후 Case 5로

 

			else
			{
				//         [p]
				// [x(DB)]    [s(B)]
				//         [near(R)][far(B)]

				//         [p]
				// [x(DB)]    [near(B)]
				//				  [s(R)]
				//					 [far(B)]

				// [Case4]
				if (s->right->color == Color::Black)
				{
					s->left->color = Color::Black;
					s->color = Color::Red;
					RightRotate(s);
					s = x->parent->right;
				}

 

Case 5. Double Black의 형제가 Black && 형제의 far 자식 = Red 일 때 

부모와 형제의 색상 교환하고, far = black으로 설정한다.  

그리고 Double Black 방향으로 Rotate한다. 그리고 추가 Black을 제거한다.

 

// [Case5]
				s->color = x->parent->color;
				x->parent->color = Color::Black;
				s->left->color = Color::Black;
				RightRotate(x->parent);
				x = _root;
			}
		}
	}

	x->color = Color::Black;
}