본문 바로가기
자료구조 알고리즘

레드 블랙 트리

__sapar 2024. 5. 29. 13:37

이진 탐색 트리의 단점은 루트 노드의 값 보다 계속 크거나 작은 값이 자식 노드로 들어오면 해당 이진 탐색 트리는  O(n) 의 시간 복잡도를 가질 수 없다는 것이다.

 

이것을 보안하기 나온 자료구조 중 레드 블랙 트리가 있다.

  1. 레드 블랙 트리는 모든 노드가 레드, 블랙 중 하나의 색상을 가진다.
  2. 모든 루트 노드는 블랙이다
  3. 리프 노드들은 블랙이다. 그래서 리프 노드를 공노드가 아닌 더미 노드를 이용한다. 블랙이라는 것을 알려주기 위해서
  4. 레드 노드의 자식 노드 양쪽은 언제나 모두 블랙이다. 레드가 연달아 나오기 불가능. 블랙 만이 레드의 부모가 될 수 있다.
  5. 어떤 노드로부터 시작되어 그에 속한 하위 리프 노드에 도착하는 모든 경로에는 리프 노드를 제외하면 모두 같은 개수의 블랙 노드가 있다.

위의 특성이 지켜지지 않으면 트리 재구성이 일어난다.

 

실제 구현에서 리프 노드는 사실상 더미 노드이므로 한 개만 만들고 모든 계층의 Nil 노드를 생성한 하나의 Nil 노드를 가리키도록 하겠다.

 

생성 함수 변화 및 컬러

Insert 함수에 변화가 필요하다. 먼저 모든 노드가 레드 or 블랙 색으로 칠해져야한다.

  • 부모와 자식이 R - R 관계가 되어지면
    1. 부모 == R && 부모와 같은 높이의 옆 노드가 == R
      • 그냥 부모, 옆 노드 = B , pp = R
    2. 부모 == R && 부모와 같은 높이의 옆 노드가 == B (꺽인 모양)
      • 회전을 통해서 case 3 로 만들어낸다. 이때 위치에 따라 왼쪽, 오른쪽 회전 결정
    3. 부모 == R && 부모와 같은 높이의 옆 노드가 == B (일자 모양)
      • 최종 색상 변경 및 오른쪽, 왼쪽 회전

핵심 이론은 위와 같다. 즉, 레드 블랙 트리로 수열이 들어오면 레드 블랙 트리는 일자 모양의 노드를 그대로 두지 않고 스스로 왼,오른쪽 회전을 통해 정형화된 이진 트리 형식으로 다시 Fix 한다.

 

헤더 파일

#pragma once

#include <iostream>
#include <vector>
#include <list>
#include <stack>
#include <queue>

using namespace std;

enum class Color
{
	Red = 0,
	Black = 1,
};


class BinarySearchTree
{
public:
	

	// 키 값에 해당 하는 노드를 만들어서 트리에 삽입
	void	 Insert(int key);
	// 레드 블랙 트리가 규칙을 잘지키고 있는지 체크하는 함수
	void	 InsertFixup(NodeTree* node);

	
	// 레드 블랙 트리
	void LeftRotate(NodeTree* node);
	void RightRotate(NodeTree* node);

public:
	NodeTree* _root = nullptr;

	// 레드블랙트리를 위한 NIL 노드	
	NodeTree* _nil = nullptr;
};

 

cpp 파일

enum class ConsoleColor
{
	BLACK = 0,
	RED = FOREGROUND_RED,
	GREEN = FOREGROUND_GREEN,
	BLUE = FOREGROUND_BLUE,
	YELLOW = RED | GREEN,
	WHITE = RED | GREEN | BLUE,
};

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

	/*if (_root == nullptr)
	{
		_root = newNode;
		return;
	}*/

	NodeTree* node = _root;
	NodeTree* parent = _nil;

	while (node != _nil)
	{
		// 해당 구문이 처음에 나옴으로써
		// 들어가야할 노드 자리의 부모 노드 자리를 알게 된다.
		// 이진 탐색 트리로 insert 하면 무조건 한 경로의 마지막까지 내려가게
		// 되어 있다.
		parent = node;

		// 여기서 공노드 나올때가지 계속 비교하고 밑에서는 대입을 하는 거임
		if (key < node->key)
			node = node->left;
		else
			node = node->right;
	}

	// 완전히 추가 될 노드 이므로 위에서 구한
	// parent 를 부모로 받고 마지막으로 한 번 더 비교해서
	// 왼/오 결정해서 거기 들어간다.
	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);
}

