적응했나..? 예전에 누으면 바로 잤는데 1시 넘어서 잠
일찍 잔다!!(라고 며칠째 다짐만 하는 중)
08:04 입실
RB트리 삽입, 삭제 원리 이해한다!!
RB Tree 삽입, 삭제는 BST부터 정확히 알고 있어야 됨.
https://www.youtube.com/watch?v=UEQp7kgIZQI
BST에서 전임자(Predecessor) & 후계자(Successor)
전임자
삭제하려는 노드보다 작은 값 중에서 가장 큰 값
즉, 왼쪽 서브트리에서 가장 큰 노드
후계자
삭제하려는 노드보다 큰 값 중에서 가장 작은 값
즉, 오른쪽 서브트리에서 가장 작은 노드
둘을 합해서 대체자(relacement)라고 함.
이진 검색 트리에서 삭제 연산을 진행할 때 트리 순서 유지를 위해 대체자가 필요함.
노드 값, 구성에 따라 유불리가 있을 수 있으나 둘 중 무엇을 사용해도 트리 특성은 보장됨.
단, 대체자의 종류에 따라 트리의 균형이 달라질 수 있음.
전임자와 후계자는 오름차순 정렬에서 노드를 중심으로 각각 바로 앞, 뒤 노드를 지칭함!
RB Tree 삽입
삽입하는 노드는 무조건 RED
이진 검색 트리 조건에 맞춰서 삽입함.
그 후 속성 유지 검사 후 재조정
-
색상 변경: 부모와 삼촌 노드의 색상 변경
-
회전: 트리 구조 변경을 위해 좌회전 또는 우회전
(회전은 두 연속된 레드 노드 해결, 삽입 노드의 부모 노드가 레드인 상황 해결) -
루트 노드가 레드라면 블랙으로 변경
삽입 시 발생할 수 있는 위반 사항
-
모든 노드는 적색이거나 흑색이다. ✅ -> 신규 노드가 레드니까 위반 없음
-
루트는 흑색이다. ❌ -> 신규 노드가 루트일 때 발생, 또는 조정 후 발생할 수 있음.
-
모든 리프는 흑색이다. ✅ -> 신규 노드의 리프는 T.nil이니까 위반 없음
-
노드가 적색이면 그 노드의 자식은 모두 흑색이다. ❌ -> 신규 노드의 부모가 적색일 때 발생
-
노드에서 자손리프로 가는 경로에는 같은 수의 흑색이 있다. ✅ -> 신규 노드가 레드니까 위반 없음
삽입 시 위반 사항은 2 또는 4 중 하나만 발생한다.
RB Tree 삽입 위반 케이스 및 조정 방법
재구성과 회전!
(z는 새로 삽입된 레드 노드)
위반 케이스1. (z의 부모는 레드) 삼촌 y가 적색인 경우
1. 삽입된 노드의 부모와 삼촌을 블랙으로 변경
2. 삽입된 노드의 조부모를 레드로 변경
(1과 2를 합해서 조부모의 블랙을 각각의 자식(부모, 삼촌)에게 내려보낸다고 이해!)
3-1. 조부모 노드가 루트라면 루트를 블랙으로 변경하고 삽입 과정 종료.
3-2. 조부모 노드가 루트 노드가 아니라면, 조부모 노드가 새로운 z노드가 되어 1~2를 다시 검토
(즉, z가 루트가 될 때까지 반복)
위반 케이스2. (z의 부모는 레드) z의 삼촌 y가 흑색이며, z가 오른쪽 자식인 경우
(z와 부모가 대각선 관계)
z의 부모를 중심으로 회전을 수행하여 케이스3을 만든다.
위반 케이스3. (z의 부모는 레드) z의 삼촌 y가 흑색이며, z가 왼쪽 자식인 경우
(z와 부모가 직선 관계)
조부모를 중심으로 회전 후, 색을 조정한다.
레드 블랙 트리에서 형제끼리 색이 꼭 같을 필요는 없다!
부모가 블랙이면 위반 케이스에 해당하지 않는다.
위반 케이스 2, 3이 생길 수가 없지 않나? 라고 생각함.
nil를 고려하지 않아서 생겼던 오해!
nil노드도 블랙인 삼촌 노드가 될 수 있다!
Dangling pointer
free는 해당 메모리 블록의 값을 없애는 게 아니다.
free역할은 운영체제 메모리 관리자에게 "그 메모리 블록이 더 이상 사용되지 않으니 재할당 가능해!"라고 알려주는 것. 즉, 해당 메모리 블록의 "사용 중" 표시를 제거하는 것이다.
free로 해제 후에도 포인터 변수 자체는 존재하면, 해제된 메모리 주소를 가리키고 있다.
이 상태의 포인터를 dangling pointer(댕글링 포인터)라고 한다.
따라서 free후에는 해당 포인터를 NULL로 설정하는 게 안전한 코딩 관습이다.
왜냐면 NULL포인터를 참조하려고 하면 운영체제를 에러를 발생시켜 프로그램을 중단시킨다.
물론 코드상으로 해제한 포인터를 다시 사용하지 않는 경우 NULL 지정 여부는 코드에 영향을 미치지 않는다.
하지만 메모리 반납 후 포인터를 NULL로 지정하면 해당 포인터를 사용하지 않는다는 것을 명시적으로 표시할 수 있고, 추후 코드 확장 시에 포인터를 잘못 사용했을 때 디버깅이 쉬워진다.
// 꺼낸 노드를 해제합니다.
free(node);
node = NULL;RB-Tree 삭제
(삭제는 삽입보다 복잡함)
- 삭제할 키는 가진 노드 탐색
- 자식이 없거나 하나만 있으면 간단하게 삭제 처리
자식이 두 개면 대체 노드(보통 삭제할 노드의 직후 노드)를 찾아 삭제할 노드와 교체 - 색깔 조정 및 회전
RB Tree 삭제 위반 케이스 및 조정 방법
어떤 색이 삭제되었는지가 관건!
삭제되는 색이 레드라면 트리 속성을 위반하지 않으며, 비교적 간단히 처리할 수 있다.
삭제되는 색이 블랙일 때 블랙이 부족한 위반이 발생하며 임시적으로 더블블랙을 부여한다.
이 더블블랙을 해결하기 위해 4가지 케이스가 있다.
(형제 w는 새롭게 올라오는 x기준이며 삭제 노드가 블랙이어서 x에 더블블랙이 부여된 상황)
케이스1. 형제 w가 적색
문제: 형제 w가 적색이면 균형이 깨진다.
1. w와 부모 노드 색상 교환.
2. 부모 노드에 대해 회전(삭제 노드가 왼쪽 자식이면 좌회전, 오른쪽 자식이면 우회전)
3. 회전 후 형제 w는 흑색이 되며, 이후 케이스2, 3, 4로 변환
케이스2. 형제 w가 흑색이고, w의 두 자식이 모두 흑색
문제: 삭제된 경로에 검은 노드가 부족하다.(더블블랙)
1. 형제 노드 w를 적색으로 변경. 이렇게 하면 부모에게 x의 더블블랙을 전가하기 위한 조치.
2. 더블 블랙을 부모 노드로 이동, 부모가 루트면 더블 블랙 제거 ✅
3. 부모가 루트가 아닌 적색이라면, 부모를 블랙으로 변경하고 더블 블랙 제거 ✅
4. 부모가 루트가 아닌 흑색이라면 부모 노드가 더블 블랙이 되므로, 케이스 1-4로 변환
케이스3. 형제 w가 흑색이고, w의 왼쪽 자식은 적색, 오른쪽 자식은 흑색
문제: 삭제된 경로에 검은 노드가 부족하다.(더블블랙)
1. w와 왼쪽 자식 색상 교환(회전 후 블랙 수를 맞추기 위해서)
2. w에 대해 우회전
3. 케이스 4로 변환
케이스4. 형제 w가 흑색이고, 오른쪽 자식은 적색
문제: 삭제된 경로에 검은 노드가 부족하다.(더블블랙)
1. w와 부모 노드 색상 교환(회전 후 블랙 수를 맞추기 위해서)
2. 적색 자식을 흑색으로 변경(더블블랙 제거) ✅
3. 부모 노드에 대해 좌회전
4. 트리 조정 완료. x를 트리의 루트로 넘김.(루트는 최종적으로 블랙으로 강제 변경)
점심먹고 나서부터 케이스4 진심 하루 종일 이해 못함..
GPT4는 이상한 소리만 하다가 3.5가 제대로 알려줌.
케이스4의 3에서 레드 자식을 흑색으로 변경하는게 더블블랙 제거 기능을 갖는 이유는
단순히 적색을 블랙을 변경하는 관점에서 생각하는 게 아니라
공통된 부모로부터 각각 블랙을 내려 받는다고 생각.
그럼 왼쪽 서브트리의 더블블랙 없앨 수 있고, 오른쪽 서브트리의 레드 노드를 블랙으로 바꿀 수 있는 것.
이거 이해하는데 8시간은 걸렸네.. 와..
RB Tree 회전 코드
// 좌회전 함수
void left_rotate(rbtree *t, node_t *x)
{
if (x == t->nil || x->right == t->nil) {
return;
}
// y를 설정
node_t *y = x->right;
// y의 왼쪽 서브트리를 x의 오른쪽 서브트리로 옮긴다.
x->right = y->left;
y->left->parent = x;
// y의 부모를 x의 부모로 변경한다.(y를 부모 자리로 승격)
y->parent = x->parent;
if (x->parent == t->nil) { // x가 루트였다면 승격된 y를 트리의 루트로 설정
t->root = y;
} else if (x == x->parent->left) { // x가 왼쪽 자식 노드였다면 승격된 y를 기존
// 부모의 왼쪽 자식으로 설정
x->parent->left = y;
} else { // // x가 오른쪽 자식 노드였다면 승격된 y를 기존 부모의 오른쪽
// 자식으로
// 설정
x->parent->right = y;
}
// 승격된 y와 강등된 x의 관계를 설정
y->left = x;
x->parent = y;
}
// 우회전 함수
void right_rotate(rbtree *t, node_t *x)
{
if (x == t->nil || x->left == t->nil) {
return;
}
// y를 설정
node_t *y = x->left;
// y의 오른쪽 서브트리를 x의 왼쪽 서브트리로 옮긴다.
x->left = y->right;
y->right->parent = x;
// y의 부모를 x의 부모로 변경한다.(y를 부모 자리로 승격)
y->parent = x->parent;
if (x->parent == t->nil) { // x가 루트였다면 승격된 y를 트리의 루트로 설정
t->root = y;
} else if (x == x->parent->left) { // x가 왼쪽 자식 노드였다면 승격된 y를 기존
// 부모의 왼쪽 자식으로 설정
x->parent->left = y;
} else { // // x가 오른쪽 자식 노드였다면 승격된 y를 기존 부모의 오른쪽
// 자식으로
// 설정
x->parent->right = y;
}
// 승격된 y와 강등된 x의 관계를 설정
y->left = x;
x->parent = y;
}RB Tree 삽입 후 속성 위반 교정 코드
void rbtree_insert_fixup(rbtree *t, node_t *z)
{
// 신규 노드가 루트면 끝 && 신규 노드의 부모 레드면 계속 체크
while (z != t->root && z->parent->color == RBTREE_RED) {
if (z->parent == z->parent->parent->left) { // 부모가 왼쪽 자식이라면
node_t *y = z->parent->parent->right; // 삼촌 노드 설정
if (y->color == RBTREE_RED) {
// 케이스1: z의 삼촌 y가 레드
z->parent->color = RBTREE_BLACK; // 부모 노드를 블랙으로 설정
y->color = RBTREE_BLACK; // 삼촌 노드를 블랙으로 설정
z->parent->parent->color =
RBTREE_RED; // 조부모를 레드로 설정(부모와 삼촌에게 블랙을 물려줌)
z = z->parent->parent; // 레드로 설정된 조부모를 신규 삽입 노드로 취급
} else {
if (z == z->parent->right) {
// 케이스2: z가 오른쪽 자식인 경우(2는 궁극적으로 케이스 3이 됨)
z = z->parent; // 회전 기준을 z의 부모로 설정
left_rotate(t, z);
}
// 케이스 3: z가 왼쪽 자식인 경우
z->parent->color = RBTREE_BLACK;
z->parent->parent->color = RBTREE_RED;
right_rotate(t, z->parent->parent); // 조부모를 기준으로 회전
}
} else { // 부모가 오른쪽 자식이라면(좌회전과 반대 코드)
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_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;
}RB Tree 삽입 코드
과제 조건에서는 동일키도 집어 넣게 되어 있다.
그건 아직 구현 못했으니까 어떻게 해야할지 고민해보기!
어렵지 않아서 바로 중복키 허용으로 수정함!
우선 오른쪽 노드로 집어넣었음.
node_t *rbtree_insert(rbtree *t, const key_t key)
{
node_t *new_node = (node_t *)(malloc(sizeof(node_t)));
if (new_node == NULL) {
print_malloc_failed();
return t->root;
}
new_node->key = key;
new_node->color = RBTREE_RED;
new_node->left = t->nil;
new_node->right = t->nil;
node_t *current = t->root;
node_t *parent = t->nil;
// BST에 따라 루트부터 신규 노드가 삽입될 위치를 찾습니다.
while (current != t->nil) {
parent = current;
if (key < current->key) {
current = current->left;
} else if (key > current->key) {
current = current->right;
} else {
// 키가 중복되었을 경우
current = current->right;
}
}
// 신규 노드의 부모를 설정
new_node->parent = current;
if (parent == t->nil) { // 부모가 nil이면 신규 노드를 트리의 루트로 설정
t->root = new_node;
} else if (key < parent->key) { // 신규 노드의 키가 부모의 키보다 작으면
// 부모의 왼쪽 자식으로 설정
parent->left = new_node;
} else if (key > parent->key) {
parent->right = new_node; // 신규 노드의 키가 부모의 키보다 작으면
// 부모의 오른쪽 자식으로 설정
} else {
parent->right = new_node; // 중복 키라면 부모의 오른쪽 자식으로 설정
}
// RB Tree 특성 복구
rbtree_insert_fixup(t, new_node);
return t->root;
}삽입, 삭제 이해에 거의 하루 종일 걸렸지만,
이해 후에 삽입 코드 구현은 크게 어렵지 않았음!
물론 GPT로 구현했지만..
코드는 다 이해하고 반복 타이핑하면 혼자 짤 수 있을 것 같음!
주석이 더러운데 완전히 이해되면 없애야지..
파이썬으로 자료구조 공부할 때 파이썬으로 클래스 만들어서
자료구조 직접 짜본게 정말 많은 도움이 되었음!
C가 낯설긴하지만 구현 자체에 큰 어려움은 없었음!
다만 아직 구조체와 포인터가 익숙치 않음.
레드블랙트리 구현 다하면 다른 자료구조도 만들어 보면 좋겠다!
RB Tree 검색 코드 구현
node_t *rbtree_find(const rbtree *t, const key_t key)
{
node_t *current = t->root;
while (current != t->nil) { // 현재 노드가 nil이 아니면 계속 검색
if (key == current->key) { // 찾았음
return current;
}
if (key < current->key) {
current = current->left; // 좌측 탐색
} else {
current = current->right; // 우측 탐색
}
}
printf("일치하는 키가 없습니다.\n");
return NULL;
}검색을 구현할 때 DSF, BSF 어떻게 구현해야 할까?
이건 바보같은 생각이었다!!
RB Tree는 이미 정렬이 되어있기 때문에 BST 특징에 따라 루트부터 순차적으로 검색하면 됨. 굳이 따지자면 DSF와 비슷한 느낌이지만, DSF처럼 모든 경로를 탐색하는 게 아님! (시간복잡도 O(log N)으로 종결!)
즉, 현재 노드를 중심으로 왼쪽, 오른쪽 중 크기 비교하면서 리프쪽으로 탐색,
키를 찾으면 현재 노드를 반환하고,
nil노드를 만날 때까지 키를 못 찾으면 root를 반환
RB Tree 최솟값, 최대값 찾기
node_t *rbtree_min(const rbtree *t)
{
node_t *current = t->root;
while (current->left != t->nil) {
current = current->left;
}
return current;
}
node_t *rbtree_max(const rbtree *t)
{
node_t *current = t->root;
while (current->right != t->nil) {
current = current->right;
}
return current;
}검색 구현하면서 RB Tree(BST)의 위대함(?)을 느낌!
이미 정렬된 배열이 마치 마법과 같다고 할 수 있다.
최솟값, 최대값을 찾으려고 전체 노드를 순회할 필요 없다!
최솟값은 왼쪽 노드만 파면 되고, 최대값은 오른쪽 노드만 파면된다.
그래도 시간 복잡도는 O(log N)
1000개의 노드도 10번 정도면 찾을 수 있다.
10억개의 노드라도 약 30번이면 찾을 수 있다.
log[2]{1000000000} = 29.897352853986
여기서 100억이면 고작 3번 증가함.
log[2]{10000000000} = 33.219280948874
