레드 블랙 트리

이승덱·2021년 9월 1일
0

Algorithm&자료구조

목록 보기
17/20

레드 블랙 트리

  • 각각의 노드가 레드나 블랙인 생상 속성을 가지고 있는 이진 탐색 트리이다.

  • 일반적인 이진 탐색 트리가 가지고 있는 조건에 추가적인 조건을 만족해야 유효한 레드 블랙 트리가 된다.

    • 노드는 레드 혹은 블랙 중의 하나이다.

    • 루트 노드는 블랙이다.

    • 모든 리프 노드(NIL)들은 블랙이다.

    • 레드 노드의 자식노드 양쪽은 모두 블랙이다. 따라서 레드 노드는 연달아 나타날 수 없으며, 블랙노드만이 레드 노드의 부모 노드가 될 수 있따.

    • 어떤 노드로부터 시작되어 그에 속한 하위 리프 노드에 도달하는 모든 경로에는 리프 노드를 제외하면 모두 같은 개수의 블랙 노드가 있다.

  • 레드 블랙 트리는 모든 리프 노드까지의 경로상의 블랙의 수가 같아야 하기 때문에 기존의 이진탐색 트리의 삽입/삭제 연산과 조금 다르다.

// 삽입

void BinarySearchTree::Insert(int key)
{
	Node* newNode = new Node();
	newNode->key = key;


	Node* node = _root;
	Node* parent = _nil;

	while (node!= _nil)
	{
		parent = node;
		if (key < node->key)
			node = node->left;
		else
			node = node->right;
	}

	newNode->parent = parent;

	if (parent == _nil)
		_root = newNode;

	if (key < parent->key)
		parent->left = newNode;
	else
		parent->right = newNode;

	// 올바른 RBT인지 검사
	newNode->left = _nil;
	newNode->right = _nil;
	newNode->color = Color::Red;
	InsertFixup(newNode);
}

void BinarySearchTree::InsertFixup(Node* node)
{
	// 1) p = red, uncle = red
	// -> p = black, uncle = black, pp = red로 바꿈
	// 2) p = red, uncle = black (triangle)
	// -> 회전을 통해 3번으로 바꿈
	// 3) p = red, uncle = black (list)
	// -> 색상 변경 + 회전

	
	while (node->parent->color == Color::Red)
	{
		// 부모가 조상의 왼쪽 자식일 경우
		if (node->parent == node->parent->parent->left)
		{
			// uncle 노드
			Node* uncle = node->parent->parent->right;
			if (uncle->color == Color::Red)
			{
				node->parent->color = Color::Black;
				uncle->color = Color::Black;
				node->parent->parent->color = Color::Red;
				node = node->parent->parent;
			}
			else
			{
				if (node == node->parent->right)	// Triangle 타입
				{
					node = node->parent;
					LeftRotate(node);
				}

				//List 타입
				node->parent->color = Color::Black;
				node->parent->parent->color = Color::Red;
				RightRotate(node->parent->parent);
			}
		}
		else
		{
			// uncle 노드
			Node* uncle = node->parent->parent->left;
			if (uncle->color == Color::Red)
			{
				node->parent->color = Color::Black;
				uncle->color = Color::Black;
				node->parent->parent->color = Color::Red;
				node = node->parent->parent;
			}
			else
			{
				if (node == node->parent->left)	// Triangle 타입
				{
					node = node->parent;
					RightRotate(node);
				}

				//List 타입
				node->parent->color = Color::Black;
				node->parent->parent->color = Color::Red;
				LeftRotate(node->parent->parent);
			}
		}
	}

	_root->color = Color::Black;
}
  • 삭제의 경우 삭제되는 노드가 레드일 경우에는 이진 탐색 트리의 삭제와 다를바 없지만 삭제되는 노드가 블랙일 경우 트리의 불균형이 생길 수 있다.(black의 수가 달라질 수 있으므로)
// 삭제

// 먼저 BST 삭제 실행
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->right;
		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)
		{
			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;
			}

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


				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->left;
			if (s->color == Color::Red)
			{
				s->color = Color::Black;
				x->parent->color = Color::Red;
				RightRotate(x->parent);
				s = x->parent->left;
			}
			//left
			//right
			if (s->right->color == Color::Black && s->left->color == Color::Black)
			{
				s->color = Color::Red;
				x = x->parent;
			}
			else
			{
				if (s->left->color == Color::Black)
				{
					s->right->color = Color::Black;
					s->color = Color::Red;
					LeftRotate(s);
					s = x->parent->left;
				}


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

	x->color = Color::Black;
}
profile
공부 기록용 블로그입니다

0개의 댓글