728x90
레드-블랙 트리란?
각각의 노드가 레드나 블랙인 색상 속성을 가지고 있는 이진 탐색 트리
이진 탐색 트리가 가지는 일반적인 조건에 다음과 같은 추가적인 조건을 만족해야 유효한 레드-블랙 트리이다.
- 노드는 레드 또는 블랙
- 루트 노드는 블랙
- 모든 리프 노드는 블랙
- 레드 노드의 자식은 모두 블랙 → 루트부터 리프 노드까지의 경로에 레드가 연이어 올 수 없다
- 어떤 노드에서 리프 노드까지의 모든 경로에는 같은 수의 블랙 노드가 존재
위 조건으로부터, 루트로부터 가장 긴 경로가 가장 짧은 경로의 길이의 두 배를 넘지 않는다. 이를 개략적으로 균형이 잡혀 있다(roughly balanced)고 한다.
→ 최악의 시간복잡도가 트리의 높이(깊이)에 따라 결정되므로 보통의 이진트리보다 효율적
💡 4와 5번째 규칙에 의해 최단거리의 경우 모두 블랙노드가, 최장의 경우 레드와 블랙노드가 교차하는 식으로 구성된다. 따라서 최장 거리가 최단거리의 두배를 넘을 수 없다.
시간복잡도
| 레드-블랙 트리 | 최악 |
| 삽입 | O(logN) |
| 탐색 | O(logN) |
| 삭제 | O(logN) |
회전
레드-블랙 트리에 새로운 값이 삽입되거나 삭제가 되었을 때
→ 레드-블랙 트리의 특징이 깨지게 되는 경우가 존재
→ 회전연산을 통해 조건을 충족
우회전
- 루트노드가 13에서 10으로 변경 → 13이 10의 자식노드로 변경
- 12가 13의 왼쪽 자식 노드로 옮겨짐
좌회전
- 루트노드가 10에서 13으로 변경 → 10이 13의 자식노드로 변경
- 12가 10의 오른쪽 자식 노드로 옮겨짐
삽입연산
기본적으로 레드-블랙트리의 삽입은 이진탐색트리와 동일하지만 삽입 이후에 규칙에 맞춰 트리를 복구하는 과정을 거친다.
- 모든 노드는 빨간색 아니면 검은색 → 문제없음
- 루트노드는 검은색 → 루트노드가 빨간색인 경우 다시 검은색으로 수정
- 리프노드는 검은색 → 문제없음
- 빨간 노드의 자식들은 모두 검은색
- 하지만 검은색 노드의 자식은 빨간색일 필요 없음 → 문제 발생
- 루트노드에서 리프노드까지 사이에 있는 검은색 노드의 수는 모두 동일 → 문제없음
💡 4번 문제의 경우 새로 삽입된 노드의 부모 역시 빨간색이므로 3가지의 방법으로 나누어 처리한다. 부모노드가 조부 노드의 왼쪽 자식일 경우를 기준이며, 오른쪽 자식일 경우 반대로 진행한다.
- 삼촌노드가 RED 인 경우
- 삼촌은 BLACK이며 새로 삽입한 노드가 부모노드의 오른쪽 자식인 경우
- 삼촌은 BLACK이며 새로 삽입한 노드가 부모노드의 왼쪽 자식인 경우
- 삼촌노드가 RED 인 경우
- 새로 삽입된 노드는 12이며, 삼촌(75)이 RED
- 부모노드와 삼촌노드를 검은색으로 칠한다
- 조부노드를 빨간색으로 칠한다
💡 조부 노드를 RED로 만들었기 때문에 그 위로 규칙 위반이 없는지 루트노드까지 재귀적으로 살펴야 한다
2. 삼촌은 BLACK이며 새로 삽입한 노드가 부모노드의 오른쪽 자식인 경우
- 새로 삽입된 노드는 75이며, 삼촌(NULL LEAF)이 BLACK
- 부모노드(50)를 왼쪽으로 회전시켜서 3번 문제와 같게 만든다
3. 삼촌은 BLACK이며 새로 삽입한 노드가 부모노드의 왼쪽 자식인 경우
- 새로 삽입된 노드는 25이며, 삼촌(NULL LEAF)이 BLACK
- 부모노드를 검은색, 조부노드를 빨간색으로 칠한다
- 조부노드를 오른쪽으로 회전시킨다
삭제연산
레드-블랙트리에서의 삭제는 기본적으로 이진탐색트리의 방법을 따른 뒤, 색상을 맞춘다
1. 형제 노드가 RED일 경우
- 회전 -> 부모와 형제 모두 색 변경
2. 부모, 형제, 모든 조카가 BLACK일 경우
- 형제 노드만 RED로 변경
3. 부모가 RED고, 형제와 모든 조카가 BLACK일 경우
- 부모와 형제 색 변경
4. 본인이 왼쪽에 있고, 가까운 위치의 조카가 RED일 경우
- 조카가 빨강 → 형제는 검정
- 가까운 조카 BLACK, 형제 RED로 색 변경 후 회전
5. 본인 위치 기준으로 먼 조카가 RED일 경우
- 흰색은 검정 또는 빨강이 모두 될 수 있다
- 부모를 BLACK, 형제의 색을 부모의 색으로, 먼 조카의 색을 BLACK으로 순차 변경
- 형제 기준으로 부모를 회전
6. 만약 끝 노드가 아니라 중간 노드가 삭제될 경우
- 삭제하고자 하는 노드를 기준으로 오른쪽에 있는 값 중에 가장 작은 값을 후보로 올린다. 여기서 값만 옮기고, 색은 옮기지 않고 그대로 사용
- 규칙 5번에 의해 부모를 BLACK, 형제를 부모의 색으로, 먼 조카를 BLACK으로 변경 후 회전을 진행한다
레드-블랙 트리 코드
- 삽입
#include <stdio.h>
#include <stdlib.h>
#include "rbtree.h"
#define INFO_NUM 8
typedef struct {
int data;
struct rb_node node;
} INFO;
typedef struct {
int data;
int color;
} NODE_INFO;
int rb_insert(struct rb_root *root, INFO *info) {
struct rb_node **p = &root->rb_node;
struct rb_node *parent = 0;
INFO *temp;
while(*p) {
// Container_of
parent = *p;
temp = rb_entry( parent, INFO, node);
if(info->data < temp->data)
p = &(*p)->rb_left;
else if(info->data > temp->data)
p = &(*p)->rb_right;
else
return 0;
}
// Insert node
rb_link_node(&info->node, parent, p);
// Balance tree
// rb_insert_color(&info->node, root);
return 1;
}
int __display(struct rb_node *temp, NODE_INFO (*array)[10], int *row, int *col) {
INFO *info;
if(temp == 0)
return 0;
++*row;
__display(temp->rb_left, array, row, col);
info = rb_entry(temp, INFO, node);
array[*row][(*col)].color = temp->rb_color;
array[*row][(*col)++].data = info->data;
__display(temp->rb_right, array, row, col);
--*row;
}
void display(struct rb_root *root) {
int row = -1;
int col = 0;
NODE_INFO a[10][10] = {0,};
__display(root->rb_node, a, &row, &col);
system("clear");
for(int i=0; i<10; i++) {
for(int j=0; j<10; j++) {
if(a[i][j].data) {
if(a[i][j].color == RB_RED)
printf("<%2d>", a[i][j].data);
else
printf("[%2d]", a[i][j].data);
}
else
printf("%4c", ' ');
}
printf("\\n");
}
getchar();
}
int main() {
struct rb_root root = {0};
int a[] = {1, 2, 3, 4, 5, 6, 7, 8};
int i;
INFO info[INFO_NUM];
display(&root);
for(i=0; i<INFO_NUM; i++) {
info[i].data = a[i];
rb_insert(&root, info+i);
display(&root);
}
return 0;
}
- 삭제
#include <stdio.h>
#include <stdlib.h>
#include "rbtree.h"
#define INFO_NUM 8
typedef struct {
int data;
struct rb_node node;
} INFO;
typedef struct {
int data;
int color;
} NODE_INFO;
int rb_insert(struct rb_root *root, INFO *info) {
struct rb_node **p = &root->rb_node;
struct rb_node *parent = 0;
INFO *temp;
while(*p) {
// Container_of
parent = *p;
temp = rb_entry( parent, INFO, node);
if(info->data < temp->data)
p = &(*p)->rb_left;
else if(info->data > temp->data)
p = &(*p)->rb_right;
else
return 0;
}
// Insert node
rb_link_node(&info->node, parent, p);
// Balance tree
// rb_insert_color(&info->node, root);
return 1;
}
int __display(struct rb_node *temp, NODE_INFO (*array)[10], int *row, int *col) {
INFO *info;
if(temp == 0)
return 0;
++*row;
__display(temp->rb_left, array, row, col);
info = rb_entry(temp, INFO, node);
array[*row][(*col)].color = temp->rb_color;
array[*row][(*col)++].data = info->data;
__display(temp->rb_right, array, row, col);
--*row;
}
void display(struct rb_root *root) {
int row = -1;
int col = 0;
NODE_INFO a[10][10] = {0,};
__display(root->rb_node, a, &row, &col);
system("clear");
for(int i=0; i<10; i++) {
for(int j=0; j<10; j++) {
if(a[i][j].data) {
if(a[i][j].color == RB_RED)
printf("<%2d>", a[i][j].data);
else
printf("[%2d]", a[i][j].data);
}
else
printf("%4c", ' ');
}
printf("\\n");
}
getchar();
}
int main() {
struct rb_root root = {0};
int a[] = {1, 2, 3, 4, 5, 6, 7, 8};
int i, index;
INFO info[INFO_NUM];
for(i=0; i<INFO_NUM; i++) {
info[i].data = a[i];
rb_insert(&root, info+i);
}
display(&root);
while(1) {
printf("Delete node: ");
scanf("%d", &index);
rb_erase(&info[index-1].node, &root);
display(&root);
}
return 0;
}