void BinarySearchTree::InsertFixup(NodeTree* node)
{
	// 1) p = red, uncle = red
	//  - p = b, u = b, pp = r 로 바꾸기
	// 2) p = red, uncle = black (triangle)
	//  - 회전을 통해 case 3 으로 바꾸어줌
	// 3) p = red, uncle = black (list)
	//  - 색상 변경 및 회전

	//          [(pp)(B)]
	//    [p(R)]        [u] 블랙이면 좋지만, red - red 면 문제임
	//        [n(R)]
	while (node->parent->color == Color::Red)
	{
		if (node->parent == node->parent->parent->left)
		{
			NodeTree* uncle = node->parent->parent->right;
			if (uncle->color == Color::Red)
			{
				node->parent->color = Color::Black; // ]
				uncle->color = Color::Black; // u
				node->parent->parent->color = Color::Red; // pp
				node = node->parent->parent;
			}
			// u 이 B 라면?
			else
			{
				//          [(pp)(B)]
				//    [p(R)]        [u(B)] 
				//        [n(R)]
				//          [(pp)(B)]
				//     [p(R)]        [u(B)] 
				//  [n(R)]     
				// 
				// triangle
				if (node == node->parent->right)
				{
					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
		{
			//          [(pp)(B)]
			//   [u(R)]        [p(R)]
			//               [n(R)]
			NodeTree* uncle = node->parent->parent->left;
			if (uncle->color == Color::Red)
			{
				node->parent->color = Color::Black; // ]
				uncle->color = Color::Black; // u
				node->parent->parent->color = Color::Red; // pp
				node = node->parent->parent;
			}
			// u 이 B 라면?
			else
			{
				//          [(pp)(B)]
				//   [u(B)]        [p(R)]
				//               [n(R)]
				// 
				//          [(pp)(B)]
				//   [u(B)]        [p(R)]
				//                     [n(R)]
				// triangle
				if (node == node->parent->left)
				{
					node = node->parent;
					RightRotate(node);
				}


				// list

				//          [(pp)(R)]
				//   [u(B)]        [p(B)]
				//                     [n(R)]
				// 
				//               [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;
}

//        [p]
//      [y]
//   [x]    [3]
// [1][2]
// 위부분에서 아래 = 오른, 아래에서 위 = 왼
//          [p]
//       [x]
//   [1]    [y]
//         [2][3]

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

	x->right = y->left;

	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;

}

//        [p]
//      [y]
//   [x]    [3]
// [1][2]
// 위부분에서 아래 = 오른, 아래에서 위 = 왼
//        [p]
//      [x]
//   [1]    [y]
//         [2][3]
void BinarySearchTree::RightRotate(NodeTree* y)
{
	NodeTree* x = y->left;

	y->left = x->right;

	if (y->right != _nil)
		y->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;
}

 

 

삭제

 

일단 레드 블랙 트리가 BST 기반이기 때문에 BST 의 삭제 기준대로 삭제를 하게 된다.

  1. 삭제할 노드가 자식이 없을 때
  2. 삭제할 노드가 자식이 하나일 때
  3. 삭제할 노드가 자식이 둘 일 떄

다만, 여기서 레드 블랙 트리는 경우가 더 늘어나는데

1. 삭제할 노드가 Red 인 경우 별다른 문제 없고 BST 처럼 삭제하면 됨

2. 삭제할 노드가 Black 이라면?

문제 생김 이유는 레드블랙의 5번 특성에 의해서 Black 노드가 사라지니깐 모든 경로에서 블랙 노드의 개수가 같아지지 않아진다는 것이다. 일단 해당 노드를 삭제하고 해당 노드에 가상의 블랙을 2번 넣어진 더블 블랙 상태를 만든다.

 

 

당연히 생각하기 편하게 가정한 것이고 저 해당 가상의 더블 블랙을 누군가가 가져가서 균일한 레드 블랙 트리로 만들어야한다.

 

이때 저 가상의 더블 블랙 중 한 개를 위로 올렸을 때 부모가 레드면 블랙으로 바꾸고 부모 또한 블랙이면 다시 부모가 더블 블랙이 되니 재귀적으로 부모가 다시 또 더블 블랙 중 한가지를 어딘가로 보내야하는 상황이 생기는 것이다.

 

여기서 문제는 끝이 아니다. 만약 부모가 레드여서 블랙 하나를 받아 레드에서 블랙 노드가 된다고 할지라도 반대로 반대편 계층의 블랙 갯수가 1개 더 많아져서 문제가 또 생긴다는 것이다.

 

3. 삭제할 노드가 루트

만약 삭제할 노드가 루트 노드고 루트 삭제 후 더블 블랙 삭제가 되면 그냥 블랙을 삭제해도 된다. 제일 쉬움. 왜냐면 제일 높이가 0이라 모든 계층이 루트를 블랙 카운팅 하기 때문에 1이 카운팅 되든 2가 카운팅되든 상관 없어서 그냥 더블 블랙 중 하나 없애도 전혀 문제 없다.

 

4. 형제가 레드 일 때

형제 자체를 블랙으로 만들어 본다… 더블 블랙을 넘겨줄때마다 특정 계층의 블랙 갯수가 엉망이 되기 때문에 차라리 형제 노드를 미리 블랙으로 만드는 것 부터 할 것. 이 때 형제를 블랙으로 부모를 레드로 바꾸어 볼 것. 당연히 이때 삽입에서 사용하던 회전 알고리즘과 유사한 알고리즘이 포함 될 것 이다. 회전 할 때는 더블 블랙의 위치에 따라 회전 방향을 결정한다. 그리고 다른 케이스로 넘

 

5. 형제가 블랙이고 형제의 양쪽 자식이 모두 블랙 일 때

부모가 레드면 블랙으로, 부모가 블랙이면 더블 블랙으로 만듬.

그리고 형제를 레드로 바꾼다. 이제 부모를 기준으로 다시 알고리즘 실행(부모가 더블 블랙이라면)

 

6. 형제가 블랙이고 형제의 자식 중 더블 블랙과 가까운 자식이 레드 멀리 있 자식이 블랙인 경우

가까운 자식을 블랙으로 형제를 레드로 바꾸어준다. 그리고 멀리 있는 자식 기준으로 회전 알고리즘 적용한다. 그리고 다음 케이스로 넘긴다.

 

7. 형제가 블랙이고 형제의 자식 중 더블 블래과 멀리 있는 자식이 레드 일 때

부모와 형제의 색을 바꾸고 멀리 있는 자식을 블랙으로 교체 한 다음 더블 블랙 방향에 부모를 기준으로 회전한 다음 더블 블랙 중 하나 제거하면서 끝!

 

위의 많은 Case 들을 정리하면 다음과 같다.

먼저 BST 삭제 실행...

  • Case1) 삭제할 노드가 Red -> 그냥 삭제! 끝!
  • Case2) root가 DB -> 그냥 추가 Black 삭제! 끝!
  • Case3) DB의 sibling 노드가 Red

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

-- DB 방향으로 rotate(p) -- goto other case

 

  • Case4) DB의 sibling 노드가 Black && sibling의 양쪽 자식도 Black

-- 추가 Black을 parent에게 이전

--- p가 Red이면 Black 됨.

--- p가 Black이면 DB 됨.

-- s = red

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

 

  • Case5) DB의 sibling 노드가 Black && sibling의 near child = red, far child = black

