4-5. 레드-블랙 트리(RBT ; Red-Black Tree) - (3) 데이터 삭제 구현

1. 기본 구성

(1) 콘솔 창에서 커서의 깜빡임을 감추기

void ShowConsoleCursor(bool flag)
{
	HANDLE output = ::GetStdHandle(STD_OUTPUT_HANDLE);
	CONSOLE_CURSOR_INFO cursorInfo;
	::GetConsoleCursorInfo(output, &cursorInfo);
	cursorInfo.bVisible = flag;
	::SetConsoleCursorInfo(output, &cursorInfo);
}

 

(2) Print 함수에서 매번 출력값을 지우면서 Print 하기

void BinarySearchTree::Print()
{
	::system("cls");
	ShowConsoleCursor(false);
	Print(_root, 10, 0);
}

 

2. 코드 분석 - Delete 함수

- BST 삭제 실행

- 변경된 노드의 색을 체크하고 Black이면 Red로 변경, Red이면 삭제만 하면 된다.

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->right;
		Replace(node, node->left);
		// 블랙 노드가 삭제됨
		if (color == Color::Black)
			DeleteFixup(right);
	}
	else
	{ // 다음 데이터 찾기
		Node* next = Next(node);
		node->key = next->key;
		Delete(next);
	}
}

 

3. DeleteFixup 함수

삭제 이후 레드-블랙 트리의 특성을 어기지 않도록 노드의 위치와 색을 조정하는 과정이다.

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

	// Case 1, Case 2
	while (x != _root && x->color == Color::Black)
	{
		if (x == x->parent->left)
		{
			// Case 3
			// 형제 노드
			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 4, 둘 중 하나가 Red
			if (s->left->color == Color::Black && s->right->color == Color::Black)
			{
				s->color = Color::Red;
				x = x->parent; // 루프로 인해서 코드가 단축
			}
			else
			{	// Case 5
				if (s->right->color == Color::Black)
				{
					s->left->color == Color::Black;
					s->color == Color::Red;
					RightRotate(s);
					s = x->parent->right;
				}

				// Case 6
				s->color = x->parent->color;
				x->parent->color = Color::Black;
				s->right->color = Color::Black;
				LeftRotate(x->parent);
				x = _root;
			}
		}
		else
		{ // 대칭적으로 반대
		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 4, 둘 중 하나가 Red
			if (s->left->color == Color::Black && s->right->color == Color::Black)
			{
				s->color = Color::Red;
				x = x->parent; // 루프로 인해서 코드가 단축
			}
			else
			{	// Case 5
			if (s->right->color == Color::Black)
			{
				s->left->color == Color::Black;
				s->color == Color::Red;
				RightRotate(s);
				s = x->parent->right;
			}
				// Case 6
				s->color = x->parent->color;
				x->parent->color = Color::Black;
				s->right->color = Color::Black;
				LeftRotate(x->parent);
				x = _root;
			}
		}
	}

	x->color = Color::Black;
}