[RBTree] 탐색 및 최솟값/최댓값 함수 구현하기 (rbtree_find, rbtree_min, rbtree_max)

RB트리 탐색 및 최솟값/최댓값 함수 구현하기

RPG 게임에서 레벨이 오르면 새로운 콘텐츠가 해금되듯이, RB트리도 삽입 기능이 구현되면 여러 기능들을 추가로 구현하는 것이 가능해지는데요. 그중 대표적인 것이 바로 탐색 기능입니다. 특정 값을 가진 노드를 찾거나, 가장 작거나 큰 값을 가진 노드를 빠르게 찾을 수 있게 되는 것이죠. 이번 글에서는 이러한 핵심 탐색 기능을 담당하는 함수들을 직접 구현해 보겠습니다.

 

 

RB트리 탐색 함수 (rbtree_find)

rbtree_find 함수는 RB트리에서 특정 값을 가진 노드를 찾아 반환하는 함수입니다. RB트리라고 해서 탐색 방식이 특별하지는 않고, 기본적인 이진 탐색 트리(BST)와 완전히 동일한 방식으로 동작합니다. 찾고자 하는 값이 현재 노드의 값보다 작으면 왼쪽 서브트리로, 크면 오른쪽 서브트리로 이동하면서 탐색을 진행하죠. 그러던 중 동일한 값을 찾으면 해당 노드를 반환하고, 끝까지 찾지 못한 경우에는 sentinel 노드인 nil을 반환하게 됩니다.

 

탐색 함수 구현하기

node_t *rbtree_find(const rbtree *t, const key_t key) {
  // 트리의 루트 노드부터 탐색 시작
  node_t *cur = t->root;

  // 현재 노드가 nil(트리의 끝)이 아닐 때까지 반복
  while (cur != t->nil) {
    // 현재 노드의 키 값이 찾는 값과 같으면 해당 노드를 반환
    if (key == cur->key) {
      return cur;
    }
    // 찾는 값이 현재 노드보다 작으면 왼쪽 자식으로 이동
    else if (key < cur->key) {
      cur = cur->left;
    }
    // 찾는 값이 현재 노드보다 크면 오른쪽 자식으로 이동
    else {
      cur = cur->right;
    }
  }
  // 값을 찾지 못한 경우 nil 노드 반환
  return t->nil;
}

 

 

RB트리 최솟값/최댓값 함수 (rbtree_min, rbtree_max)

rbtree_min과 rbtree_max 함수는 RB트리에서 각각 최솟값을 가진 노드와 최댓값을 가진 노드를 찾아 반환하는 함수입니다. 이 함수들의 로직은 정말 간단한데요.

• 최솟값을 찾기 위해서는 왼쪽 자식이 없을 때까지 계속 왼쪽으로 내려가고,
• 최댓값은 오른쪽 자식이 없을 때까지 계속 오른쪽으로 내려가면 됩니다.

즉, 이진 탐색 트리의 구조만 이해하고 있다면 누구나 쉽게 구현할 수 있는 함수들입니다.

 

최솟값/최댓값 함수 구현하기

// RB트리에서 가장 작은 값을 가진 노드를 반환하는 함수
node_t *rbtree_min(const rbtree *t) {
  // 트리의 루트 노드부터 탐색 시작
  node_t *cur = t->root;

  // 왼쪽 자식이 있는 동안 계속 왼쪽으로 이동
  while (cur->left != t->nil) {
    cur = cur->left;
  }

  // 가장 작은 값을 가진 노드를 반환
  return cur;
}

// RB트리에서 가장 큰 값을 가진 노드를 반환하는 함수
node_t *rbtree_max(const rbtree *t) {
  // 트리의 루트 노드부터 탐색 시작
  node_t *cur = t->root;

  // 오른쪽 자식이 있는 동안 계속 오른쪽으로 이동
  while (cur->right != t->nil) {
    cur = cur->right;
  }

  // 가장 큰 값을 가진 노드를 반환
  return cur;
}