....
개요
RB트리는,
Red와 Black으로
규칙을 설정하여,
규칙을 따르면 Balenced Tree가 되도록 유지시켜
평균 검색속도를 O(log N)으로 지속하게 하는 트리다.
노드를 추가할 때,(삽입할 때,)
노드를 삭제할 때,
이진 트리의 법칙을 따르지만,
그렇게 삽입과 삭제를 거치고 나면
속성 5가지가 모두 위배되지 않는지 확인하고,
위배한다면,
위배하지 않도록 조정시킨다.
속성 다섯 가지는 이렇다.
(속성 다섯 가지가 코드에서 실제로 어떠한 조건문으로 존재하진 않지만,
그러한 속성을 유지시키기 위한 조건들은 존재한다.)
- 모든 노드는 RED/Black
- 루트 노드는 Black
- 모든 NIL 노드는 BLACK
- 노드가 RED면, 자녀는 BLACK
(즉, RED는 연속해서 있어서는 안된다.)
(BLACK이 연속해서 있으면 안된다는 얘기도 아니며,
같은 레벨은 색이 일치해야한다는 얘기도 아니다.)- 임의의 경로(자신을 제외)부터 자손 NIL까지 BLACK 개수는 동일하다.
? NIL 노드?
NIL 노드는 이 RB트리의 리프 노드 자리에,
(그러니까 원래라면 리프노드로 해당할 자리의 노드가,)
NIL노드를 가지고 있다.
정확히 말하자면,
Sentilnel 노드로,
경계 노드라고도 하는데,
보통 아래에 노드가 이어지지 않으면 NULL 을 자식 속성으로 갖겠지만,
여기 RB트리에서는 NIL 노드라고
경계 노드를 세워서 비어있을 자식 속성에 대신 채워둔다.
이건 자식에 한정된 게 아니라,
루트 노드의 부모 또한 NIL 노드로 설정하는데,
엄밀히 따지자면 RB트리의 경계선을 나타낸다고 보는게 좋을거같다.
이러한 게 존재하는 이유는 RB트리의 구현때문이다.
RB 트리는 임의의 노드를
다른 노드와 대체하거나, 이동하는 경우가 많다.
그러나 이때 NIL이라는, 노드 특성을 가지지만
값은 가지지 않는 노드를 설정하지 않는다면,
NULL일때의 케이스를 따로 조건문으로 만들어줘야한다.
(보통 NULL은 색상, 부모, 왼쪽, 오른쪽, 같은 속성이 없을테니까.)
(코드를 그대로 쓰면 Index error 같은게 날것이다.)
NIL이라면 케이스를 따로 빼지 않아도,
최소한만 설정해서
(예를 들어, 아무튼 NIL이면
자리를 대체할때 부보-자식, 자식-부모 둘다 설정하지만
NIL의 부모가 누구인지 까지 설정할 필요는 없을테니까.)
코드를 간결하게 구현할 수 있다.
흠! 생각해보니 꽤 인상깊네.
실제로도 속성을 그대로 갖지만 아무역할도 하지 않는
동일한 데이터속성을 버퍼처럼 넣는다는것은
좋은 아이디어인 것 같다.
다만 AVL 트리 같은 경우는 똑같이 회전을 해도
굳이 NIL노드 같은 것을 만들지 않는데,
색상 등의 속성을 확인하지 않기때문인 것 같다...
필수
이 곳은
Tree 생성, 삭제,
그리고 삽입과 삭제를 구현하기 위해서
필수적으로 필요한 함수들인 회전 함수, 대체 함수를 서술한다.
new, delete Tree
new
Tree를 생성하는 함수.
C에서는 자료구조를 만들기 위해서
앞으로 사용할 자료구조의 메모리를 할당해줘야한다.
그래서 대개 메모리 할당이 어떻게 이루어지냐면
그만큼의 메모리를 사용할 '포인터'를 반환한다.
어떠한 규칙을 갖고 이동하는 포인터를,
그만큼의 규칙만큼 이동할 수 있도록 넉넉한 자리가 확보된 시작 주소와 함께
생성하는 것이다.
포인터의 규칙은 이렇다.
배정받은 자료형의 크기만큼 이동한다.
...그렇다!
그래서 맨처음에 무슨 자료형을 담당하는 지 선언한 뒤,
시작 주소를 어디로 줄지 앞으로 쓸 용량에 따라 배정(할당)해주는 것이다.
그래서 new를 선언하는 (init이라고도 한다.)
함수는 포인터와, malloc으로 선언하면 끝이지만,
추가적으로 초기화해줘야하는 변수가 있다면 추가로 설정한다.
우리는 검정색 속성이 있는 nil노드를 설정해줄 것이기때문에
이렇게 된다.
rbtree *new_rbtree(void) {
// rbtree 크기의 1개를 할당.
rbtree *p = (rbtree *)calloc(1, sizeof(rbtree));
// 여기서 nil도 일종의 노드 처럼 할당해서 검정 속성 부여.
if (p != NULL){
p->nil= (node_t*)calloc(1,sizeof(node_t));
p->nil->color = RBTREE_BLACK;
p->root = p->nil;
return p;
}
else{
return 0;
}
}delete
트리를 삭제하는 함수.
root를 찾아서,
중위 순회....를 하려했지만
그러면 나중에 다시한번 재귀로 빠질때
위치를 상실하기때문에
결국 구현은 후위 순회로 했다.
노드를 먼저 찾아서 다 free한 다음에,
tree 자체도 free 해준다!
// 트리 지우기
void delete_rbtree(rbtree *t) {
node_t *y= t->root;
inorder_tree_free(t, y);
free(t->nil);
free(t);
t = NULL;
}Rotate
골자는 이렇다.
왼쪽 회전
: 왼쪽 자식(x) - 부모 노드(y)
-> 부모 노드(x)- 오른쪽 자식
오른쪽 회전
: 부모 노드(x) - 오른쪽 자식(y)
-> 왼쪽 자식(x) - 부모 노드(y)
...인 것이다!
그런데,
트리에서 어떤 특정 노드의 위치는
두 가지 속성으로 정의된다.
- parent 기준으로 어느쪽 자식인가?
- 자식 기준으로 누가 부모인가?
즉, 특정 노드를 호출할 때
x가 부모의 왼쪽 자식이라고 가정하면,
(x->parent)->left와
x->parent = (x->parent) 라는 것이다...
.......
이렇게 나란히 두니 좀 헷갈리므로
x->parent를 p라고 한다면
p->left = x와
x->parent = p를
둘다 설정해야한다는 것이다!
그래서 rotate함수는
각각의 노드를 서로의 부모, 자식 관계 값에 대신 넣는다.
어떤 것이 값이고,
어떤 것이 위치인지 잘 구분할 수 있다면 어렵지 않다.
그림을 그려두고 생각한다면 더 쉬울 것이다!
구현 코드.
// 왼쪽으로 회전.
//(x의 오른쪽 자식 노드 y가 x자리에,)
//(x는 y의 왼쪽 자식이 된다.)
void left_rotate(rbtree *t, node_t *x){
node_t *y;
// y가 x의 오른쪽 자식일때.
y = x->right;
if(y != t->nil){
// (손자 정리 시즌)
// x의 오른쪽에는, 오른쪽 자식y의 왼쪽 자식(손자) 트리를 붙인다.
x->right = y->left;
// 근데 y의 왼쪽 자식이 nil이 아니라면 그 노드의 부모도 설정해준다.
if (y->left != t->nil){
y->left->parent = x;
}
// (y 이동 시즌 )
// 그리고 y도 자리를 옮겨, y도 부모를 설정해준다.
y->parent = x->parent;
// 만약 y가 최고 조상이었으면, root임을 알려준다.
if (x->parent == t->nil){
t->root = y;
}
// 조상의 왼쪽 자식이었으면, y도 왼쪽 자식.
else if (x == x->parent->left)
{
x->parent->left = y;
}
// 조상의 오른쪽 자식이었으면, y도 오른쪽 자식.
else {
x->parent->right = y;
}
// (x 이동 시즌)
// y의 자식으로 x를, x부모에도 y를 설정.
y->left = x;
x->parent = y;}
}이러한 방식으로 오른쪽 회전도 구현하면 된다.
(약간 책이 이렇게 써놓은 이유를 이해하고 말았다.)
Transplant
삭제 시,
삭제하는 노드의 위치를
노드의 자식 중에 대체하는 경우가 있다.
(만약 자식이 없다면 대체할 필요가 없긴 하겠지만.)
그 때의 경우를 따로 함수로 뺐다.
이 역시,
nil도 노드이기때문에
이러한 함수 구현에 들어와도 별로 문제가 없다.
이는 삭제 시 대체하는 함수이기때문에,
두 노드 다 자식과 부모를 갱신해주지 않고,
새로 들어오는 노드만
(원래 삭제하는 노드는 자리를 설정해줄 필요 없지 않겠는가?)
자식 부모 관계를 설정해주는 함수다.
// rb트리에서 두 노드의 자리를 바꾸는 함수.
// 정확히는 u자리에 v만 들어갈뿐임.(v자리는 아무도 안들어감.)
void rb_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;
}삽입
이진 트리를 따라,
루트에서 시작하여
리프 노드까지 나아가
대응하는 위치에 추가한다.
단, 넣을 때는 무조건 RED 속성으로 시작하여,
만약 부모 노드가 RED라면 레드블랙트리의 4번 속성을 위반하게 되면서,
임의의 속성 위반을 고치기 위한 로직을 따르게 된다.
(아! 그래서 레드 블랙이라는 개념을 만들었나보다.)
(새로 어떠한 노드를 삽입할 때,
연달아 삽입한다면 모두 RED일텐데,
거기서 균형 조정이 더 필요한 트리,
즉, 들어온지 얼마 안 된 서브 트리가
높은 확률로 그 트리의 리프 노드가 RED일 테니,
무게가 클테므로(노드의 수가 많을 테므로)
그런 걸 검출하기 위해 RED, BLACK으로
RED는 일종의 tmp 같은 개념이었던 게 아닐까?)
삽입 함수
로직은 이렇다.
노드 생성(malloc까지 해주고, 키값도 넣어주고.)
위치 찾기(적절한 리프노드 자식으로 들어가야하니까.)
(여기서 아예 빈 트리일 때는 안 들어가게 설정.)
그 위치의 자식으로 붙여주기.(이 때, 본인이 루트면 부모가 없으니 제외.)
마지막으로 삽입 속성 위반 함수 첨부.
// rb트리 삽입.
node_t *rbtree_insert(rbtree *t, const key_t key) {
node_t *y = t->nil;
node_t *x = t->root;
node_t *z = (node_t *)malloc(sizeof(node_t));
// 넣을 노드는 빨간색. 노드 형에 값을 넣어줘서 z노드를 만든다.
z->key = key;
z->color = RBTREE_RED;
z->left = t->nil;
z->right = t->nil;
z->parent = t->nil;
// 근데 루트가 안 비어있다면,
while (x != t->nil)
{
// y로 현재 지점은 저장하고, 맞는 위치까지, nil을 만날 때까지 트리 아래로 하강.
y = x;
if(z->key < x->key){
x = x->left;
}
else{
x = x->right;
}
}
// 찾았을테니, 현재 지점을 z의 부모로 설정하는데....
z->parent = y;
// 만약 그 자리가 최고 조상이면 z가 루트.
if (y == t->nil){
t->root = z;
}
//크기에 따라 z가 왼쪽 자식인지 오른쪽 자식인지 지정.
else if (z->key < y->key)
{
y->left = z;
}
else{
y->right = z;
}
// 잘 했으니 z에게 nil 들을 붙여주고, z 색도 다시 빨강!
z->left = t->nil;
z->right = t->nil;
z->color = RBTREE_RED;
rbtree_insert_fixup(t,z);
return t->root;
}삽입 속성 위반 함수
그래서,
부모가 RED라면.
1) 부모의 형제자매가 RED,
형제자매가 BLACK 인데
2)자신이 꺾인 상태
3)자신이 펴진 상태
에 따라 처리를 달리 한다.
1)은 삼촌이 RED라면
부모와 형제자매의 색을 검정,
조부모를 RED로 해준다.
그리고 조부모 기준으로 다시 fix up.
(왜 조부모인가 했는데,
당연히 삽입은 연속 red만 검출하니,
여기서 red가 된건 조부모라 거기를 fixup하겠지.)
(조건문에서는 x를 그래서 while문 조건이라서
x를 조부모로 갱신해준다.)
2)는
펴진 상태 처리를 해주기 위해
꺾인 상태를 펴주고,
3)은
엥?
~~ 검
~ 빨~ 검
빨
에서
~~ 빨
~검~ 검
빨
해서
~~ 검
~빨~ 빨
~~-ㅡ 검
을 한다는데
depth... 안 맞지않나?
하고 보니까
애초에 첫 케이스부터
depth가 안 맞는 트리였던거군............
............
그래서 당연히 옮겨도 안 맞지
미치겠다 열받네
아무튼
흠....
딱
사실 문제가 되는 상황이
할아버지
부모 / 삼촌
일때,
부모와 삼촌의 균형이 안 맞을 때가 문제라서.
실제 부모와 삼촌이 각각 가진 자식 트리의 상황에 따라
색깔이 레드와 블랙일테니까.
균형을 맞추는건
무거운쪽 -> 가벼운쪽으로 옮기는 거니까
그러기 적합한 조건, 상황을 파악해서 진행하는 것 같다.
구현 코드.
/삽입 시 속성 위반
void *rbtree_insert_fixup(rbtree *t, node_t *z) {
node_t *y;
// 현재 부모가 레드라면
while (z->parent->color == RBTREE_RED) {
// 부모가 할아버지의 왼쪽 자식일때
if (z->parent == z->parent->parent->left) {
// y는 삼촌이라고 할 때
y = z->parent->parent->right;
// 삼촌도 레드면
if (y->color == RBTREE_RED) {
// 부모 블랙! 삼촌 블랙! 할아버지 레드!
z->parent->color = RBTREE_BLACK;
y->color = RBTREE_BLACK;
z->parent->parent->color = RBTREE_RED;
// z를 할아버지로 설정!
z = z->parent->parent;
} else {
// 현재 애가 부모의 오른쪽 자식이면(꺾인 상태면)
if (z == z->parent->right) {
// 부모 기준으로 왼쪽 회전!
z = z->parent;
left_rotate(t, z);
}
// 현재 펴진 상태.
// 부모 색깔 블랙! 할아버지 색깔 레드! 할아버지 기준 오른쪽 회전!
z->parent->color = RBTREE_BLACK;
if (z->parent != t->nil && z->parent->parent != t->nil) {
z->parent->parent->color = RBTREE_RED;
right_rotate(t, z->parent->parent);
}
}
...
(반대쪽 함수)
t->root->color = RBTREE_BLACK;
return 0;
}
삭제
...
삭제는
리프 노드면 그 자리에서 삭제.
내부 노드면 오른쪽의 가장 작은 값이나
왼쪽의 가장 큰 값을 삭제한다.
(무엇으로 구현하든 상관없으나,
보통 오른쪽의 가장 작은 값을 삭제하는 듯.)
그리고 검은 색이 삭제 된다면,
임의의 경로의 검은색 갯수가 맞게 되지 않으므로,
그걸 맞추기 위해 속성 위반을 확인한다.
음, 사실
검은색 갯수를 맞추는 이유가
어쩌면 삭제할 때
총 트리에 달린 노드의 갯수를 확인하는 용도일지도.
(근데 사실,
갯수를 확인하는 건 그냥 세는건....
너무 비합리적이고.)
(검정색의 갯수도 실제로 세지는 않잖아?)
(하지만 삭제되는 색이 "검정색"이라는 건 확인하지.)
(오, 그러면 현재 트리에 달린 검정색의 갯수가 몇개이든.)
(일정 구역에 있는 검정색의 갯수를 "유지"한다면.)
(그리고, 그걸 직접 갯수를 세는 게 아니라.)
(할아버지, 부모, 형제 정도에서 확인한다면.)
(확실히, 균형을 유지할 수 있을 것 같다.)
(그렇지만 좀 특이하다.)
(어차피 색깔이 어떻든, 누구는 자식이 있고 누구는 없다.)
(실질적 노드 갯수는 그대로라는 것이다.)
(그런데 왜 색깔의 갯수를 유지하는게 유효하다는 것인가?)
(생각해보면, nil은 검은색 취급받지만.)
(다른 말로하면, red 노드는 자식이 있기 쉽단 말이지.)
(흠....)
.....
(아!)
(어차피 Red 노드의 자식은 절대로 black이다.)
(그야 red는 연속해서 올 수 없으니까.)
(그런데 black의 자식은 red일수도 있다.)
(그래서 red를 지워도,
즉 삭제색이 red라는건,
그 red의 자식 중 black 노드가 없었단 이야기가 된다.)
(꼭 직전 자식이 아니어도, 아무튼 최종적으로 삭제색이 red라면)
(그 노드는 black자식으로만 이루어졌을 수는 없다.)
(그러므로 리프노드니까, 그냥 지운다!)
(그렇지만, black이 지워진다는건
꼭 균형이 안 맞게 되어있다!)
(그때는 black이 실질적으로 리프노드여도,
항상 경로 수가 맞다는건, 다른쪽의 리프노드도 black이라는 뜻이라서!)
그러므로,
검은색의 균형을 맞춘다는 건,
갯수를 안 세고도 현재 현황을 색깔로 기록한 것...!
...
이라면,
단지 색깔이라는 속성만으로
이런 걸 만드는 걸 활용한다면....
트리 최적화식 알고리즘이긴 하지만 좀 더 제네럴하게 만들면
본래 현재 상황의 속성을 0, 1식으로 분류하긴 하는데
이건 0, 1의 각각의 정의를 디테일하게 만든 것에 가깝네.
반복적으로 발생하는 상황이 생겼을 때,
아예 속성처럼 만드는데, 그게 단순히 이분법적인 게 아니라,
디테일한 케이스를 속성으로 담을 수 있다는 건데.
0, 1, 2, 3, 4를 케이스마다 속성을 넣을 수는 있지만
이게 멋진 이유는 0, 1 두가지만으로 컴팩트하게 만들었다는 점이겠지...
조금 더 뽑자면,
특히 데이터를 삽입 삭제 시점 시
데이터 구조를 일관적으로 정렬해야할 때,
기존 데이터 / 새로운 데이터
의 순번을 정하는 규칙.....일까.
삭제 함수
int rbtree_erase(rbtree *t, node_t *z) {
node_t *y;
node_t *x;
color_t succesor;
y = z;
succesor = y->color;
// 오른쪽 자식이 있다면 걔와 대체.
if(z->left == t->nil){
x = z->right;
rb_transplant(t,z,z->right);
}
// 왼쪽 자식이 있다면 걔와 대체.
else if (z->right == t->nil)
{
x = z->left;
rb_transplant(t,z,z->left);
}
// 자식이 둘다 있다면 우측 최솟값과 대체.
else{
y = tree_minimum(t,z->right);
succesor = y->color;
x = y->right;
// 바로 자식이면 그대로 올림.
if(y->parent == z){
x->parent = y;
}
// 손자면 복잡하게 올림.(부모, 자식 재설정.)
else{
rb_transplant(t,y,y->right);
y->right = z->right;
y->right->parent = y;
}
rb_transplant(t,z,y);
y->left = z->left;
y->left->parent = y;
y->color = z->color;
}
// 삭제 색이 검정이면 fixup.
if(succesor == RBTREE_BLACK){
rbtree_delete_fixup(t,x);
}
// z를 없애기 위해 호적에서 팜.
if(z == z->parent->left){
z->parent->left = t->nil;
}
else if(z == z->parent->right){
z->parent->right = t->nil;
}
free(z);
z = t->nil;
return 0;
}삭제 속성 위반 함수
// 삭제시 위반 속성을 검사하는 함수.
void rbtree_delete_fixup(rbtree *t, node_t *x){
node_t *w;
// x가 루트가 아니고 삭제색깔이 검정이라면.
while (x != t->root && x->color== RBTREE_BLACK){
// x가 부모의 왼쪽 자식 일 경우.
if(x == x->parent->left){
w = x->parent->right;
// 형제가 RED
if(w->color == RBTREE_RED){
w->color =RBTREE_BLACK;
x->parent->color = RBTREE_RED;
left_rotate(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;
}
// 형제의 꺾인 자식이 RED
else {
if (w->right->color == RBTREE_BLACK){
w->left->color = RBTREE_BLACK;
w->color = RBTREE_RED;
right_rotate(t, w);
w = x->parent->right;
}
// 형제의 펴진 자식이 RED
else{
w->color = x->parent->color;
x->parent->color = RBTREE_BLACK;
w->right->color = RBTREE_BLACK;
left_rotate(t,x->parent);
x = t->root;
}
}
}
