자료구조 | Red-Black Tree

자료구조 | Red-Black Tree

반응형

위키백과에 의하면 Red-Black tree(레드-블랙 트리)는 자가 균형 이진 탐색 트리 로서, 대표적으로는 연관 배열 등을 구현하는 데 쓰이는 자료구조라고 한다. 레드-블랙 트리는 복잡한 자료구조지만, 실 사용에서 효율적이며 최악의 경우에도 O(logN) 시간복잡도를 보장할 정도로 안정(balanced)되었다.

즉 레드-블랙 트리는 실시간 처리와 같은 실행 시간이 중요한 경우에 유용하게 쓰이고 일정한 실행 시간을 보장하는 또 다른 자료구조를 만드는 데 좋다고 한다. 예를 들면 각종 기하학 계산에 쓰이는 많은 자료구조들이나 많은 SDK나 라이브러리 세트에서 검색 알고리즘으로 사용되고 있다고 한다.

글을 보면서도 잘 이해가 되지 않아서 많은 자료들을 찾아봤었다. 레드-블랙 트리도 이진탐색트리의 일종인데, 이진탐색트리는 탐색을 위해 사용되는 자료구조다. 자료를 이진트리로 구성하여 검색 구조로 삼는 이유는 단순한 구조이면서도 자료의 검색, 삽입, 삭제가 효율적이기 때문이다.

위의 이진트리 그림을 보면, 루트 노드부터 검색을 시작하게 되고 한 노드는 자식을 두 명까지 가질 수 있다. 또한 자신보다 작은 값의 노드는 왼쪽, 큰 값의 노드는 오른쪽에 두는 규칙을 가지고 있다. 때문에 탐색시 모든 노드를 고려할 필요가 없어서 효율적이다. 예를 들면 위의 트리에서 8을 찾는다고 하면 10->7->8로 두 번의 비교만으로 찾을 수 있다.

마냥 좋을 것 같은 이진탐색트리에도 단점이 있다.

위의 그림처럼 값이 한 쪽으로 쏠리게 들어왔을 경우 가장 아래에 있는 값을 검색하기 위해서는 결국 모든 경우를 고려해야 하고, 이는 일반적인 선형 검색의 시간복잡도 O(N)과 다를 게 없다. 그래서 어떤 상황에서도 O(logN)을 보장하는 RBtree가 많이 사용된다고 한다.

레드-블랙 트리는 각각의 노드가 레드나 블랙의 색상 속성을 가지고 있는 이진 탐색 트리

RBTREE 특성

좋은 효율을 보이는 레드-블랙 트리를 구현하기 위해서는 다음과 같은 조건이 필요하다.

1. 노드는 '레드' 혹은 '블랙' 중 하나이다.

2. 루트 노드는 '블랙'이다.

3. 모든 리프 노드(NIL)들은 '블랙'이다.

4. 노드가 '레드'일 때, 자식 노드 양쪽은 언제나 모두 '블랙'이다. (즉 레드 노드는 연달나 나타날 수 없다)

5. 각 노드에 대해 해당 노드에서 리프 노드를 제외한 자식 노드까지의 모든 경로들은 같은 수의 '블랙' 노드 개수를 가진다.

RBTREE 동작

레드-블랙 트리는 수행 시간을 보장하기 위해 트리를 수정한다. 그 결과 레드-블랙 트리의 특성을 위반하게 되기 때문에 몇몇 노드의 색을 바꾸거나(색상 전환) 포인터 구조를 바꿔야 하는데 이러한 작업을 로테이션이라고 한다. 노드를 삽입하고 삭제하는 과정에서 많은 case들이 존재하는데, 이런 경우들을 고려하여 구현해야 코드가 정상적으로 잘 돌아간다.

코드 구현

#include #include 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; }

반응형

from http://dapsu-startup.tistory.com/85 by ccl(A) rewrite - 2021-10-13 14:00:57