[알고리즘] 레드 블랙 트리 - 1.삽입

이진 탐색 트리는 문제점이 있는데 데이터가 한쪽에 편향될 경우

탐색 효율이 연결 리스트와 별 다를 것 없어진다는 것이다.

그래서 데이터 편향을 방지하는 트리가 레드 블랙 트리이다. 

 

출처: 위키피디아

레드블랙 트리는 다음과 같은 규칙을 가진다.

1. 노드는 레드 혹은 블랙 중의 하나이다.
2. 루트 노드는 블랙이다.
3. 모든 리프 노드들(NIL)은 블랙이다.
4. 레드 노드의 자식노드 양쪽은 언제나 모두 블랙이다. (즉, 레드 노드는 연달아 나타날 수 없으며, 블랙 노드만이 레드 노드의 부모 노드가 될 수 있다)
5. 어떤 노드로부터 시작되어 그에 속한 하위 리프 노드에 도달하는 모든 경로에는 리프 노드를 제외하면 모두 같은 개수의 블랙 노드가 있다.

 

레드 블랙트리의 삽입 방식은 이진 탐색트리와 동일하지만 삽입하고나서  레드 블랙 트리의 규칙에 맞춰 조정하는 단계를 거친다. 기본적으로 새로 삽입하는 노드는 빨간색이기 때문에 부모가 검정색일 경우 문제가 없고 부모가 빨강색일 경우

분기로 나누어 함수를 실행한다. 그리고 현재노드 부모의 형제를 삼촌 노드라고 한다.

 

	while (node->parent->color == Color::Red)
	{
		if (node->parent == node->parent->parent->left)
		{
			Node* uncle = node->parent->parent->right;
			if (uncle->color == Color::Red)
			{
				node->parent->color = Color::Black; // p
				uncle->color = Color::Black; // u
				node->parent->parent->color = Color::Red; // pp
				node = node->parent->parent;
			}

삼촌이 Red일 때 부모와 삼촌을 Black으로 만들고 조부를 Red로 설정, node를 조부모로 설정해 다시 루프를 돌린다.

이 경우 p = red u = red 일 때고 가장 간단한 케이스이다.

//     [y]
//  [x]   [3]
// [1][2]
  
//    [x]  
// [1]   [y]
//      [2][3]

void BinarySearchTree::LeftRotate(Node* x)
{
	Node* y = x->right;

	x->right = y->left; // [2];
	
	if (y->left != _nil)
		y->left->parent = x;

	y->parent = x->parent;

	if (x->parent == _nil)
		_root = y;
	else if (x == x->parent->left)
		x->parent->left = y;
	else
		x->parent->right = y;

	y->left = x;
	x->parent = y;
}

Parent가 Red이고 Uncle이 Black일 경우 LeftRotate나 RightRotate를 사용해야 한다.

트리를 좌측이나 우측으로 회전하는 형태로 첫번째 주석에서 두번째로 바뀌는 것이 RightRotate 반대가 LeftRotate다.

 

			else
			{
				//       [pp(B)]
				//   [p(R)]     [u(B)]
				//      [n(R)]

				//        [pp(B)]
				//      [p(R)]  [u(B)]
				//   [n(R)]   

				if (node == node->parent->right) // Triangle 타입
				{
					node = node->parent;
					LeftRotate(node);
				}

				// List 타입

				//        [pp(R)]
				//      [p(B)]  [u(B)]
				//   [n(R)]  

				//       [p(B)]  
				//   [n(R)]   [pp(R)]
				//		[u(B)]
				node->parent->color = Color::Black;
				node->parent->parent->color = Color::Red;
				RightRotate(node->parent->parent);
			}
		}

그리고 조부,부모,현재 노드가 꺾여있으면 triangle 타입, 쭉 펴져있으면 list 타입인데 triangle 타입이면 부모노드에 대하여 

LeftRotate를 해주고 그러면 List 타입이 되는데 부모를 Black 조부를 Red로 설정하고 RightRotate를 해준다.

그리고 지금까지 과정은 부모 노드가 왼쪽 자식임을 기준으로 한 것이므로 오른쪽 자식일 때도 else 블록에 적어준다.