각각의 노드가 레드나 블랙인 생상 속성을 가지고 있는 이진 탐색 트리이다.
일반적인 이진 탐색 트리가 가지고 있는 조건에 추가적인 조건을 만족해야 유효한 레드 블랙 트리가 된다.
노드는 레드 혹은 블랙 중의 하나이다.
루트 노드는 블랙이다.
모든 리프 노드(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;
}
// 삭제
// 먼저 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;
}