레드 블랙 트리 #2

Delete

 

 

 

1. 삭제할 노드가 Red -> 그냥 삭제 

2. Root가 DB -> 그냥 추가 Black 삭제

3. DB의 sibling 노드가 Red

s = black, p = red (s <-> p 색상 교환)

DB 방향으로 rotage(p)

4. DB의 sibling 노드가 Black && sibling의 양쪽 자식도 Black

추가 Black을 parent에게 이전

p가 Red이면 Black 됨

p가 Black이면 DB 됨

s = red

p를 대상으로 알고리즘 이어서 실행 (DB가 여전히 존재하면)

5. DB의 sibling 노드가 Black && sibling의 near child =red, far child = black

s <-> near 색상 교환

far 방향으로 rotate(s)

6. DB의 sibling 노드가 Black && sibling의 far child = red

p<->s 색상 교환

far = black

rotate(p) (DB방향으로)

추가 Black 제거

 

 

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

void BinarySearchTree::Delete(Node* 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;

	while (x != _root && x->color == Color::Black)
	{
		if (x == x->parent->left)
		{
			//case 3번	DB의 sibling 노드가 Red일 경우
			//s = black, p = red (s <-> p 색상 교환)
			//DB 방향으로 rotage(p)

			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;
			}

			//case 4번 DB의 sibling 노드가 Black && sibling의 양쪽 자식도 Black
			//추가 Black을 parent에게 이전
			//p가 Red이면 Black 됨
			//p가 Black이면 DB 됨
			//s = red
			//p를 대상으로 알고리즘 이어서 실행(DB가 여전히 존재하면)

			if (s->left->color == Color::Black && s->right->color == Color::Black)
			{
				s->color = Color::Red;
				x = x->parent; // p를 대상으로 whild문을 돌면서 나머지 부분을 check 해준다.
			}
			else
			{
				//case 5번 DB의 sibling 노드가 Black && sibling의 near child = red, far child = black
				//s < ->near 색상 교환
				//far 방향으로 rotate(s)

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

				//case 6 DB의 sibling 노드가 Black && sibling의 far child = red
				//p < ->s 색상 교환
				//far = black
				//rotate(p) (DB방향으로)
				//추가 Black 제거

				s->color = x->parent->color;
				x->parent->color = Color::Black;
				s->right->color = Color::Black;
				LeftRotate(x->parent);
				x = _root;
			}
		}
		else
		{
			if (x == x->parent->right)
			{
				//case 3번	DB의 sibling 노드가 Red일 경우

				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->right;
				}

				//case 4번 DB의 sibling 노드가 Black && sibling의 양쪽 자식도 Black

				if (s->right->color == Color::Black && s->left->color == Color::Black)
				{
					s->color = Color::Red;
					x = x->parent; // p를 대상으로 whild문을 돌면서 나머지 부분을 check 해준다.
				}
				else
				{
					//case 5번 DB의 sibling 노드가 Black && sibling의 near child = red, far child = black

					if (s->left->color == Color::Black)
					{
						s->right->color = Color::Black;
						s->color = Color::Red;
						LeftRotate(s);
						s = x->parent->left;
					}

					//case 6 DB의 sibling 노드가 Black && sibling의 far child = red

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

	x->color = Color::Black;
}