RB-Tree 구현하기 (C언어) - Part.1 설명 및 뼈대 구현

RB-Tree(Red Black Tree)란?

컴퓨터 과학에서 이진 탐색 트리(BST: binary search tree)는 다음과 같은 속성이 있는 이진트리 자료 구조이다.

• 각 노드에 값이 있다.
• 값들은 전순서가 있다.
• 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다.
• 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이루어져 있다.
• 좌우 하위 트리는 각각이 다시 이진 탐색 트리여야 한다.

높이가 h인 이진 탐색 트리에서 동적 집합 연산이 O(h) 될 수 있다는 것이다. 즉 이진 탐색 트리의 경우 치우친 편향 트리 (skewed tree)가 발생할 수 있다.

Skewed Tree 예시 - 출처 : https://www.geeksforgeeks.org/skewed-binary-tree/

위의 이미지가 치우친 편향 트리의 예시인데 만약 이러한 트리에 100개의 자식이 전부 위와 같은 모양이고 이 중 100이라는 값을 찾으려면 해당 값을 돌기 위해 트리의 오른쪽 자식을 100개나 확인해야 할 것이다. 그렇다면 위 케이스는 최악의 경우 O(n)를 가지게 된다. 위와 같은 경우를 방지하기 위해 자가 균형 이진트리(self-balancing binary tree)의 개념이 등장했다.

그 중 우리는 레드 블랙 트리에 대한 것을 다룰 예정이다.

레드 블랙 트리 (줄여서 RB-Tree)는 이진 탐색 트리(BST)의 일종이다. RB-Tree의 경우 트리에 n개의 원소가 있을 때에도 O(log N)의 시간 복잡도로 삽입, 삭제, 검색을 할 수 있다.

RB-Tree 특성

1. 모든 노드는 RED/ Black의 상태를 가진다.
2. 루트 노드는 Black이다.
3. 모든 NIL 노드는 Black이다.
4. 노드가 RED 면, 자녀는 Black이다. (Red는 연속하면 안 됨 반대로 블랙은 연속 가능)
5. 임의의 경로(자신을 제외)부터 자손 NIL 까지 Black 개수는 동일하다.

위 5개의 특성을 지켜야지 RB-Tree가 될 수 있다. 

트리의 각 노드는 color, key, left, right, parent 등의 필드를 가진다. 한 노드의 자식 또는 부모가 존재하지 않으면 그에 대응되는 노드의 포인터 필드는 NIL 값으로 채워진다.

NIL 노드란?

• RB-Tree에서 NIL 노드는 리프 노드로 사용되는 특별한 노드
• 모든 리프 노드는 NIL 노드로 취급되며, 항상 Black 색상을 가짐
• 실제 구현에서는 메모리 효율을 위해 하나의 NIL 노드를 공유하여 사용
• NIL 노드는 RB-Tree의 종료 조건을 명확히 하고, 특히 3번 속성(모든 NIL 노드는 Black)을 만족시키는데 중요한 역할
• 각 노드는 하나의 키(key), 왼쪽자식(left), 오른쪽 자식(right), 부모노드(p)의 주소를 저장한다.
• 루트의 부모 또한 NIL노드라고 가정한다.
• 노드들은 내부 노드와 NIL 노드로 분류된다.
• 리프 노드가 아닌 노드들을 내부 노드라고 한다.

NIL 노드를 사용하는 이유:

• 트리의 끝을 명확하게 표시
• RB-Tree의 속성을 검사할 때 일관된 처리가 가능
• Black 높이를 계산할 때 기준점 역할

Black Height

어떤 노드 x의 black height란, x에서부터 리프(NIL 노드)까지 가는 모든 단순 경로에서 지나치는 검은 노드(black node)의 수를 의미한다.

• 여기서 "지나친다"는 건 자기 자신은 포함하지 않고, 자식 쪽 경로 상의 노드만 포함한다.
• NIL 노드도 검은 노드로 간주된다.

---

구현 (트리 생성, 트리 삭제, 탐색)

트리 생성

rbtree *new_rbtree(void) {
    rbtree *p = (rbtree *) calloc(1, sizeof(rbtree));
    // TODO: initialize struct if needed
    
    return p;
}

위의 코드를 구현하면 되는데 내가 작성한 코드는 더 보기를 통해 확인할 수 있도록 하겠다. 되도록 직접 구현해 보는 것이 좋을 것이다.

