위키백과에 의하면Red-Black tree(레드-블랙 트리)는 자가 균형이진 탐색 트리로서, 대표적으로는 연관 배열 등을 구현하는 데 쓰이는 자료구조라고 한다. 레드-블랙 트리는 복잡한 자료구조지만, 실 사용에서 효율적이며최악의 경우에도 O(logN)시간복잡도를 보장할 정도로 안정(balanced)되었다.
트리 구조는 우리 주변 일상에서 쉽게 볼 수 있는 위아래 개념을 컴퓨터에서 표현한 구조다. 더 중요한 트리의 속성 중 하나는 재귀로 정의된 자기 참조 자료구조라는 점!
각 트리의 명칭
그렇다면 그래프와 트리의 차이점은 무엇일까? 한 줄로 요약하자면"트리는 순환 구조를 갖지 않는 그래프"이다.
트리는 특수한 형태의 그래프의 일종이며, 크게 그래프의 범주에 포함된다. 하지만 트리는 그래프와 달리 어떠한 경우에도 한 번 연결된 노드가 다시 연결되는 법이 없다. 이외에도 단방향, 양방향을 모두 가리킬 수 있는 그래프와 달리 트리는 부모 노드에서 자식 노드를 가리키는 단방향 뿐이다.
즉 레드-블랙 트리는 실시간 처리와 같은 실행 시간이 중요한 경우에 유용하게 쓰이고 일정한 실행 시간을 보장하는 또 다른 자료구조를 만드는 데 좋다고 한다. 예를 들면 각종 기하학 계산에 쓰이는 많은 자료구조들이나 많은 SDK나 라이브러리 세트에서 검색 알고리즘으로 사용되고 있다고 한다.
글을 보면서도 잘 이해가 되지 않아서 많은 자료들을 찾아봤었다. 레드-블랙 트리도 이진탐색트리의 일종인데, 이진탐색트리는 탐색을 위해 사용되는 자료구조다. 자료를 이진트리로 구성하여 검색 구조로 삼는 이유는 단순한 구조이면서도 자료의 검색, 삽입, 삭제가 효율적이기 때문이다.
위의 이진트리 그림을 보면, 루트 노드부터 검색을 시작하게 되고 한 노드는 자식을 두 명까지 가질 수 있다. 또한 자신보다 작은 값의 노드는 왼쪽, 큰 값의 노드는 오른쪽에 두는 규칙을 가지고 있다. 때문에 탐색시 모든 노드를 고려할 필요가 없어서 효율적이다. 예를 들면 위의 트리에서 8을 찾는다고 하면 10->7->8로 두 번의 비교만으로 찾을 수 있다.
마냥 좋을 것 같은 이진탐색트리에도 단점이 있다.
위의 그림처럼 값이 한 쪽으로 쏠리게 들어왔을 경우 가장 아래에 있는 값을 검색하기 위해서는 결국 모든 경우를 고려해야 하고, 이는 일반적인 선형 검색의 시간복잡도 O(N)과 다를 게 없다. 그래서 어떤 상황에서도 O(logN)을 보장하는 RBtree가 많이 사용된다고 한다.
레드-블랙 트리는 각각의 노드가 레드나 블랙의 색상 속성을 가지고 있는 이진 탐색 트리
RBTREE 특성
좋은 효율을 보이는 레드-블랙 트리를 구현하기 위해서는 다음과 같은 조건이 필요하다.
1. 노드는 'red' 혹은 'black' 중 하나이다. 2. 루트 노드는 'black'이다. 3. 모든 리프 노드(NIL)들은 'black'이다. 4. 노드가 'red'일 때, 자식 노드 양쪽은 언제나 모두 'black'이다. (즉 레드 노드는 연달나 나타날 수 없다) 5. 각 노드에 대해 해당 노드에서 리프 노드를 제외한 자식 노드까지의 모든 경로들은 같은 수의 'black' 노드 개수를 가진다.
RBTREE 동작
레드-블랙 트리는 수행 시간을 보장하기 위해 트리를 수정한다. 그 결과 레드-블랙 트리의 특성을 위반하게 되기 때문에 몇몇 노드의 색을 바꾸거나(색상 전환) 포인터 구조를 바꿔야 하는데 이러한 작업을로테이션이라고 한다. 노드를 삽입하고 삭제하는 과정에서 많은 case들이 존재하는데, 이런 경우들을 고려하여 구현해야 코드가 정상적으로 잘 돌아간다.
삽입
기본적으로 삽입하면서 새로 생성되는 노드는 '레드'이다(루트는 예외). 신규 노드가 삽입되면서 레드 노드가 연속으로 나타나서 rbtree의 4번 특성을 위반하는 경우가 발생할 수 있는데, 이 때는 케이스에 따라 2가지 방법으로 해결한다.
case 1: 부모 노드가 레드인데, 부모의 형제가 없거나 블랙일 때 - 회전
case 2: 부모 노드가 레드인데, 부모의 형제가 레드일 때 - 색상 변환
삭제
삭제하려는 노드가 레드일 때는 rbtree의 특성을 위배하는 경우가 없기 때문에 그냥 삭제하면 된다. 하지만 삭제하려는 노드가 블랙이라면 조금 복잡해진다. 블랙을 지우게 되면 특성 5번을 위반할 수 있기 때문!
더 구체적으로 얘기해보자면 삭제하려는 노드가 블랙이고 자식이 레드라면 자식 노드를 색상 변환하면 해결되지만, 자식 노드도 블랙이면 위에서 말한 것 처럼 특성 5번을 어기게 된다. 여러 케이스별로 해결 방법을 적어보겠다.
case 1: 삭제하려는 노드의 형제 노드가 블랙, 부모 노드는 레드일 때
삭제하려는 노드를 삭제하게 되면, 부모 노드 기준에서 좌측과 우측의 블랙 노드 개수가 맞지 않게 된다. 이 때는 형제 노드를 레드로 색상 변환하고 부모 노드는 블랙으로 바꾸면 된다.
case 2: 삭제하려는 노드의 형제, 부모 노드 모두 블랙일 때
형제 노드를 레드로 색상 변환하면 되지만, 블랙 노드가 하나 부족한 것이 부모 노드로 전이된다. 그러므로 여기서는 부모 노드를 문제 노드로 두고 다시 문제를 해결해야 한다.
case 3: 삭제하려는 노드의 형제 노드는 블랙이고 형제 노드의 오른쪽 자식(편의 상 x로 지칭)이 레드일 때
left 방향 회전을 하고, x의 색상을 블랙으로 바꾼다.
case 4: 삭제하려는 노드의 형제 노드는 블랙이고 형제 노드의 왼쪽 자식(x)이 레드일 때
이 경우는 형제 노드를 기점으로 right 회전을 한 후 레드 색상을 x에서 형제에게로 옮긴다. 그렇게 하면 case 3과 같은 상황이 되고, case 3처럼 해결하면 된다.
case 5: 삭제하려는 노드의 형제 노드가 레드인 경우
부모 노드를 기준으로 left 로테이션을 한다(삭제 노드가 왼 쪽인 경우). 그 이후 형제 노드는 블랙, 부모 노드는 레드로 색상 변환한다.
글로만 쓰니까 어렵다;; 코드로 다시 보면서 구체적으로 이해하자.
코드 구현
#include <stdlib.h>
#include <stddef.h>
typedef enum { RBTREE_RED, RBTREE_BLACK } color_t;
typedef int key_t;
typedef struct node_t {
color_t color;
key_t key;
struct node_t *parent, *left, *right;
} node_t;
typedef struct {
node_t *root;
} rbtree;
rbtree *new_rbtree(void);
void delete_rbtree(rbtree *);
node_t *rbtree_insert(rbtree *, key_t);
node_t *rbtree_find(const rbtree *, const key_t);
node_t *rbtree_min(const rbtree *);
node_t *rbtree_max(const rbtree *);
int rbtree_erase(rbtree *, node_t *);
int rbtree_to_array(const rbtree *, key_t *, const size_t);
void *insert_fixup(rbtree *, node_t *);
void *erase_fixup(rbtree *, node_t *);
// nil 생성
node_t make_nil = {
.color = RBTREE_BLACK,
.left = NULL,
.right = NULL,
.parent = NULL
};
node_t *nil = &make_nil;
// 트리 생성
rbtree *new_rbtree(void) {
rbtree *p = (rbtree *)calloc(1, sizeof(rbtree)); // rbtree의 인자를 1개 메모리 할당(할당된 공간의 값을 모두 0으로 초기화)
return p;
}
// RBtree 구조체가 차지했던 메모리 반환
void del_node(node_t * t) {
if (t != NULL) {
del_node(t->left);
del_node(t->right);
}
free(t);
}
void delete_rbtree(rbtree *t) {
del_node(t->root);
free(t);
}
// 좌회전 함수
node_t *left_rotate(node_t *t, node_t *base) {
node_t *y = base->right;
base->right = y->left;
if (y->left != NULL) {
y->left->parent = base; // 왼쪽으로 돌리기 때문에 y의 작은 수는 base 자식으로 옮겨짐
}
y->parent = base->parent; // 부모 노드 옮기기
if (base->parent == NULL) { // base->parent가 없다면 y가 root
t = y;
}
else if (base == base->parent->left) { // base가 왼쪽에 위치한다면
base->parent->left = y;
}
else {
base->parent->right = y;
}
y->left = base;
base->parent = y;
return t;
}
// 우회전 함수
node_t *right_rotate(node_t *t, node_t *base) {
node_t *y = base->left;
base->left = y->right;
if (y->right != NULL) {
y->right->parent = base;
}
y->parent = base->parent;
if (base->parent == NULL) {
t = y;
}
else if (base == base->parent->right) {
base->parent->right =y;
}
else {
base->parent->left = y;
}
y->right = base;
base->parent = y;
return t;
}
void *insert_fixup(rbtree *t, node_t *n) {
node_t *y;
while (n->parent != NULL && n->parent->color == RBTREE_RED) { // 부모 노드가 RED면
if (n->parent == n->parent->parent->left) { // 부모 노드가 조부모 노드의 왼쪽에 있다면
y = n->parent->parent->right; // 삼촌 노드
if (y != NULL && y->color == RBTREE_RED) { // 부모, 삼촌 다 RED
n->parent->color = RBTREE_BLACK;
y->color = RBTREE_BLACK;
n->parent->parent->color = RBTREE_RED;
n = n->parent->parent; // 균열이 생기는 지점(조부모 노드가 레드로 변하면서 조건을 깰 수 있기 때문!)
}
else { // 부모 노드 RED, 삼촌 노드 BLACK
if (n == n->parent->right) { // 현재 노드가 오른쪽에 위치한다면(부모보다 큰 수)
n = n->parent;
t->root = left_rotate(t->root, n);
}
n->parent->color = RBTREE_BLACK;
n->parent->parent->color = RBTREE_RED;
t->root = right_rotate(t->root, n->parent->parent);
}
}
else { // 부모 노드가 조부모 노드의 오른쪽에 있다면
y = n->parent->parent->left; // 삼촌 노드
if (y != NULL && y->color == RBTREE_RED) { // 부모, 삼촌 다 RED
n->parent->color = RBTREE_BLACK;
y->color = RBTREE_BLACK;
n->parent->parent->color = RBTREE_RED;
n = n->parent->parent;
}
else {
if (n == n->parent->left) { // 현재 노드가 왼쪽에 위치한다면
n = n->parent; // 로테이션 할 기준 변경
t->root = right_rotate(t->root, n);
}
n->parent->color = RBTREE_BLACK;
n->parent->parent->color = RBTREE_RED;
t->root = left_rotate(t->root, n->parent->parent);
}
}
}
// t->root->parent = NULL;
t->root->color = RBTREE_BLACK; // 루트 색은 검정!
}
node_t *rbtree_insert(rbtree *t, const key_t key) {
node_t *y = NULL;
node_t *x = t->root;
// 새로 들어올 노드 생성
node_t *n = (node_t *)malloc(sizeof(node_t));
n->color = RBTREE_RED;
n->key = key;
n->left = NULL;
n->right = NULL;
while (x != NULL) { // 노드 n이 들어갈 위치 찾는 과정
y = x; // y는 n의 부모 노드
if (key < x->key) {
x = x->left;
}
else {
x = x->right;
}
}
n->parent = y;
if (y == NULL) { // x가 0이었다면(트리가 없었다면)
t->root = n;
}
else if (key < y->key) {
y->left = n;
}
else {
y->right = n;
}
insert_fixup(t, n);
return n;
}
node_t *rbtree_find(const rbtree *t, const key_t key) {
node_t *find_node;
find_node = t->root;
while (find_node != nil) {
if (key == find_node->key) {
return find_node;
}
if (key < find_node->key) {
find_node = find_node->left;
}
else if (key > find_node->key) {
find_node = find_node->right;
}
return NULL;
}
}
node_t *rbtree_min(const rbtree *t) {
node_t *tmp = t->root;
while (tmp->left != NULL) {
tmp = tmp->left;
}
return tmp;
}
node_t *rbtree_max(const rbtree *t) {
node_t *tmp = t->root;
while (tmp->right != NULL) {
tmp = tmp->right;
}
return tmp;
}
/*rbtree의 특성 유지
노드의 위치를 이동시키는 함수*/
void tree_transplant(rbtree *t, node_t *n1, node_t *n2) {
if (n1->parent == NULL) {
t->root = n2;
}
else if (n1 == n1->parent->left) {
n1->parent->left = n2;
}
else {
n1->parent->right = n2;
}
if (n2 != NULL){
n2->parent = n1->parent; // n1의 부모 노드와 n2의 부모 노드 연결
}
}
// node_nil: x가 없을 때, 더미노드 nil 반환
node_t *node_nil(node_t *x) {
if (x == NULL) {
return nil;
}
else {
return x;
}
}
// successor
node_t *successor(rbtree *t, node_t *x) {
if (x->right != NULL) { // x의 우노드가 존재할 때, 서브트리의 최소값 찾기
node_t *c = x->right;
while (c->left != NULL) {
c = c->left;
}
return c;
}
node_t *p = x->parent;
while (p != NULL && x == p->right) { // x의 우노드가 없을 때, 위로 올라가다 처음 오른쪽 위로 꺾였을 때 첫 노드
x = p;
p = p->parent;
}
return p;
}
// 노드 삭제 시 rbtree 특성 유지시키는 함수
void *erase_fixup(rbtree *t, node_t * x) {
node_t *s; // x노드의 형제 노드
node_t *s_left, * s_right; // s노드의 좌, 우 자식 노드
while (x != t->root && x->color == RBTREE_BLACK) {
if (x == x->parent->left) { // x노드가 왼쪽에 있다면
s = x->parent->right;
if (s->color == RBTREE_RED) { // case1: 형제 노드가 red일 경우
s->color = RBTREE_BLACK;
x->parent->color = RBTREE_RED;
t->root = left_rotate(t->root, x->parent);
s = x->parent->right;
}
s_left = node_nil(s_left);
s_right = node_nil(s_right);
if ((s_left->color == RBTREE_BLACK) && (s_right->color == RBTREE_BLACK)) { // case2: 형제 노드 'black', 형제 노드의 자식 노드 모두 'black'
s->color = RBTREE_RED; // 색상 전환
x = x->parent;
}
else {
if (s_right->color == RBTREE_BLACK) { // case3: 형제 노드 'black', 형제 좌노드 'red', 형제 우노드 'black'
s_left->color = RBTREE_BLACK;
s->color = RBTREE_RED;
t->root = right_rotate(t->root, s); // 단일 회전
s = x->parent->right;
}
s->color = x->parent->color;
x->parent->color = RBTREE_BLACK;
s->right->color = RBTREE_BLACK;
t->root = left_rotate(t->root, x->parent);
x = t->root;
}
}
else {
s = x->parent->left;
if (s->color == RBTREE_RED) {
s->color = RBTREE_BLACK;
x->parent->color = RBTREE_RED;
t->root = right_rotate(t->root, x->parent);
s = x->parent->left;
}
s_left = node_nil(s_left);
s_right = node_nil(s_right);
if ((s_right->color == RBTREE_BLACK) && (s_left->color == RBTREE_BLACK)) {
s->color = RBTREE_RED;
x = x->parent;
}
else {
if (s_left->color == RBTREE_BLACK) {
s_right->color = RBTREE_BLACK;
s->color = RBTREE_RED;
t->root = left_rotate(t->root, s);
s= x->parent->left;
}
s->color = x->parent->color;
x->parent->color = RBTREE_BLACK;
s->left->color = RBTREE_BLACK;
t->root = right_rotate(t->root, x->parent);
x = t->root;
}
}
}
x->color = RBTREE_BLACK;
}
int rbtree_erase(rbtree *t, node_t *p) {
node_t *y = p; // 삭제되거나 이동될 노드
node_t *x; // y의 원래 위치(삭제 or 이동되기 전 위치)
color_t y_or_color = y->color; // y의 원래 색
if (p->left == NULL) { // p노드의 좌노드가 없을 때
x = node_nil(p->right);
tree_transplant(t, p, x);
free(p);
}
else if (p->right == NULL) { // p노드의 우노드가 없을 때
x = node_nil(p->left);
tree_transplant(t, p, x);
free(p);
}
else { // p노드가 자식노드 모두를 가지고 있을 때
y = successor(t, p);
y_or_color = y->color;
x = node_nil(y->right);
if (y->parent == p) {
x->parent = y;
}
else {
tree_transplant(t, y, x);
y->right = p->right;
y->right->parent = y;
}
tree_transplant(t, p, y);
y->left = p->left;
y->left->parent = y;
y->color = p->color;
free(p);
}
if (y_or_color == RBTREE_BLACK) {
erase_fixup(t, x);
}
// 루트가 nil이 될 경우가 발생하기 때문에 nil과 연결 끊기
if (t->root == nil) {
t->root = NULL;
}
else if (nil->parent != NULL) {
if (nil->parent->left == nil) {
nil->parent->left = NULL;
}
else {
nil->parent->right = NULL;
}
}
nil->parent = NULL;
return 0;
}
댓글