레드블랙트리
높이가 적당히 작은 이진 검색 트리의 높이가 h라고하면 Search, Predecessor, Successor, Minimum, Insert, Delete와 같은 동적 집합 연산이 O(h) 시간에 수행될 수 있다. 하지만, 높이가 크고 편향된 트리가 구성될 경우 연산의 실행 속도는 연결 리스트와 비슷한 정도에 불과해진다. 레드 블랙 트리는 트리가 균형을 이루도록 고안된 검색 트리 구조중 하나로, 기본적인 동적 집합 연산을 최악의 경우에도 O(logn) 시간에 수행하도록 보장한다.
다음의 레드블랙 특성을 만족하는 이진 검색 트리를 레드블랙 트리라고 한다.
1. 모든 노드는 적색이거나 흑색이다.
2. 루트는 흑색이다.
3. 모든 리프(NIL)은 흑색이다.
4. 노드가 적색이면 그 노드의 자식은 모두 흑색이다.
5. 각 노드로부터 그 노드의 자손인 리프로 가는 경로들은 모두 같은 수의 흑색 노드를 포함한다.
회전
이진 검색 트리 특성을 보전해주기 위해 노드를 국소적으로 회전 시킨다. 노드 x에 대해서 좌회전을 적용할 때 오른쪽 자식 y는 T.nil 이 아니라고 가정한다. 즉, x는 오른쪽 자식이 T.nil 이 아닌 모든 노드에 대해 해당한다. 좌회전은 x와 y를 연결하는 링크를 중심축으로 하여 적용된다. 그 결과 y는 서브 트리의 새로운 루트가 되며, x는 y의 왼쪽 자식이 되고 y의 왼쪽 자식은 x의 오른쪽 자식이 된다.
우회전은 좌회전과 대칭이고, 두 연산 모두 O(1)시간에 수행된다. 회전을 통해 포인터만 변경되며 다른 필드는 그대로 유지된다.
- C언어로 구현한 트리의 회전
void left_rotation(rbtree* t, node_t* x) {
node_t* y = x->right;
x->right = y->left;
if (y->left != t->nil) {
y->left->parent = x;
}
y->parent = x->parent;
if (x->parent == t->nil) {
t->root = y;
} else if (x == x->parent->left) {
x->parent->left = y;
} else {
x->parent->right = y;
}
y->left = x;
x->parent = y;
return;
}
void right_rotation(rbtree* t, node_t* x) {
node_t* y = x->left;
x->left = y->right;
if (y->right != t->nil) {
y->right->parent = x;
}
y->parent = x->parent;
if (x->parent == t->nil) {
t->root = y;
} else if (x == x->parent->right) {
x->parent->right = y;
} else {
x->parent->left = y;
}
y->right = x;
x->parent = y;
return;
}삽입
n개의 노드로 이루어진 레드블랙 트리에서 노드 하나를 삽입하는 것은 O(logn)시간에 수행될 수 있다. 이진 탐색 트리의 삽입 프로시저를 변형시켜 사용하게 되는데, 일반적인 BST의 삽입과 다르게 RedBlackTree의 구조를 유지하기 위해 삽입되는 노드 z의 자식들이 T.nil로 지정된다. 노드 z를 삽입한 뒤 적색으로 칠하고, 이 때 레드블랙 특성을 만족함을 보장하기 위해 보조 프로시저 RB-INSERT-FIXUP을 호출해 노드의 색을 바꾸고 회전을 수행한다.
node_t *rbtree_insert(rbtree *t, const key_t key) {
node_t* y = t->nil;
node_t* x = t->root;
while (x != t->nil) {
y = x;
if (key < x->key) {
x = x->left;
} else {
x = x->right;
}
}
node_t* z = (node_t *)calloc(1, sizeof(node_t));
z->parent = y;
if (y == t->nil) {
t->root = z;
} else if (key < y->key) {
y->left = z;
} else {
y->right = z;
}
z->key = key;
z->color = RBTREE_RED;
z->left = t->nil;
z->right = t->nil;
rbtree_insert_fixup(t, z); // fixup 호출
return t->root;
}RB-INSERT-FIXUP은 삽입을 통해 발생하는 RB특성 위반을 다음과 같이 나눠 해결한다.
case 1) z의 삼촌 y가 적색인 경우
- z의 부모노드(z.parent)와 삼촌(y)을 흑색으로 칠해 z와 z.p가 모두 적색이라는 문제를 해결한다.
- 조부모노드(z.parent.parent)를 적색으로 칠해서 특성5를 만족시킬 수 있다.
- z.p.p를 새로운 z로 놓고 while루프를 반복한다.
case 2) z의 삼촌 y가 흑색이며 z가 왼쪽 자식인 경우
-
케이스 2,3에서 z의 삼촌 y는 흑색이다. 두 경우는 z가 z.parent의 왼쪽 자식인지 오른쪽 자식인지에 따라 구분된다.
( z의 부모노드를 z와 반대방향으로 회전시킨다 -> z가 부모가 있던 위치로 간다) -
2번 케이스에서 z는 부모의 왼쪽 자식이다. 여기에 우회전을 적용하여 꿈으로써 3번 케이스의 상황으로 바꿀 수 있다. z와 z.parent 모두 적색이기 때문에 회전에 의해 노드의 black height 나 특성5 에는 영향을 주지 않는다. 반대의 경우( 부모노드가 조부모의 왼쪽 자식, z가 부모의 오른쪽 자식)도 동일하게 적용된다.
case 3) z의 삼촌 y가 흑색이며 z가 오른쪽 자식인 경우
( Z의 조부모 노드를 z의 반대방향으로 회전한다 -> z의 부모가 조부모의 위치로 간다.
그리고 z의 부모와 조부모의 색을 바꾼다.)
- 3번 케이스에서 일부 노드의 색깔이 바뀌고 회전이 수행되는데, 이로 인해 특성5 가 보존되며, 두 개의 적색 노드가 연달아 존재하지 않기 때문에 목적이 달성된다. z.parent가 흑색이므로 while루프는 더 이상 수행되지 않는다. 마찬가지로 반대의 경우( 부모 노드가 조부모의 왼쪽자식, z가 부모의 왼쪽자식)에도 적용된다.
void rbtree_insert_fixup(rbtree *t, node_t *z) {
while (z->parent->color == RBTREE_RED) { // z의 부모가 적색
if (z->parent == z->parent->parent->left) {
node_t *y = z->parent->parent->right;
if (y->color == RBTREE_RED) { // case 1) z의 삼촌의 색이 적색
z->parent->color = RBTREE_BLACK;
y->color = RBTREE_BLACK;
z->parent->parent->color = RBTREE_RED;
z = z->parent->parent;
} else { // case 2) z의 삼촌이 흑색
if (z == z->parent->right) {
z = z->parent;
left_rotation(t, z);
} // case 3) z의 삼촌이 흑색이고 z가 부모의 왼쪽 자식
z->parent->color = RBTREE_BLACK;
z->parent->parent->color = RBTREE_RED;
right_rotation(t, z->parent->parent);
}
} else { // z의 부모가 z의 조부모의 오른쪽자식이라면 왼쪽과 반대로 실시
node_t *y = z->parent->parent->left;
if (y->color == RBTREE_RED) {
z->parent->color = RBTREE_BLACK;
y->color = RBTREE_BLACK;
z->parent->parent->color = RBTREE_RED;
z = z->parent->parent;
} else {
if (z == z->parent->left) {
z = z->parent;
right_rotation(t, z);
}
z->parent->color = RBTREE_BLACK;
z->parent->parent->color = RBTREE_RED;
left_rotation(t, z->parent->parent);
}
}
}
t->root->color = RBTREE_BLACK;// 특성 2을 유지하기 위해 root는 항상 BLACK
return;
}RB-INSERT의 시간복잡도
노드가 n개인 레드블랙 트리의 높이는 O(logn)이므로 삽입에는 O(logn) 시간이 걸린다. RB-INSERT-FIXUP에서 while루프가 반복되는 경우는 case1 뿐이며, 이 때 포인터 z는 두 단계씩 위로 이동한다. 즉, while 루프가 반복될 수 있는 횟수는 O(logn)이다. 따라서 RB-INSERT는 총 O(logn) 시간에 수행된다. 또한 while루프는 case2나 case3일 때 종료하므로 최대 두번만 일어나게 된다.
삭제
레드 블랙트리에서 노드를 삭제하는 프로시저는 BST-DELETE 프로시저를 기반으로 하지만, 이의 서브 루틴인 TRANSPLANT를 레드 블랙 트리에 맞게 수정해야한다.
노드 z를 삭제하려 할 때, 이 노드가 하나 이하의 자식을 가지고 있을 때는 z가 트리에서 제거되며 y를 z로 설정한다. z가 두 개의 자식을 가지고 있을 때, y는 z의 Successor가 되어야 하며 y는 z의 원래 위치로 이동한다. 또한 y가 제거되거나 이동하기 전의 색깔을 저장하며 y의 원래 위치로 이동하는 노드 x도 관리하는데, 이는 노드x도 레드블랙 특성을 위반할 수 있기 때문이다. 노드 z를 삭제한 후 RB-DELETE에서 보조 프로시저인 RB-DELETE-FIXUP을 호출하며 여기서는 레드블랙 특성을 복구하기 위해 색 변경과 회전이 일어난다.
void rbtree_transplant(rbtree *t, node_t *u, node_t * v) {
if (u->parent == t->nil) {
t->root = v;
} else if (u == u->parent->left) {
u->parent->left = v;
} else {
u->parent->right = v;
}
v->parent = u->parent;
return;
}
int rbtree_erase(rbtree *t, node_t *p) {
node_t *x;
node_t *y = p;
color_t y_color = y->color;
if (p->left == t->nil) {
x = p->right;
rbtree_transplant(t, p, p->right);
} else if (p->right == t->nil) {
x = p->left;
rbtree_transplant(t, p, p->left);
} else { // 삭제할 노드의 왼쪽, 오른쪽 자식이 둘다 있을 때
y = rbtree_successor(t, p->right); // y = Successor
y_color = y->color;
x = y->right;
if (y->parent == p) {
x->parent = y;
} else {
rbtree_transplant(t, y, y->right);
y->right = p->right;
y->right->parent = y;
}
rbtree_transplant(t, p, y); // 삭제할 노드 부모와 y를 연결
y->left = p->left;
y->left->parent = y;
y->color = p->color;
}
free(p);
p = NULL;
if (y_color == RBTREE_BLACK) { // 삭제한 노드의 색이 BLACK일 때(특성 5 위반) 색을 바꾼다
rb_delete_fixup(t, x);
}
return 0;
}노드의 삭제 후 다음 네가지 케이스로 나눠져 특성 1, 2, 4를 복구한다
case 1) x의 형제 w가 적색인 경우
- 노드x의 형제 w가 적색인 경우, w가 흑색 자식 노드를 가져야 하므로 w와 x.parent의 색깔을 바꾼다
- x.parent를 기준으로 좌회전을 수행한다. x의 형제는 원래 w의 자식이였는데 현재는 x의 형제,흑색이므로 케이스 2,3,4 중 하나로 케이스가 바뀌게 된다.
case 2) x의 형제 w가 흑색이고 w의 두 자식이 모두 흑색인 경우
- x와 w에서 흑색을 하나씩 제거해 x를 순수(단일)흑색으로 두고 w를 적색으로 바꾼다.
- 제거한 흑색을 보충하기 위해 x.parent에 여분의 흑색을 하나 추가하게 된다. 이는 x.parent를 새로운 x로 두고 while 루프를 반복함으로써 이루어진다.
case 3) x의 형제 w는 흑색, w의 왼쪽 자식은 적색, w의 오른쪽 자식은 흑색인 경우
- w와 왼쪽 자식 w.left의 색을 바꾸고 w에 대해 우회전을 수행한다. 이에 따라 case 3는 case 4가 된다.
case 4) x의 형제 w는 흑색이고 w의 오른쪽 자식은 적색인 경우
- 노드의 색깔을 바꾸고 x.parent에 대해 좌회전을 함으로써 x의 여분 흑색을 지우고 순수한 흑색으로 바꾼다.
- x가 루트가 되면 루프 조건의 검사 때 while루프는 종료된다.
void rb_delete_fixup(rbtree *t, node_t *x){
node_t *w;
while ((x != t->root) && (x->color == RBTREE_BLACK)) {
if (x == x->parent->left) {
w = x->parent->right;
if (w->color == RBTREE_RED) {// case 1) x의 형제가 적색
w->color = RBTREE_BLACK;
x->parent->color = RBTREE_RED;
left_rotation(t, x->parent);
w = x->parent->right;
}// case 2) x의 형제 w와 그 자식 모두 흑색
if (w->left->color == RBTREE_BLACK && w->right->color == RBTREE_BLACK) {
w->color = RBTREE_RED;
x = x->parent;
} else {// case 3) x의 형제 w는 흑색, 그 왼쪽자식은 적, 오른쪽은 흑
if (w->right->color == RBTREE_BLACK) {
w->left->color = RBTREE_BLACK;
w->color = RBTREE_RED;
right_rotation(t, w);
w = x->parent->right;
}
w->color = x->parent->color;// case 4) x의 형제 w는 흑색, 그 오른쪽 자식은 적색
x->parent->color = RBTREE_BLACK;
w->right->color = RBTREE_BLACK;
left_rotation(t, x->parent);
x = t->root;
}
} else {
w = x->parent->left;
if (w->color == RBTREE_RED) {
w->color = RBTREE_BLACK;
x->parent->color = RBTREE_RED;
right_rotation(t, x->parent);
w = x ->parent->left;
}
if (w->right ->color == RBTREE_BLACK && w->left->color == RBTREE_BLACK) {
w->color = RBTREE_RED;
x = x->parent;
} else {
if (w->left->color == RBTREE_BLACK) {
w->right->color = RBTREE_BLACK;
w->color = RBTREE_RED;
left_rotation(t, w);
w = x->parent->left;
}
w->color = x->parent->color;
x->parent->color = RBTREE_BLACK;
w->left -> color = RBTREE_BLACK;
right_rotation(t, x->parent);
x = t->root;
}
}
}
x->color = RBTREE_BLACK;
return;
}RB-DELETE의 시간복잡도
노드가 n개인 레드블랙 트리의 높이는 O(logn)이므로 RB-DELETE-FIXUP 호출을 제외한 프로시저의 총 비용은 O(logn) 시간이다. RB-DELETE-FIXUP에서 case 1, 3, 4는 정해진 횟수의 색깔 변경과 최대 세 번의 회전 후 종료된다. case 2에 해당할 때만 while루프가 반복되는데, 이 때 포인터 x는 트리를 따라 최대 O(logn) 번 위로 움직이고 회전은 수행되지 않는다. 따라서 RB-DELETE-FIXUP은 O(logn) 시간이 소요되고 최대 세 번의 회전을 수행하게 되어 RB-DELETE의 총 수행시간도 O(logn) 이 된다.
전체 코드
Sentinel을 이용해 c 언어로 RBTree를 구현했다.
Sentinel : 보초병, 감시병(syn: sentry)
경계노드 라는 의미로 쓰인다. 한계 조건을 간단하게 해주는 더미객체로, 이를 통해 노드x의 NIL 자식을 x의 정상적인 자식 노드와 동일하게 다룰 수 있게 된다. 트리 내 각각의 NIL을 위해 개별적인 경계 노드를 사용할 수 있지만 그렇게 한다면 저장공간이 낭비되게 된다. 하나의 경계노드 T.nil을 두어서 모든 NIL, 즉 모든 리프와 루트의 부모를 표현한다.
구현 범위:
- tree = new_tree(): RB Tree 구조체 생성
- delete_tree(tree): RB Tree 구조체가 차지했던 메모리 반환
- tree_insert(tree, key): key 추가
- ptr = tree_find(tree, key): RB Tree 내 해당 key가 있는지 탐색하여 있으면 node pointer 반환; 없으면 NIL 반환
- tree_erase(tree, ptr): ptr로 지정된 node 삭제 및 메모리 반환
- ptr = tree_min(tree): RB Tree 중 최소값을 가진 node pointer 반환
- ptr = tree_max(tree): RB Tree 중 최대값을 가진 node pointer 반환
- tree_to_array(tree, array, n): RB Tree의 내용을 key 순서대로 주어진 array 반환; array의 크기는 n으로 주어지며 tree의 크기가 n보다 큰 경우에는 순서대로 n개 까지만 반환
#include "rbtree.h"
#include <stdlib.h>
// 트리 초기화
rbtree *new_rbtree(void) {
rbtree *t = (rbtree *)calloc(1, sizeof(rbtree));
node_t *nil_node = (node_t *)calloc(1, sizeof(node_t));
nil_node->color = RBTREE_BLACK;
t->nil = nil_node;
t->root = nil_node;
return t;
}
// 각각의 노드들이 가리키는 공간들 해제
void delete_node(node_t *node, rbtree *t) {
// 현재 노드가 트리의 nil노드면 return
if (node == t->nil) {
return;
}
delete_node(node->left, t); // 왼쪽으로 재귀
delete_node(node->right, t); // 오른쪽으로 재귀
free(node); // 현재 노드가 가리키는 메모리 할당 해제
node = NULL; // 할당 해제 후 현재 노드값을 NULL로 초기화
return;
}
// 트리, 트리의 nil이 가리키는 공간 해제
void delete_rbtree(rbtree *t) {
// 트리가 없으면 return
if (t == NULL) {
return;
}
delete_node(t->root, t); // 생성된 노드들이 가리키는 메모리 해제
free(t->nil); // 트리의 nil노드가 가리키는 메모리 해제
t->nil = NULL; // 메모리 해제 후 트리의 nil노드값을 NULL로 초기화
free(t); // 트리가 가리키는 메모리 할당 해제
return;
}
// 좌회전
void left_rotation(rbtree* t, node_t* x) {
node_t* y = x->right;
x->right = y->left;
if (y->left != t->nil) { // y의 왼쪽이 nil이 아니면
y->left->parent = x; // y의 왼쪽 부모 x로 변경
}
y->parent = x->parent; // y의 부모를 x의 부모로 변경
if (x->parent == t->nil) { // x의 부모가 nil이라면 루트라는 뜻
t->root = y; // 트리의 루트를 y로 변경
} else if (x == x->parent->left) { // x가 x의 부모의 왼쪽 자식이라면
x->parent->left = y; // x의 부모의 왼쪽자식을 y로 변경
} else { // x가 x의 부모의 오른쪽 자식이라면
x->parent->right = y; // x의 부모의 오른쪽자식을 y로 변경
}
y->left = x; // y의 왼쪽자식을 x로 변경
x->parent = y; // x의부모 = y
return;
}
// 우회전(좌회전과 대칭, 반대로)
void right_rotation(rbtree* t, node_t* x) {
node_t* y = x->left;
x->left = y->right;
if (y->right != t->nil) {
y->right->parent = x;
}
y->parent = x->parent;
if (x->parent == t->nil) {
t->root = y;
} else if (x == x->parent->right) {
x->parent->right = y;
} else {
x->parent->left = y;
}
y->right = x;
x->parent = y;
return;
}
// 색 변경
void rbtree_insert_fixup(rbtree *t, node_t *z) {
while (z->parent->color == RBTREE_RED) { // z의 부모가 RED일 경우
if (z->parent == z->parent->parent->left) { // z의 부모가 z의 조부모의 왼쪽 자식이면
node_t *y = z->parent->parent->right; // y는 z의 조부모의 오른쪽 자식(삼촌)
if (y->color == RBTREE_RED) { // case 1) z의 삼촌이 빨강일 경우
z->parent->color = RBTREE_BLACK; // z의 부모 BLACK으로 변경
y->color = RBTREE_BLACK; // z의 삼촌 BLACK으로 변경
z->parent->parent->color = RBTREE_RED; // z의 조부모 RED로 변경
z = z->parent->parent; // z = 조부모
} else { // case 2) z의 삼촌이 검정일 경우
if (z == z->parent->right) { // z가 오른쪽 자식일 경우
z = z->parent; // z를 z의 부모로 변경
left_rotation(t, z); // z를 기준으로 좌회전
} // case 3) z의 삼촌이 검정이고 z가 왼쪽 자식일 때
z->parent->color = RBTREE_BLACK; // z의 부모 검정으로 변경
z->parent->parent->color = RBTREE_RED; // z의 조부모 빨강으로 변경
right_rotation(t, z->parent->parent); // z의 조부모 기준으로 우회전
}
} else { // z의 부모가 z의 조부모의 오른쪽이라면 왼쪽case의 반대로
node_t *y = z->parent->parent->left;
if (y->color == RBTREE_RED) {
z->parent->color = RBTREE_BLACK;
y->color = RBTREE_BLACK;
z->parent->parent->color = RBTREE_RED;
z = z->parent->parent;
} else {
if (z == z->parent->left) {
z = z->parent;
right_rotation(t, z);
}
z->parent->color = RBTREE_BLACK;
z->parent->parent->color = RBTREE_RED;
left_rotation(t, z->parent->parent);
}
}
}
t->root->color = RBTREE_BLACK; // 특성 2을 유지하기 위해 root BLACK으로 설정
return;
}
// 삽입
node_t *rbtree_insert(rbtree *t, const key_t key) {
node_t* y = t->nil; // y는 트리의 nil노드
node_t* x = t->root; // x는 트리의 root노드
while (x != t->nil) { // 서브트리 탐색
y = x;
if (key < x->key) {
x = x->left;
} else {
x = x->right;
}
}
node_t* z = (node_t *)calloc(1, sizeof(node_t)); // z(노드) 생성
z->parent = y; // z의 부모 = y
if (y == t->nil) { // y가 트리의 nil일 때(첫 노드 삽입)
t->root = z; // 트리의 root = z
} else if (key < y->key) { // y의 key값이 삽입할 키 값보다 작을 때
y->left = z; // 왼쪽 서브트리 탐색
} else { // y의 key값이 삽입할 키 값보다 크거나 같을 때
y->right = z; // 오른쪽 서브트리 탐색
}
z->key = key; // z의 key값은 현재 key
z->color = RBTREE_RED; // z의 color값은 RED, 삽입할 때는 무조건 RED
z->left = t->nil; // 좌 / 우 자식 NIL 연결
z->right = t->nil;
rbtree_insert_fixup(t, z); // fixup 호출
return t->root; // 트리의 root값 반환
}
// 트리에서 원하는 값 찾기
node_t *rbtree_find(const rbtree *t, const key_t key) {
node_t *x = t->root; // x는 트리의 루트
while (x != t->nil && key != x->key) { // 서브트리 탐색
if (x->key < key) {
x = x->right;
} else {
x = x->left;
}
}
if (x == t->nil) { // x가 nil노드면, 즉 key를 찾지 못했을 때
return NULL; // NULL 반환
}
return x; // x가 nil노드가 아니면 x 반환, 즉 key를 찾았을 때
}
// 트리의 최솟값
node_t *rbtree_min(const rbtree *t) {
node_t *x = t->root; // 트리에서 가장 작은 값은 트리의 가장 왼쪽에 위치한다
while (x->left != t->nil) {
x = x->left;
}
return x; // x 반환
}
// 트리의 최댓값
node_t *rbtree_max(const rbtree *t) {
node_t *x = t->root; // 트리에서 가장 작은 값은 트리의 가장 오른쪽에 위치한다
while (x->right != t->nil) {
x = x->right;
}
return x; // x 반환
}
// u의 부모와 v와 연결
void rbtree_transplant(rbtree *t, node_t *u, node_t * v) {
if (u->parent == t->nil) { // u의 부모가 nil일 때, 즉, 삭제할 노드가 트리의 root면
t->root = v; // 트리의 root는 v
} else if (u == u->parent->left) { // u가 u의 부모의 왼쪽 자식이면
u->parent->left = v; // u의 부모의 왼쪽 자식 v
} else { // u가 u의 부모의 오른쪽 자식이면
u->parent->right = v; // u의 부모의 오른쪽 자식은 v
}
v->parent = u->parent; // v의 부모는 u의 부모
return;
}
void rb_delete_fixup(rbtree *t, node_t *x){
node_t *w;
while ((x != t->root) && (x->color == RBTREE_BLACK)) {
if (x == x->parent->left) {
w = x->parent->right;
if (w->color == RBTREE_RED) {
w->color = RBTREE_BLACK;
x->parent->color = RBTREE_RED;
left_rotation(t, x->parent);
w = x->parent->right;
}
if (w->left->color == RBTREE_BLACK && w->right->color == RBTREE_BLACK) {
w->color = RBTREE_RED;
x = x->parent;
} else {
if (w->right->color == RBTREE_BLACK) {
w->left->color = RBTREE_BLACK;
w->color = RBTREE_RED;
right_rotation(t, w);
w = x->parent->right;
}
w->color = x->parent->color;
x->parent->color = RBTREE_BLACK;
w->right->color = RBTREE_BLACK;
left_rotation(t, x->parent);
x = t->root;
}
} else {
w = x->parent->left;
if (w->color == RBTREE_RED) {
w->color = RBTREE_BLACK;
x->parent->color = RBTREE_RED;
right_rotation(t, x->parent);
w = x ->parent->left;
}
if (w->right ->color == RBTREE_BLACK && w->left->color == RBTREE_BLACK) {
w->color = RBTREE_RED;
x = x->parent;
} else {
if (w->left->color == RBTREE_BLACK) {
w->right->color = RBTREE_BLACK;
w->color = RBTREE_RED;
left_rotation(t, w);
w = x->parent->left;
}
w->color = x->parent->color;
x->parent->color = RBTREE_BLACK;
w->left -> color = RBTREE_BLACK;
right_rotation(t, x->parent);
x = t->root;
}
}
}
x->color = RBTREE_BLACK;
return;
}
// successor찾기, 삭제할 노드의 오른쪽 자식을 루트로 하는 서브트리의 최솟값
node_t *rbtree_successor(rbtree *t, node_t *x) {
node_t *y = x;
while (y->left != t->nil) {
y = y->left;
}
return y;
}
int rbtree_erase(rbtree *t, node_t *p) {
node_t *x; // 노드 x
node_t *y = p; // y = 삭제할 노드
color_t y_color = y->color; // y_color는 y의 색
if (p->left == t->nil) { // 삭제할 노드의 왼쪽이 nil일 경우
x = p->right; // x는 삭제할 노드의 오른쪽
rbtree_transplant(t, p, p->right); // 삭제할 노드의 부모와 삭제할 노드의 오른쪽을 연결
} else if (p->right == t->nil) { // 삭제할 노드의 오른쪽이 nil일 경우
x = p->left; // x = 삭제할 노드의 왼쪽자식
rbtree_transplant(t, p, p->left); // 삭제할 노드의 부모와 삭제할 노드의 왼쪽을 연결
} else { // 삭제할 노드의 왼쪽, 오른쪽 자식이 둘다 있을 때
y = rbtree_successor(t, p->right); // y = successor
y_color = y->color; // y_color는 직후 원소의 색
x = y->right; // x = y의 오른쪽 자식
if (y->parent == p) { // y의 부모가 삭제할 노드일 때
x->parent = y; // x의 부모 = y
} else { // y의 부모가 삭제할 노드가 아닐 때
rbtree_transplant(t, y, y->right); // y의 부모와 y의 오른쪽 자식을 연결
y->right = p->right; // y의 오른쪽 자식 = 삭제할 노드의 오른쪽 자식
y->right->parent = y; // y의 오른쪽 자식의 부모 = y
}
rbtree_transplant(t, p, y); // 삭제할 노드 부모와 y를 연결
y->left = p->left; // y의 왼쪽 자식 = 삭제할 노드의 왼쪽 자식
y->left->parent = y; // y의 왼쪽 자식의 부모 = y
y->color = p->color; // y의 색 = 삭제할 노드의 색
}
free(p); // 삭제한 노드가 가리키는 공간 삭제
p = NULL; // 할당 해제 후 삭제한 노드값을 NULL로 초기화
if (y_color == RBTREE_BLACK) { // y_color가 BLACK이면(삭제한 노드의 색이 BLACK이면(특성 5 위반))
rb_delete_fixup(t, x); // fixup 호출
}
return 0;
}
// 트리의 중위 순회
// root 노드는 계속 변화
int rbtree_inorder(node_t *nil, node_t *root, key_t *arr, const size_t n, int index) {
if (root == nil) { // root노드가 nil노드면
return index; // index 반환
}
if (index == n) { // index가 n하고 같을 때 더 이상 재귀 돌지 않게 종료 조건
return index; // index반환
}
index = rbtree_inorder(nil, root->left, arr, n, index); // 왼쪽으로 재귀
if(index < n) { // idenx가 n보다 작을 때만 arr에 추가
arr[index++] = root->key; // arr[현재 index] = 현재 노드의 키 값
}
index = rbtree_inorder(nil, root->right, arr, n, index); // 오른쪽으로 재귀
return index; // index 반환
}
// 트리를 이용하여 오름차순 구현
int rbtree_to_array(const rbtree *t, key_t *arr, const size_t n) {
// 트리의 루트가 nil노드일 때 반환
if (t->root == t->nil) {
return 0;
}
rbtree_inorder(t->nil, t->root, arr, n, 0); // 중위 순회
return 0;
}
0개의 댓글