-- s <-> near 색상 교환

-- far 방향으로 rotate(s) -- goto case 6

  • Case6) DB의 sibling 노드가 Black && sibling의 far child = red

--p <-> s 색상 교환

--far = black

--rotate(p) (DB 방향으로)

--추가 Black 제거

 

헤더 파일에 함수추가하고

// 헤더 파일에 함수 추가
// 해당 함수가 Delete 함수에 추가된다.
void	 DeleteFixup(NodeTree* node);

 

 

먼저 nullptr 을 _nil 로 바꾼다. 그리고 삭제 함수에도 color 를 사용하기 위해 삭제할 노드의 color 를 이용하여 체킹 후 DeleteFixup 함수를 호출한다.

DeleteFixup 는 노드가 부모의 왼쪽인지 오른쪽이 기준으로 나뉘어 작성하고 복붙으로 왼/오만 바꾸어주었다. 여기서 Replace 로 노드를 삭제하고 DeleteFixup으로 트리 계층을 리팩토링한다.

// 바뀐 Delete 함수
void BinarySearchTree::Delete(NodeTree* node)
{
	if (node == _nil)
		return;

	if (node->left == _nil)
	{
		Color color = node->color;
		NodeTree* right = node->right;
		Replace(node, node->right);

		if (color == Color::Black)
			DeleteFixup(right);
	}
	else if (node->right == _nil)
	{
		Color color = node->color;
		NodeTree* left = node->left;
		Replace(node, node->left);
		if (color == Color::Black)
			DeleteFixup(left);
	}
	// 둘 다 있을 때
	else
	{
		NodeTree* next = Next(node);
		node->key = next->key;
		Delete(next);
	}

}



// DeleteFixup 함수
void BinarySearchTree::DeleteFixup(NodeTree* node)
{
	// 삭제할 노드
	NodeTree* x = node;

	// [Case1][Case2]
	while (x != _root && x->color == Color::Black)
	{
		if (x == x->parent->left)
		{
			// [Case3]
			// 형제 노드
			NodeTree* 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;
			}

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

					// Case6 로 만들어버림
				}

				// [Case6]
				s->color = x->parent->color;
				x->parent->color = Color::Black;
				s->right->color = Color::Black;
				LeftRotate(x->parent);
				x = _root;

			}
		}
		else
		{
			// [Case3]
			// 형제 노드
			NodeTree* 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;
			}

			// [Case4]
			if (s->right->color == Color::Black && s->left->color == Color::Black)
			{
				s->color = Color::Red;
				x = x->parent;
			}
			else
			{
				// [Case5]
				if (s->left->color == Color::Black)
				{
					s->right->color = Color::Black;
					s->color = Color::Red;
					LeftRotate(s);
					s = x->parent->left;

					// Case6 로 만들어버림
				}

				// [Case6]
				s->color = x->parent->color;
				x->parent->color = Color::Black;
				s->left->color = Color::Black;
				RightRotate(x->parent);
				x = _root;

			}
		}
	}

	x->color = Color::Black;
}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

'자료구조 알고리즘' 카테고리의 다른 글

길찾기2 BFS 를 이용하기  (0) 2024.05.29
길찾기 1 우수법  (0) 2024.05.29
이진 탐색 트리  (0) 2024.05.29
힙으로 구현한 우선순위 큐  (0) 2024.05.29
이진트리 와 힙 이론  (0) 2024.05.29

'자료구조 알고리즘' Related Articles

티스토리툴바