개념
- 들어가기 앞서, 이 정리에선 RBTREE의 개념은 가볍게 다룰 예정이다. 이 정리글은 C 활용 능력 향상에 포커스를 맞추고 있기에, RBTREE보단 포인터, 구조체, 함수구조와 같은 부분에 집중해 코드리뷰 할 예정이다.
- 코드 리뷰 이기에, 크게 초기화, 회전, 삽입, 삭제와 같이 기능으로 나눠 설명할 예정이다.
특성
- 레드-블랙 트리(red-black tree)는 자가 균형 이진 탐색 트리(self-balancing binary search tree)로서, 대표적으로는 연관 배열 등을 구현하는 데 쓰이는 자료구조다.
- 1978년 레오 귀바스(Leo J. Guibas)와 로버트 세지윅이 1972년 루돌프 바이어가 창안한 "대칭형 이진 B-트리"를 발전시켜 만들었다.
- 레드-블랙 트리는 복잡한 자료구조지만, 실 사용에서 효율적이고, 최악의 경우에도 상당히 우수한 실행 시간을 보인다: 트리에 n개의 원소가 있을 때 O(log n)의 시간복잡도로 삽입, 삭제, 검색을 할 수 있다.
- RBTREE 의 5가지 속성
- 모든노드는 RED 또는 BLACK 이다.
- 루트노드는 BLACK 이다.
- 모든 리프(nil)은 흑색이다.
- 노드가 RED 라면, 그 노드의 자식들은 모두 BLACK 이다. (RED 는 연속될 수없다.)
- 각 노드로 부터 그 노듸의 자손인 리프로 가는 경로들은 모드 같은 수의 BLACK 노드를 포함한다.
- 삽입, 삭제를 할 경우 2, 4, 5 속성을 위반하게 되는데, 이들을 해결하기 위해서 구조를 바꾸게 되면, 자연스럽게 균형이 잡히게 된다.
SENTINEL
- 레드블랙 트리의 코드에서, 한계 조건을 다루기 편리하도록 nil을 표현하기 위해, 하나의 경계 노드를 사용하는데, 그걸 sentinel 이라고 부른다. 레드블랙 트리 T 에서의 경계노드 T.nil 은 다른 보통의 노드와 마찬가지로 동일한 필드를 가진다.
- 이 노드의 다른 p, left, right, key 등은 의미를 가지지 않지만, color 필드는 BLACK 을 가진다.
높이, 시간복잡도
- 높이 : n 개의 내부 노드를 가지는 RBTREE 는 최대 2log(n+1) 의 높이를 가진다.
- 시간복잡도 : 모든 연산에 대해서 O(logn)
구조체
- 문제에서 주어진 구조체
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;
node_t *nil; // for sentinel
} rbtree;
- Q & A
- enum, struct 차이점
struct는 구조체를 의미하며, 서로 다른 타입의 변수들을 하나의 타입으로 묶어 관리하는 것이다. 예를 들어, node_t 구조체는 color_t 타입의 color, key_t 타입의 key, 그리고 node_t 타입의 포인터 parent, left, right를 멤버로 가지고 있다.
enum은 열거형 이라는 뜻으로, 서로 관련된 여러 개의 상수를 하나의 타입으로 묶어 관리하는 것이다. 예를 들어, 위의 color_t는 RBTREE_RED와 RBTREE_BLACK 두 개의 상수를 가지는 열거형이다. 각 상수는 컴파일러에 의해 자동으로 0부터 시작하는 정수로 변환된다. - typedef 쓰는이유?
typedef는 타입 정의를 위한 키워드로, 기존의 타입에 새로운 이름을 부여하거나 복잡한 타입을 간결하게 표현할 수 있게 돕는다. 예를 들어, typedef int key_t;는 int 타입에 key_t라는 새로운 이름을 부여하는 것! 이를 통해 코드의 가독성을 높이고, 나중에 타입을 변경할 때 유연성을 높일 수 있다. - struct node_t 안에 struct node_t 가 있는 이유?
주의할 점은, 이 부분에서 선언되는 것은 struct node_t 자체가 아니라 struct node_t 타입의 포인터. 이는 각 노드가 다른 노드를 '가리키는' 포인터를 가지고 있음을 의미하며, 이를 통해 트리 구조가 형성된다.
struct node_t 안의 struct node_t *parent, *left, *right;는 node_t 타입의 포인터를 선언하는 부분이다. 이는 트리 구조를 구현하는 데 필수적인 부분으로, 각 노드가 부모 노드와 자식 노드를 가리킬 수 있게 한다. 이렇게 자기 자신을 가리키는 구조를 재귀적 자료구조라고 한다.
- enum, struct 차이점
회전
- 포인터를 변경하기 위해 회전을 사용하는데, 이는 이진 검색 트리 특성을 보전해주는 국소적인 연산이다.
- 기초적인 트리의 연산 함수이기 때문에 자세한 설명은 스킵!
LEFT-ROTATE(t, x)
- 의사 코드
LEFT-ROTATE(t, x)
y = x.right // x의 오른쪽 자식을 y로 설정
x.right = y.left // y의 왼쪽 서브트리를 x의 오른쪽 서브트리로 설정
if y.left != t.nil
y.left.p = x // y의 왼쪽 자식의 부모를 x로 설정
y.p = x.p // y의 부모를 x의 부모로 설정
if x.p == t.nil
t.root = y // x의 부모가 없는 경우 (즉, x가 root인 경우), y를 새로운 root로 설정
elseif x == x.p.left
x.p.left = y // x가 왼쪽 자식인 경우, x의 부모의 왼쪽 자식을 y로 설정
else
x.p.right = y // x가 오른쪽 자식인 경우, x의 부모의 오른쪽 자식을 y로 설정
y.left = x // y의 왼쪽 자식을 x로 설정
x.p = y // x의 부모를 y로 설정
- C구현 코드
void left_rotate(rbtree *t, node_t *x)
{
node_t *y = x->right;
x->right = y->left;
// y의 왼쪽 자식 노드가 nil이 아니라면, 그 노드의 부모를 x로 설정
if (y->left != t->nil) {
y->left->parent = x;
}
y->parent = x->parent;
// x의 부모가 nil이라면, x는 root였으므로, y를 새로운 root로 설정
if (x->parent == t->nil) {
t->root = y;
}
// x가 왼쪽 자식이었다면, x의 부모의 왼쪽 자식을 y로 설정
else if (x == x->parent->left) {
x->parent->left = y;
}
// x가 오른쪽 자식이었다면, x의 부모의 오른쪽 자식을 y로 설정
else {
x->parent->right = y;
}
y->left = x;
x->parent = y;
}
- Q & A
- node_t *y = x->right; 와 같이, y를 포인터로 지정해 주는 이유?
- 메모리 효율성: 포인터를 사용하면 노드의 데이터를 복사하거나 이동시키는 대신에, 그 데이터의 메모리 주소만 참조할 수 있다. 이는 메모리 사용을 효율적으로 만들며, 특히 큰 데이터 구조를 다룰 때 중요하다.
- 데이터 구조의 유동성: 트리와 같은 복잡한 데이터 구조에서, 노드 간의 관계를 쉽게 변경할 수 있도록 한다. 예를 들어, 노드의 자식 노드를 변경하거나, 노드를 다른 위치로 이동시키는 등의 연산을, 데이터를 복사하거나 이동시키지 않고도 수행할 수 있다.
- (연결 질문) y = x->right; 이렇게 해주면안 되는거야?
아래 답변은 참고만 하면 좋을것 같다. 실제로 이 코드에서 y를 포인터로 선언해 주지 않으면 구현이 불가능 하다.
- node_t *y = x->right; 와 같이, y를 포인터로 지정해 주는 이유?
y = x->right;는 코드가 작동합니다만, y의 데이터 타입이 무엇인지에 따라 다릅니다.하지만 y가 node_t (즉, 노드 자체) 타입으로 선언되었다면, y = x->right;는 오류를 발생시킵니다. 왜냐하면 x->right는 node_t* 타입이며, 이는 node_t 타입의 y에 직접 할당할 수 없기 때문입니다.
따라서 y = x->right; 문장은 y의 타입에 따라 다르게 작동합니다. 보통, 트리와 같은 복잡한 데이터 구조에서는 노드 간의 관계를 표현하기 위해 노드에 대한 포인터(node_t*)를 사용합니다.
y가 node_t* (즉, 노드에 대한 포인터) 타입으로 선언되었다면, y = x->right;는 y가 x의 오른쪽 자식 노드를 가리키도록 합니다.
RIGHT-ROTATE(t, x)
- 의사 코드
RIGHT-ROTATE(t, x)
y = x.left // y를 설정
x.left = y.right // y의 오른쪽 서브트리를 x의 왼쪽 서브트리로 옮기는 과정
if y.right != t.nil
y.right.p = x
y.p = x.p // x의 부모를 y로 연결
if x.p == t.nil
t.root = y
elseif x == x.p.right
x.p.right = y
else
x.p.left = y
y.right = x // x를 y의 오른쪽으로 놓는 과정
x.p = y
- C구현 코드
void right_rotate(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;
}
삽입
- 삽입과정
- 삽입전 RBTREE는 5가지 속성을 만족한다.
- 삽입 방식은 일반적인 BST(이진탐색트리)와 동일하다. (삽입노드의 색깔은 항상 RED)
- 삽입후 RB트리 속성 위반 여부 확인하고, 위반했다면 재조정 (insert-fixup) 한다.
- 레드-블랙 트리의 삽입은 단순 이진 탐색 트리에서 하는것과 같이, 노드를 삽입하고, 색을 붉은색으로 정하는 것으로 시작한다. 그 다음 단계는, 그 주위 노드의 색에 따라 달라진다. 여기서 '삼촌 노드(uncle node)'를 도입할텐데, 이는 같은 높이에 있는 옆 노드(다시 말해, 사촌)의 부모 노드(삼촌)를 뜻한다. 여기서 레드-블랙 트리의 특성이 추가된다.
- 특성 3(모든 리프 노드들은 검은색이다)은 언제나 변하지 않는다.
- 특성 4(적색 노드의 모든(두) 자식은 검은색이다)는 적색 노드의 추가, 검은색 노드의 적색 노드로의 전환, 회전(rotation)에 의해서 제대로 지켜지지 않는 상황이 된다.
- 특성 5(어떤 노드로부터 시작되어 리프 노드에 도달하는 모든 경로에는 모두 같은 개수의 블랙 노드가 있다)는 검은색 노드의 추가, 적색 노드의 검은색 노드로의 전환, 회전(rotation)에 의해서 제대로 지켜지지 않는 상황이 된다.
- 삽입 케이스
1 속성 : 트리의 시작은 검은색이다.
2 속성 : root node는 검은색이다.
4 속성 : 붉은색 노드의 모든 자식 노드는 검은색이다.
5 속성 : 한 노드에서 부터 뻗어나가는 모든 경로에 대해 검은색 노드의 수는 같다.
-
- CASE 1 :
새로운 노드가 트리의 시작(root)에 위치한다.
이 경우, 레드-블랙 트리의 1 속성을 만족하기 위해서, N을 검은색으로 표시한다. 시작점으로 부터 뻗어나가는 모든 경로에 검은색 노드를 하나 추가한 셈이 되기 때문에 레드-블랙 트리의 5 속성은 여전히 유효하다. - CASE 2 :
새로운 노드의 부모 노드 P가 검은색이라면, 레드-블랙 트리의 4 속성은 유효하다.
그러므로 두 번째 경우에도 이 트리는 적절한 레드-블랙 트리이다. 레드-블랙 트리의 5 속성도 별 문제가 없는데, 이는 새로운 노드 N은 두개의 검은색 노드를 leaf node로 가지고 있기 때문이다. 비록 N이 붉은색 노드라고 해도 N이 들어간 자리에 원래 위치했던 노드의 색이 검은색이었으므로, N의 자식 노드에게서 시작되는 경로들은 모두 같은 수의 검은색 노드를 가지게 되고, 결과적으로 다섯 번째 속성은 유지되게 된다. - CASE 3 :
만약 부모 노드 P 와 삼촌 노드 U 가 모두 붉은색 노드라면, RBT 의 5 속성을 유지하기 위해서, P와 U를 모두 검은색으로 바꾸고 할아버지 노드 G를 붉은색으로 바꾼다. 이렇게 함으로써 붉은색 노드인 N은 검은색 부모 노드를 가지게 된다.
이를 해결하기 위해서 G에 대해 지금까지 설명한 첫 번째 경우부터 세 번째 경우까지를 재귀적으로적용한다. 이 작업은 삽입 과정 중에 발생하는 유일한 재귀 호출이며, 회전 작업을 하기 전에 적용해야 한다는 것에 주의한다. 이는 일정한 횟수의 회전 작업만이 필요하다는 것을 증명한다.
그런데 이번에는 할아버지 노드 G가 레드 블랙 트리의 2 속성이나 4 속성을 만족하지 않을 수 있다(네 번째 속성은 G의 부모 노드가 붉은색일 경우 만족하지 않는다). - CASE 4 :
부모 노드 P가 붉은색인데, 삼촌 노드 U는 검은색이고, 새로운 노드 N은 P의 오른쪽 자식 노드이며, P는 할아버지 노드 G의 왼쪽 자식 노드일 경우, N과 P의 역할을 변경하기 위해서 왼쪽 회전을 한다. 그 후, 부모 노드였던 P를 다섯 번째 경우에서 처리하게 된다. 이는 레드-블랙 트리의 4 속성을 아직 만족하지 않기 때문이다.
회전 작업은 몇몇 경로들이 이전에는 지나지 않았던 노드를 지나게 하는데, 그럼에도 양쪽 노드가 모두 붉은색이므로, 레드-블랙 트리의 5 속성을 위반하지 않는다. - CASE 5 :
부모 노드 P는 붉은색이지만 삼촌 노드 U는 검은색이고, 새로운 노드 N이 P의 왼쪽 자식 노드이고, P가 할아버지 노드 G의 왼쪽 자식 노드인 상황에서는 G에 대해 오른쪽 회전을 한다. 회전의 결과 이전의 부모 노드였던 P는 새로운 노드 N과 할아버지 노드 G를 자식 노드로 갖는다.
G가 이전에 검은색이었고, P는 붉은색일 수밖에 없기 때문에, P와 G의 색을 반대로 바꾸면 레드-블랙 트리의 4 속성을 만족한다. 레드-블랙 트리의 5 속성(은 계속 유지되는데, 이는 이전에 P를 포함하는 경로는 모두 G를 지나게 되고, 바뀐 후 G를 포함하는 경로는 모두 P를 지나기 때문이다. 바뀌기 전에는 G가, 바뀐 후에는 P가 P, G, N중 유일한 검은색 노드이다.
- CASE 1 :
RB-INSERT(t, z)
- 의사 코드
RB-INSERT(t, z)
y = t.nil // y를 NIL로 초기화
x = t.root // x를 루트로 설정
// Case 1: 트리가 비어있는 경우 또는 적절한 위치를 찾을 때까지
while x != t.nil // x가 NIL이 아닐 때까지
y = x // y를 x로 업데이트
if z.key < x.key // 삽입할 값이 현재 노드의 키보다 작으면
x = x.left // 왼쪽으로 이동
else // 삽입할 값이 현재 노드의 키보다 크거나 같으면
x = x.right // 오른쪽으로 이동
z.p = y // z의 부모를 y로 설정
// Case 2: 새 노드가 루트 노드가 될 경우
if y == t.nil // 트리가 비어 있으면
t.root = z // z를 루트로 설정
// Case 3: 새 노드가 부모 노드의 왼쪽 자식이 될 경우
elseif z.key < y.key // z의 키가 y의 키보다 작으면
y.left = z // z를 y의 왼쪽 자식으로 설정
// Case 4: 새 노드가 부모 노드의 오른쪽 자식이 될 경우
else // z의 키가 y의 키보다 크거나 같으면
y.right = z // z를 y의 오른쪽 자식으로 설정
z.left = t.nil // z의 왼쪽 자식을 NIL로 설정
z.right = t.nil // z의 오른쪽 자식을 NIL로 설정
z.color = RED // z의 색을 레드로 설정
RB-INSERT-FIXUP(t, z) // 레드-블랙 트리 속성을 유지하도록 수정
- C구현 코드
// TODO: implement insert
node_t *rbtree_insert(rbtree *t, const key_t key){
// 새로운 노드를 만들어 준다. insert fixup에 활용하기 위해서!
node_t *new = (node_t *)calloc(1, sizeof(node_t));
new->key = key; // 매개변수의 key값을 new에 저장
new->left = t->nil;
new->right = t->nil;
new->color = RBTREE_RED; // 삽입 색은 무조건 레드!
node_t *y = t->nil;
node_t *x = t->root;
// 트리가 비어있는 경우 또는 적절한 위치를 찾을 때까지 반복
while(x != t->nil){
y = x;
if(new->key < x->key){
x = x->left;
}
else{
x = x->right;
}
}
new->parent = y;
// Case 1: 새 노드가 루트 노드가 될 경우
if(y == t->nil){
t->root = new;
}
// Case 2: 새 노드가 부모 노드의 왼쪽 자식이 될 경우
else if(new->key < y->key){
y->left = new;
}
// Case 3: 새 노드가 부모 노드의 오른쪽 자식이 될 경우
else{
y->right = new;
}
rbtree_insert_fixup(t, new);
return new;
//return t->root;
}
RB-INSERT-FIXUP(t, z)
- 삽입 후 2, 4 속성을 위반할 경우가 발생 하므로, 다음의 알고리즘을 수행해서 속성 위반을 해결 가능하다.
while (부모가 RED) {
// CASE 1.
if 부모/삼촌 == RED이면,
부모/삼촌 모두 BLACK으로 바꾸고, 할아버지를 RED로 변경
할아버지에서 다시 시작
// CASE 2/3. 삼촌 == BLACK
else {
// CASE 2.
if 할아버지/부모/자신 꺾인상테
회전해서 부모/자신을 펴준다. CASE 3 상태가 됨
// CASE 3. 할아버지/부모/자신 펴진상테
부모/할아버지 서로 색바꾸기
할아버지 기준 회전
}
}
// 종료전
루트를 BLACK으로 변경
- 의사 코드
RB-INSERT-FIXUP(t, z)
// Case 1: z의 부모 노드가 RED일 때까지 반복
while z.p.color == RED // z의 부모의 색이 레드일 때까지
// Case 2: z의 부모가 z의 할아버지의 왼쪽 자식일 경우
if z.p == z.p.p.left // z의 부모가 왼쪽 자식이면
y = z.p.p.right // y를 z의 삼촌으로 설정
// Case 2.1: z의 삼촌이 RED일 경우
if y.color == RED // y의 색이 레드면
z.p.color = BLACK // z의 부모의 색을 블랙으로 변경
y.color = BLACK // y의 색을 블랙으로 변경
z.p.p.color = RED // z의 할아버지의 색을 레드로 변경
z = z.p.p // z를 z의 할아버지로 업데이트
else
// Case 2.2: z가 부모의 오른쪽 자식이고, 삼촌이 BLACK인 경우
if z == z.p.right // z가 부모의 오른쪽 자식이면
z = z.p // z를 z의 부모로 업데이트
LEFT-ROTATE(t, z) // z를 중심으로 왼쪽 회전
z.p.color = BLACK // z의 부모의 색을 블랙으로 변경
z.p.p.color = RED // z의 할아버지의 색을 레드로 변경
RIGHT-ROTATE(t, z.p.p) // z의 할아버지를 중심으로 오른쪽 회전
else // Case 3: z의 부모가 z의 할아버지의 오른쪽 자식일 경우
y = z.p.p.left // y를 z의 삼촌으로 설정
// Case 3.1: z의 삼촌이 RED인 경우
if y.color == RED:
z.p.color = BLACK // z의 부모의 색을 블랙으로 변경
y.color = BLACK // y의 색을 블랙으로 변경
z.p.p.color = RED // z의 할아버지의 색을 레드로 변경
z = z.p.p // z를 z의 할아버지로 업데이트
else:
// Case 3.2: z가 부모의 왼쪽 자식이고, 삼촌이 BLACK인 경우
if z == z.p.left: // z가 부모의 왼쪽 자식이면
z = z.p // z를 z의 부모로 업데이트
RIGHT-ROTATE(t, z) // z를 중심으로 오른쪽 회전
z.p.color = BLACK // z의 부모의 색을 블랙으로 변경
z.p.p.color = RED // z의 할아버지의 색을 레드로 변경
LEFT-ROTATE(t, z.p.p) // z의 할아버지를 중심으로 왼쪽 회전
t.root.color = BLACK // 트리의 루트를 블랙으로 변경
- C구현 코드
void rbtree_insert_fixup(rbtree *t, node_t *z){
node_t *y;
// Case 1: z의 부모 노드가 RED일 때까지 반복
while (z->parent->color == RBTREE_RED) {
// Case 2: z의 부모가 z의 할아버지의 왼쪽 자식일 경우
if (z->parent == z->parent->parent->left) {
y = z->parent->parent->right;
// Case 2.1: z의 삼촌이 RED일 경우
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 {
// Case 2.2: z가 부모의 오른쪽 자식이고, 삼촌이 BLACK인 경우
if (z == z->parent->right) {
z = z->parent;
left_rotate(t, z);
}
z->parent->color = RBTREE_BLACK;
z->parent->parent->color = RBTREE_RED;
right_rotate(t, z->parent->parent);
}
}
// Case 3: z의 부모가 z의 할아버지의 오른쪽 자식일 경우
else {
y = z->parent->parent->left;
// Case 3.1: z의 삼촌이 RED인 경우
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 {
// Case 3.2: z가 부모의 왼쪽 자식이고, 삼촌이 BLACK인 경우
if (z == z->parent->left) {
z = z->parent;
right_rotate(t, z);
}
z->parent->color = RBTREE_BLACK;
z->parent->parent->color = RBTREE_RED;
left_rotate(t, z->parent->parent);
}
}
}
t->root->color = RBTREE_BLACK;
}
삭제
- 아직 확신하진 못하지만, 삭제는 여러가지 알고리즘으로 구현이 가능한것 같다. 내가 구현한 방식은 INTRODUCTION TO ALGORITHMS 책에 나와있는 수도코드를 통해 구현 했기에, 총 4가지 케이스를 간략하게 설명하고, 관련 사진을 첨부할 예정이다.
- extra black 설명영상 - https://www.youtube.com/watch?v=6drLl777k-E
- RBT 위키백과 설명 https://ko.wikipedia.org/wiki/레드-블랙_트리
- 다른 방법들에 대해서도 다루고 싶은데, 여러 자료들을 돌아다녀본 결과, 본인이 이해한 방법대로 구현하는게 가장 깔끔한것 같다는 생각이 들었다. 나는 nil노드를 활용한 코드 구현이 가장 쉬웠고, extra black을 통한 설명이 제일 이해하기 쉬웠던것 같다. 공부에 참고한 자료들을 공유하는걸로 대신 하겠다!
- 삭제를 본격적으로 다루기전 알아야하는 두가지가 있다.
- 삭제되는 노드가 RED면, 삭제되거나 이동해도 레드 블랙 특성이 유지된다. 이유는 아래와 같다.
- 흑색 높이는 모두 그대로 유지된다.
- 적색노드가 인접하지 않는다.
- RED가 삭제된다면 루트가 삭제되는게 아니기에, 루트는 흑색으로 유지된다. (루트는 항상 BLACK
- extra black 은 개념을 이해하기 위해 등장한 명칭이며, 코드 구현에는 관련이 없다.
- 삭제되는 노드가 RED면, 삭제되거나 이동해도 레드 블랙 특성이 유지된다. 이유는 아래와 같다.
- 삭제 케이스
- CASE 1 :
x 의 형제 w 가 RED 인 경우
유일하게 형제 노드가 RED인 경우이다. 간단한 회전과 색변환을 통해서 구현 가능하다. 이 과정속에 있는 회전과 색변환이 아래의 모든 개념에서도 사용된다. - CASE 2 :
x 의 형제 w 는 BLACK 이고, w 의 두 자식이 모두 BLACK 인 경우
extra black의 개념이 알차게 적용된 케이스. 자식노드들의 색이 같고, 부모노드와 다른색이라면, 서로의 색을 바꿔줘도 RBT를 만족하는데, 이 개념을 활용해서 extra black을 제거해준다. 이 케이스의 경우 루트에 닿을때 까지 while문을 통해 정상적인 RBT가 완성될때까지 반복한다. - CASE 3 :
x 의 형제 w 는 BLACK, w 의 왼쪽 자식은 RED, w 의 오른쪽 자식은 BLACK 인 경우
CASE 3 의경우는, 노드들의 모습을 CASE 4 로 만들기 위한 과정이다. 쉽게 말해서, 4번으로 해결하기 위해 바꿔주는 과정이다. - CASE 4 :
x 의 형제 w 는 BLACK 이고, w 의 오른쪽 자식은 RED 인 경우
회전과 색변환을 통해 정상적인 RBT를 만들수 있다.
특징이 되는 부분들만 언급하고 나머지는 그대로 두었는데, 책과 문서들을 보며 직접 그려보는걸 추천한다. 시간이 많았다면 전부 다 그려서 설명하고 싶지만… 불가능하기에… 나중에 혹시나 이 글을 다시 수정할 일이 생긴다면 그때 와서 내용을 추가해 보겠다.
RB-TRANSPLANT(t, u, v)
- 의사 코드
RB-TRANSPLANT(t, u, v)
if u.p == t.nil // u가 root 노드인 경우
t.root = v // v를 새로운 root로 설정
else if u == u.p.left // u가 부모의 왼쪽 자식인 경우
u.p.left = v // u의 부모의 왼쪽 자식을 v로 설정
else // u가 부모의 오른쪽 자식인 경우
u.p.right = v // u의 부모의 오른쪽 자식을 v로 설정
v.p = u.p // v의 부모를 u의 부모로 설정
- C구현 코드
void transplant(rbtree *t, node_t *x, node_t *y){
if(x->parent == t->nil){
t->root = y;
}else if(x == x->parent->left){
x->parent->left = y;
}else{
x->parent->right = y;
}
y->parent = x->parent;
}
RB-ERASE-MIN(t, p)
- 이 코드는 책의 코드를 완벽하게 구현하기 위해서 만들어낸 함수다. test.c에서 활용하는 min, max 함수는 전체 트리에서의 min, max를 확인하고 있기에, ERASE 함수에 필요한 일부 부분트리의 최소값 찾기에 활용할 수 없었다. 저 while문 자체를 RB-ERASE 에 넣어줘도 구현이 가능하다.
- C구현 코드
node_t *rbtree_erase_min(const rbtree *t, node_t *p) {
node_t *cur = p;
while (cur->left != t->nil) {
cur = cur->left;
}
return cur;
}
RB-ERASE(t, z)
- 일반적으로는 RB-DELETE(t, z)
- 의사 코드
RB-ERASE(t, z)
y = z // y를 삭제할 노드 z로 설정
y-original-color = y.color // y의 원래 색을 저장
// z의 왼쪽 자식이 없는 경우
if z.left = t.nil
x = z.right // x를 z의 오른쪽 자식으로 설정
RB-TRANSPLANT(t, z, z.right) // z를 z의 오른쪽 자식으로 대체
// z의 오른쪽 자식이 없는 경우
elseif z.right == t.nil
x = z.left // x를 z의 왼쪽 자식으로 설정
RB-TRANSPLANT(t, z, z.left) // z를 z의 왼쪽 자식으로 대체
// z의 양쪽 자식이 모두 있는 경우
else
y= TREE-MIN(z.right) // y를 z의 오른쪽 서브트리에서 가장 작은 노드로 설정
y-original-color = y.color // y의 원래 색을 저장
x = y.right // x를 y의 오른쪽 자식으로 설정
// y가 z의 직접적인 오른쪽 자식인 경우
if y.p == z
x.p = y // x의 부모를 y로 설정
// y가 z의 오른쪽 서브트리에서 더 아래에 있는 경우
else
RB-TRANSPLANT(t, y, y.right) // y를 y의 오른쪽 자식으로 대체
y.right = z.right // y의 오른쪽 자식을 z의 오른쪽 자식으로 설정
y.right.p = y // y의 오른쪽 자식의 부모를 y로 설정
// z를 y로 대체
RB-TRANSPLANT(t, z, y)
y.left = z.left // y의 왼쪽 자식을 z의 왼쪽 자식으로 설정
y.left.p = y // y의 왼쪽 자식의 부모를 y로 설정
y.color = z.color // y의 색을 z의 색으로 설정
// y의 원래 색이 BLACK인 경우, 레드-블랙 트리의 속성을 복구
if y-original-color == BLACK
RB-DELETE-FIXUP(t, x)
- C구현 코드
int rbtree_erase(rbtree *t, node_t *p){
node_t *y = p;
node_t *x = t->nil;
color_t y_origin_color = y->color;
if(p->left == t->nil){
x = p->right;
transplant(t,p,p->right);
}
else if(p->right == t->nil){
x = p->left;
transplant(t,p,p->left);
}
else{
y = rbtree_erase_min(t, p->right);
y_origin_color = y->color;
x = y->right;
if(y->parent == p){
x->parent = y;
}
else{
transplant(t,y,y->right);
y->right=p->right;
y->right->parent = y;
}
transplant(t,p,y);
y->left = p->left;
y->left->parent = y;
y->color = p->color;
}
if(y_origin_color == RBTREE_BLACK){
rbtree_delete_fixup(t,x);
}
free(p);
return 0;
}
RB-DELETE-FIXUP(t, x)
- 의사 코드
RB-DELETE-FIXUP(t, x)
while x != t.root and x.color == BLACK // x가 루트가 아니고, 색이 블랙인 동안 반복
if x == x.p.left // x가 부모의 왼쪽 자식인 경우
w = x.p.right // w를 x의 형제 노드로 설정
if w.color == RED // w의 색이 레드인 경우 (Case 1)
w.color = BLACK // w를 블랙으로 바꿈
x.p.color = RED // x의 부모를 레드로 바꿈
LEFT-ROTATE(t, x.p) // x의 부모를 기준으로 왼쪽 회전
w = x.p.right // w를 x의 형제 노드로 다시 설정 (w의 색은 블랙)
if w.left.color == BLACK and w.right.color == BLACK // w의 두 자식이 모두 블랙인 경우 (Case 2)
w.color = RED // w를 레드로 바꿈
x = x.p // x를 부모로 업데이트
else
if w.right.color == BLACK // w의 오른쪽 자식이 블랙인 경우 (Case 3)
w.left.color = BLACK // w의 왼쪽 자식을 블랙으로 바꿈
w.color = RED // w를 레드로 바꿈
RIGHT-ROTATE(t, w) // w를 기준으로 오른쪽 회전
w = x.p.right // w를 x의 형제 노드로 다시 설정 (w의 색은 블랙)
w.color = x.p.color // w의 색을 x의 부모의 색으로 바꿈
x.p.color = BLACK // x의 부모의 색을 블랙으로 바꿈
w.right.color = BLACK // w의 오른쪽 자식의 색을 블랙으로 바꿈
LEFT-ROTATE(t, x.p) // x의 부모를 기준으로 왼쪽 회전
x = t.root // x를 루트로 업데이트
else // x가 부모의 오른쪽 자식인 경우. 위의 조건과 대칭적임.
w = x.p.left // w를 x의 형제 노드로 설정
if w.color == RED // w의 색이 레드인 경우
w.color = BLACK // w를 블랙으로 바꿈
x.p.color = RED // x의 부모를 레드로 바꿈
RIGHT-ROTATE(t, x.p) // x의 부모를 기준으로 오른쪽 회전
w = x.p.left // w를 x의 형제
if w.right.color == BLACK and w.left.color == BLACK // w의 두 자식이 모두 블랙인 경우 (Case 2)
w.color = RED // w를 레드로 바꿈
x = x.p // x를 부모로 업데이트
else
if w.left.color == BLACK // w의 왼쪽 자식이 블랙인 경우 (Case 3)
w.right.color = BLACK // w의 오른쪽 자식을 블랙으로 바꿈
w.color = RED // w를 레드로 바꿈
LEFT-ROTATE(t, w) // w를 기준으로 왼쪽 회전
w = x.p.left // w를 x의 형제 노드로 다시 설정 (w의 색은 블랙)
w.color = x.p.color // w의 색을 x의 부모의 색으로 바꿈
x.p.color = BLACK // x의 부모의 색을 블랙으로 바꿈
w.left.color = BLACK // w의 왼쪽 자식의 색을 블랙으로 바꿈
RIGHT-ROTATE(t, x.p) // x의 부모를 기준으로 오른쪽 회전
x = t.root // x를 루트로 업데이트
x.color = BLACK // x의 색을 블랙으로 바꿈 (루트 노드는 항상 블랙)
- c구현 코드
void rbtree_delete_fixup(rbtree *t, node_t *x){
while (x != t->root && x->color == RBTREE_BLACK) {
if (x == x->parent->left){
node_t *w = x->parent->right;
// Case 1: x의 형제 w가 RED인 경우
if (w->color == RBTREE_RED){
w->color = RBTREE_BLACK;
x->parent->color = RBTREE_RED;
left_rotate(t, x->parent);
w = x->parent->right;
}
// Case 2: x의 형제 w는 BLACK이고, w의 두 자식이 모두 BLACK인 경우
if (w->left->color == RBTREE_BLACK && w->right->color == RBTREE_BLACK) {
w->color = RBTREE_RED;
x = x->parent;
}
else{
// Case 3: x의 형제 w는 BLACK, w의 오른쪽 자식은 BLACK, w의 왼쪽 자식은 RED인 경우
if (w->right->color == RBTREE_BLACK) {
w->left->color = RBTREE_BLACK;
w->color = RBTREE_RED;
right_rotate(t, w);
w = x->parent->right;
}
// Case 4: x의 형제 w는 BLACK이고, w의 오른쪽 자식은 RED인 경우
w->color = x->parent->color;
x->parent->color = RBTREE_BLACK;
w->right->color = RBTREE_BLACK;
left_rotate(t, x->parent);
x = t->root;
}
}
else {
node_t *w = x->parent->left;
// Case 1: x의 형제 w가 RED인 경우
if (w->color == RBTREE_RED){
w->color = RBTREE_BLACK;
x->parent->color = RBTREE_RED;
right_rotate(t, x->parent);
w = x->parent->left;
}
// Case 2: x의 형제 w는 BLACK이고, w의 두 자식이 모두 BLACK인 경우
if (w->right->color == RBTREE_BLACK && w->left->color == RBTREE_BLACK) {
w->color = RBTREE_RED;
x = x->parent;
}
else
{
// Case 3: x의 형제 w는 BLACK, w의 왼쪽 자식은 BLACK, w의 오른쪽 자식은 RED인 경우
if (w->left->color == RBTREE_BLACK) {
w->right->color = RBTREE_BLACK;
w->color = RBTREE_RED;
left_rotate(t, w);
w = x->parent->left;
}
// Case 4: x의 형제 w는 BLACK이고, w의 왼쪽 자식은 RED인 경우
w->color = x->parent->color;
x->parent->color = RBTREE_BLACK;
w->left->color = RBTREE_BLACK;
right_rotate(t, x->parent);
x = t->root;
}
}
}
x->color = RBTREE_BLACK;
}
트리 함수
- 따로 설명을 달아두진 않을 예정이다. 트리의 기본적인 ARRAY 호출함수, MIN 함수, MAX함수를 그대로 가져왔다.
RB-TO-ARRAY(t, arr, n)
- C구현 함수
int rbtree_to_array(const rbtree *t, key_t *arr, const size_t n){
node_t *cur = rbtree_min(t);
int i = 0;
while (cur != t->nil && i < n) {
arr[i++] = cur->key;
if (cur->right != t->nil) {
cur = cur->right;
while (cur->left != t->nil) {
cur = cur->left;
}
}
else {
while (cur->parent != t->nil && cur == cur->parent->right) {
cur = cur->parent;
}
cur = cur->parent;
}
}
return 0;
}
RB_min(t), RB_max(t)
- C 구현 함수
node_t *rbtree_min(const rbtree *t){
if(t->nil == t->root){
return NULL;
}
node_t *cur = t->root;
while (cur->left != t->nil) {
cur = cur->left;
}
return cur;
//return t->root;
}
node_t *rbtree_max(const rbtree *t){
if(t->nil == t->root){
return NULL;
}
node_t *cur = t->root;
while (cur->right != t->nil) {
cur = cur->right;
}
return cur;
//return t->root;
}
'[C]' 카테고리의 다른 글
| [C] PINTOS - KEYWORD (0) | 2023.06.01 |
|---|---|
| [C] PROXY - BOOK (0) | 2023.05.25 |
댓글