[C++ 자/알 Note] 레드블랙트리 - 개념 및 삽입

균형이진탐색트리

이진탐색트리의 문제점은 트리의 균형에 따라서

최악의 경우 삽입/삭제/탐색에서 O(N)이 발생한다는 점이다

이를 해결하기 위해 균형을 맞추는 대표적인 유형은

AVL, 레드블랙트리, Treap이 있다

대부분 stl에서는 레드블랙트리가 기본으로 사용된다

 

균형이진탐색트리 유형정리

트리 종류	탐색속도 (빠른 순)	삽입/삭제 속도 (빠른 순)	특징
AVL 트리	1	3	가장 엄격한 균형, 빠른 탐색, 삽입/삭제 시 회전 연산 많음
레드블랙트리	2	2	효율적인 균형, 적절한 탐색 및 삽입/삭제 성능, 가장 널리 사용됨
Treap	3	1	무작위 우선순위, 삽입/삭제 빠름, 구현이 간단함, 평균적인 성능 좋지만 최악의 경우 존재

AVL 트리는

가장 엄격한 균형으로 인해 삽입/삭제 속도가 느린 것이 단점이다
레드블랙 트리는

균형 잡힌 성능을 제공하며 대부분의 라이브러리나 실용적인 환경에서 많이 사용된다

Treap은

구현이 간단하고 삽입/삭제가 빠르지만 무작위 우선순위로 인한 트리의 불균형이 발생할 수 있는 것이 단점이다

 

해당 순위는 일반적인 경향을 나타내는 것으로

실제 성능은 데이터의 특성, 구현 방법, 사용 환경에 따라 달라질 수 있다
탐색 속도 차이는 대부분의 경우 미미하며, 삽입/삭제 성능 차이가 더 크게 나타난다

 

레드블랙트리 개념

레드블랙트리는 복잡한 자료구조이지만,

실 사용에서 효율적이고, 최악의 경우에도 상당히 우수한 실행 시간을 보인다

삽입/삭제/탐색 시간복잡도는 모두 O(logN)이다

 

레드블랙트리 특징

1. 노드는 레드 혹은 블랙 중의 하나이다
2. 루트 노드는 반드시 블랙이다
3. 모든 리프 노드들(NIL)은 반드시 블랙이다
4. 레드 노드는 연달아 이어질 수 없다

(즉, 레드 노드의 자식노드 양쪽은 언제나 모두 블랙이다 )
5. 어떤 노드로부터 시작해서 그에 속한 하위 리프 노드에 도달하는

모든 경로에는 모두 같은 개수의 블랙 노드가 있다

 

레드블랙트리 삽입 구현 주의사항

- NIL

BST에서는 nullptr로 자식이 없음을 표시하는 방식 혹은

NIL로 dummy를 만드는 방식 둘 중 하나를 선택해서 사용하면 된다

그러나

레드블랙트리에서는 NIL을 사용하는 방식을 선택하는 것이 기본이다

 

- 재구성(회전)이 발생하는 경우

삽입을 하는 경우에 위의 특징 5가지 중

일반적으로 4번과 5번을 위반하는 경우가 발생하기에

재구성(회전)을 통해 이를 해결한다

 

- 재구성(회전) 방법

 

- 삽입하는 경우 발생하는 case

1번 case) parent == red, uncle == red인 경우

해결법: parent = black, uncle = black, parent의 parent = red로 바꾸면 된다

 

2번 case) parent == red, uncle == black인 경우 (triangle 상황)

해결법: 회전을 통해 3번 case로 바꾸면 된다

3번 case) parent == red, uncle == black인 경우 (list 상황)
해결법: 색상 변경 + 회전

 

 

레드블랙트리 삽입 구현

- _nil 추가

_nil 멤버변수로 하나 만들어서 계속 돌려쓴다 

Node* _nil = nullptr;

BinarySearchTree::BinarySearchTree()
{
	_nil = new Node();// Black
	_root = _nil;
}

BinarySearchTree::~BinarySearchTree()
{
	delete _nil;
}

 

- 삽입하는 경우, _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;
	else if (key < parent->key)
		parent->left = newNode;
	else
		parent->right = newNode;

	// 검사
	newNode->left = _nil;
	newNode->right = _nil;
	newNode->color = Color::Red;

	InsertFixup(newNode);
}

 

- InsertFixup

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

	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;
			}
			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);
			}
		}
		else
		{
			Node* uncle = node->parent->parent->left;
			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;
			}
			else
			{
				if (node == node->parent->left) // Triangle 타입
				{
					node = node->parent;
					RightRotate(node);
				}

				// List 타입

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

	_root->color = Color::Black;
}

 

- 회전

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

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

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

void BinarySearchTree::RightRotate(Node* y)
{
	Node* x = y->left;

	y->left = x->right; // [2];

	if (x->right != _nil)
		x->right->parent = y;

	x->parent = y->parent;

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

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