1. 소개
Red-Black 트리는 BST 종류 중 하나로 스스로 균형을 잡는 Self-Balanced BST다. BST에서 균형은 성능을 높이기 위해 매우 중요하다. 탐색과 삽입, 삭제 등 주요 연산의 시간 복잡도는 균형이 잡혔을 때 이지만 한쪽으로 편향될수록 에 가까워진다. Red-Black 트리 외에 대표적인 Self-Balanced BST로 AVL 트리가 있다. AVL 트리는 Red-Black 트리에 비해 엄격하게 균형을 유지해서 탐색에선 AVL트리가 더 장점이 있다. 대신 균형을 유지하기 위한 오버헤드가 Red-Black 트리보다 커서 삽입/삭제 같은 트리를 수정하는 연산은 Red-Black 트리에 비해 느릴 가능성이 높다. AVL 트리는 예전에 한 번 구현해 봤다. Red-Black 트리는 AVL 트리에 비해 구현 난이도가 높아 보여서 구현을 미뤘었는데 이번에 도전해 봤다. 유튜브 쉬운 코드 채널의 Red-Black 트리 강의를 바탕으로 구현했다.
2. 구조
2.1. Node struct
/*------------*
* Node *
*------------*/
template<typename K, typename V>
struct Node
{
enum class Color
{
red,
black,
doubleBlack,
nilBlack,
};
K key;
V value;
Node* pRight = nullptr;
Node* pLeft = nullptr;
Color color = Color::red;
Node(K key, V value);
};
C++
복사
key는 트리에서 Node를 식별하기 위해 사용하고 value가 실질적인 데이터를 저장한다. 자식을 가리키기 위한 포인터 두 개가 존재하고 Node의 색깔을 저장하기 위한 변수가 있다. black에 extra black이 붙으면 doubleBlack이 되고 삭제될 Node에 붙으면 nilBlack이 된다. red에 extra black이 붙을 땐 black으로 처리하면 돼서 따로 redBlack값을 만들진 않았다.
2.2. RedBlackTree class
/*--------------------*
* RedBlackTree *
*--------------------*/
template<typename K, typename V>
class RedBlackTree
{
private:
using Node = Node<K, V>;
enum class Rotation
{
none,
right,
rightLeft,
left,
leftRight,
};
public:
~RedBlackTree();
void Insert(K key, V value);
void Delete(K key);
void Clear();
bool ViolatesProperties();
private:
Node* Insert(K key, V value, Node* pCurrent);
Node* Delete(K key, Node* pCurrent);
void Clear(Node* pCurrent);
Node* AddExtraBlack(Node* pCurrent);
Node* RemoveExtraBlack();
Node* HandleDoubleBlack(Node* pGrandParent);
bool ViolatesProperties(Node* pCurrent, bool isParentRed, int numberBlacks, int& maxNumberBlacks);
static Node* RotateRight(Node* pRoot);
static Node* RotateLeft(Node* pRoot);
static Node* RotateRightLeft(Node* pRoot);
static Node* RotateLeftRight(Node* pRoot);
static Node* HandleConsecutiveReds(Node* pGrandParent, Rotation rotation);
static Node* GetSuccessor(Node* pRoot);
private:
Node* m_pRoot = nullptr;
Node* m_pDoubleBlack = nullptr;
bool m_isConsecutiveReds = false;
bool m_isConsecutiveRedsRight = false;
bool m_isRotated = false;
};
C++
복사
삽입/삭제는 오버로딩 메서드가 존재하는데 public의 메서드를 호출하면 private에 있는 메서드를 이용해 재귀적으로 작업을 수행한다. Node의 색깔을 다루는 메서드들이 존재하고 균형을 잡기 위한 회전 연산들도 존재한다. 회전 연산은 AVL 트리에서 사용하는 것과 같은 것들이다. 멤버 변수엔 루트에 대한 포인터, double black Node에 대한 포인터가 있다. 그리고 Red Node가 연속으로 존재하는지 확인할 수 있는 멤버와 연속으로 존재하는 Red Node의 자식이 오른쪽인지 왼쪽인지 판단하기 위한 멤버도 있다. 삽입 시 회전 처리를 한 번 하면 더 이상 할 필요가 없는데 그것을 확인하기 위해서 회전 여부를 저장하는 멤버가 있다. debug 모드에선 삽입/삭제 시 ViolatesProperties 메서드로 마지막에 Red-Black 트리 속성을 위반했는지 확인한다. 실제 구현 코드는 아래 깃허브 코드에 있다.
