RB-Tree 구현하기 (C언어) - Part.2 최소, 최대, 출력 구현

1. 구현 목표

이전 포스팅을 통해 RB-Tree의 생성과 트리 삭제, 탐색을 다뤘다면 이번 글에서는 RB-Tree의 핵심인 삽입과 삭제를 다루기 전에 추가적으로 필요한 기능들을 구현하고 넘어가려고 한다.

2025.04.20 - [크래프톤 정글] - RB-Tree 구현하기 (C언어) - Part.1 설명 및 뼈대 구현

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

우리가 이번에 구현할 기능은 RB-Tree에서 최소 값과 최댓값을 찾는 기능을 각각 구현할 것이며 RB-Tree에 있는 값들을 출력하기 위한 기능을 구현할 것이다.

---

2. 기능 구현

🔨 rbtree_min

node_t *rbtree_min(const rbtree *t) {
	// TODO: implement find
}

이 기능은 전체 트리에서 가장 작은 값이 있는 노드를 찾아내는 기능이다. 구현된 함수는 아래 더 보기를 통해 확인할 수 있으나 바로 확인하지 않고 구현해 보고 이후에 열어보는 것을 추천한다.

node_t *rbtree_min(const rbtree *t) {
    // TODO: implement find
    node_t *cur = t->root;
    while (cur->left != t->nil) {
        cur = cur->left;
    }
    return cur;
}

구현 아이디어 :

1. 이진 탐색 트리의 경우 루트보다 작은 값은 왼쪽에 있다.
2. 현재 노드의 왼쪽 자식 노드가 nil이 나올 때까지 반복한다.
3. 즉 가장 왼쪽으로 계속 들어가서 값을 찾는 것이다.

코드가 매우 쉽다. 이 말은 가장 큰 값을 찾는 기능 역시 비슷하게 작성이 가능하다는 것이다.

🔨 rbtree_max

node_t *rbtree_max(const rbtree *t) {
    // TODO: implement find
}

이 기능은 전체 트리에서 가장 큰 값이 있는 노드를 찾아내는 기능이다. 구현된 함수는 아래 더 보기를 통해 확인할 수 있으나 바로 확인하지 않고 구현해 보고 이후에 열어보는 것을 추천한다.

node_t *rbtree_max(const rbtree *t) {
    // TODO: implement find
    node_t *cur = t->root;
    while (cur->right != t->nil) {
        cur = cur->right;
    }
    return cur;
}

구현 아이디어 :

1. 이진 탐색 트리의 경우 루트보다 큰 값은 오른쪽에 있다.
2. 현재 노드의 오른쪽 자식 노드가 nil이 나올 때까지 반복한다.
3. 즉 가장 오른쪽으로 계속 들어가서 값을 찾는 것이다.

🔨 rbtree_to_array

이 함수는 RB-Tree 안의 모든 값을 조회해서 이를 arr에 저장하는 것이다.

int rbtree_to_array(const rbtree *t, key_t *arr, const size_t n) {
    // TODO: implement to_array
}

역시 아래 더 보기를 눌러 완성 코드를 확인할 수 있다.

void in_order_search(const rbtree *t, key_t *arr, size_t n, int *ptr_i, node_t *p) {
    if (p == t->nil || *ptr_i >= n) {
        return;
    }
    in_order_search(t, arr, n, ptr_i, p->left);
    if (*ptr_i < n) {
        arr[*ptr_i] = p->key;
        *ptr_i += 1;
    }
    in_order_search(t, arr, n, ptr_i, p->right);
}


int rbtree_to_array(const rbtree *t, key_t *arr, const size_t n) {
    // TODO: implement to_array
    node_t *cur = t->root;
    int i = 0;
    int *ptr_i = &i;
    in_order_search(t, arr, n, ptr_i, cur);
    return 0;
}

구현 아이디어 :

1. 이진 탐색 트리를 기반으로 하는 것이 RB-Tree이니 재귀적인 방법으로 값들을 탐색하면서 배열을 만들 수 있지 않을까?
2. 하지만 rbtree_to_array 함수의 입력 값들을 보니 현재 상태에서는 재귀를 사용할 수 없다. 우리는 원형 함수의 인자를 수정할 수 없기 때문
3. 별도의 함수를 만들어서 중위순회를 이용한 탐색을 진행
4. 원본 함수의 입력에는 트리의 사이즈를 나타내는 n이라는 값이 있는데 이를 활용해야 한다.
5. 재귀 베이스 조건 - 현재 탐색하는 노드가 nil이거나 *prt_i 가 n 보다 크거나 작은 경우 즉 노드 크기에 도달했을 경우
6. 왼쪽 자식 확인 (재귀)
7. 루트 기록 - 배역 arr[*ptr_i] 에 노드의 키 값을 추가하고 *prt_i의 값을 1 증가한다. 
8. 오른쪽 자식 확인 (재귀)

---

이렇게 3가지 추가적인 함수를 구현했다. 이제 다음 포스팅부터는 삽입과 삭제라는 RB-Tree의 가장 중요한 기능들을 차례로 살펴보고 구현해 볼 것이다.