[C++ 자/알 Note] 레드블랙트리 - 삭제

레드블랙트리 삭제 구현 주의사항 1 - DoubleBlack

레드블랙트리의 5번째 특징을 고려하면

경로로 뻗어가는 모든 경우에서 블랙 노드의 개수가 같아야 한다

그러나 삭제가 발생하면 블랙노드의 개수가 달라질 수도 있다

예를 들어, 위의 그림에서 20이 삭제되기 전에는

모든 경로에서 블랙노드는 2개가 있다

20이 삭제된 이후에는 왼쪽에서는 1개 오른쪽에서는 2개가 된다

 

이러한 상황에서 강제로 가상의 블랙을 현재 삭제한 노드에

추가하면서 DoubleBlack 상황을 만든다

그리고 이러한 DoubleBlack을 폭탄 돌리기처럼

어떻게 이동시키고 해결할지에 초점을 맞춘다

 

레드블랙트리 삭제 구현 주의사항 2 - 삭제하는 경우 발생하는 case

1번 case) 삭제할 노드가 Red인 경우

해결법: 그냥 삭제하면 끝이다

 

2번 case) root가 DoubleBlack인 경우

해결법: 그냥 추가된 Black을 삭제하면 끝이다

3번 case) DoubleBlack의 sibling 노드가 Red인 경우

해결법:

- s = black, p = red (s <-> p 색상 교환)
- DoubleBlack 방향으로 rotate(p)
이렇게 되면, 다른 케이스로 변경이 되며 실행

4번 case) DoubleBlack의 sibling 노드가 Black && sibling의 양쪽 자식도 Black인 경우

해결법:

- 추가된 Black을 parent에게 이전하면,

p가 Red이면 Black으로 
p가 Black이면 DoubleBlack이 됨

- s = red로 변경
이렇게 되면, p를 대상으로 다른 케이스로 이어서 실행 (DoubleBlack이 여전히 존재하면)

5번 case) DoubleBlack의 sibling 노드가 Black && sibling의 near child == red, far child == black
- s <-> near 색상 교환
- far 방향으로 rotate(s)
이렇게 되면, 6번 케이스로 변경이되며 실행

6번 case) DoubleBlack의 sibling 노드가 Black && sibling의 far child == red
- p <-> s 색상 교환

- far = black
- rotate(p) (DoubleBlack 방향으로)
- 추가 Black 제거

 

레드블랙트리 삭제 구현

void BinarySearchTree::Delete(int key)
{
	Node* deleteNode = Search(_root, key);
	Delete(deleteNode);
}

void BinarySearchTree::Delete(Node* node)
{
	if (node == _nil)
		return;

	if (node->left == _nil)
	{
		Color color = node->color;
		Node* right = node->right;
		Replace(node, node->right);

		if (color == Color::Black)
			DeleteFixup(right);
	}
	else if (node->right == _nil)
	{
		Color color = node->color;
		Node* right = node->left;
		Replace(node, node->left);

		if (color == Color::Black)
			DeleteFixup(right);
	}
	else
	{
		// 다음 데이터 찾기
		Node* next = Next(node);
		node->key = next->key;
		Delete(next);
	}
}

void BinarySearchTree::DeleteFixup(Node* node)
{
	Node* x = node;

	// [Case1][Case2]
	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)
		{
			// [Case3]
			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]
			}

			// [Case4]
			if (s->left->color == Color::Black && s->right->color == Color::Black)
			{
				s->color = Color::Red;
				x = x->parent;
			}
			else
			{
				//         [p]
				// [x(DB)]    [s(B)]
				//         [near(R)][far(B)]

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

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

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

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

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

	x->color = Color::Black;
}

 

레드블랙트리 정리 참고 추천 블로그

https://bo5mi.tistory.com/212