rbtree *new_rbtree(void) {
    rbtree *p = (rbtree *) calloc(1, sizeof(rbtree));
    // TODO: initialize struct if needed
    if (p == NULL) {
        return NULL;
    }
    node_t *nil = (node_t *)calloc(1, sizeof(node_t));
    if (nil == NULL) {
        free(p);
        return NULL;
    }
    nil->color = RBTREE_BLACK;
    nil->key = 0;
    // 여기를 수정했다.
    nil->parent = nil;
    nil->left = nil;
    nil->right = nil;

    p->nil = nil;
    p->root = nil;
    return p;
}

 

구현 아이디어:

1. rbtree라고 이름 붙여진 구조체를 생성한다. 이때 동적 메모리 할당을 통해 메모리를 할당한다.
2. 메모리 할당이 정상적으로 이루어졌는지 체크한다.
3. nil 노드로 사용할 노드를 생성한다. 이때 에도 동적 메모리 할당을 통해 메모리를 할당한다.
4. nil 노드의 색, key, 부모노드, left, right 노드 정보를 업데이트한다.
5. 트리의 정보를 초기화한다. nil노드를 사용하는 경우 트리의 생성 직후 루트 및 nil 노드 정보는 nil이 될 것이다.

트러블 슈팅 내역:

처음 구현했을 때 nil 노드의 부모, 자식들을 NULL로 설정했었는데 이렇게 만든 뒤 생성에 대한 테스트 코드는 통과가 됐는데 최종 테스트에 실패했다. 이게 왜 문제였냐면 트리를 순회하거나 조작을 할 때 nil노드의 자식이나 부모를 참조하게 되면 NULL 접근이 발생하게 되고 잘못된 접근으로 세그멘테이션 오류가 발생할 수 있었다.

또한 RB-Tree에서 nil 노드는 자기 참조하도록 설정하는 것이 정석이기 때문이다.

트리 삭제

void delete_rbtree(rbtree *t) {
}

위의 코드를 구현하면 되는데 내가 작성한 코드는 더 보기를 통해 확인할 수 있도록 하겠다.

void free_child_data(rbtree *t, node_t *root) {
    if (root == t->nil) {
        return;
    }
    free_child_data(t, root->left);
    free_child_data(t, root->right);
    free(root);
}


void delete_rbtree(rbtree *t) {
    // TODO: reclaim the tree nodes's memory
    if (t->root != t->nil) {
        free_child_data(t, t->root);
    }
    free(t->nil);  // sentinel node 해제
    free(t);
}

트리를 구성하던 모든 노드의 동적 할당된 메모리를 해제하는 방법으로 재귀를 사용하여 구현할 것이다.

구현 아이디어:

트리 제거

1. 트리의 루트 노드가 nil이 아닐 경우 재귀적으로 자식 노드들을 제거한다.
2. 재귀가 종료되어 자식 노드들이 제거되면 트리와 연결된 nil노드를 제거한다.
3. nil노드를 제거하고 최종 적으로 트리를 제거한다.

자식 노드 제거

1. 재귀 종료를 위한 베이스 조건을 설정한다.
2. 왼쪽 자식을 제거한다.
3. 오른쪽 자식을 제거한다.
4. 재귀에서 복귀할 때 루트를 제거한다. (후위 순회 사용)

트리 탐색

node_t *rbtree_find(const rbtree *t, const key_t key) {
    // TODO: implement find
}

탐색에 대한 코드 역시 더 보기를 통해 확인할 수 있다.

node_t *rbtree_find(const rbtree *t, const key_t key) {
    // TODO: implement find
    node_t *cur = t->root;
    while (t->nil != cur) {
        if (key == cur->key) {
            return cur;
        }else {
            if (key < cur->key) {
                cur = cur->left;
            } else {
                cur = cur->right;
            }
        }
    }
    return NULL;
}

구현 아이디어 :

1. 반복문을 사용한다. (조건 = 현재 노드가 nil노드가 될 때까지
2. 먼저 현재 노드 값이 찾으려는 키 값과 같은지 확인하고 같다면 현재 노드를 반환
3. 아닌 경우 현재 노드의 키 값과 찾으려는 키의 값을 비교해 찾으려는 키 값이 더 작으면 왼쪽 크다면 오른쪽 노드를 현재 노드로 재 지정한다.
4. 현재 노드가 nil 노드가 될 때까지 돌았는데 키 값을 찾지 못한 경우 NULL을 반환한다.

---

이렇게 트리 생성, 트리 삭제, 트리 탐색을 구현해 봤다. 다음 포스팅에서는 나머지 기타적인 기능을 구현해 보겠다.

---

출처

https://www.geeksforgeeks.org/skewed-binary-tree/