이번 글에서는 이진 탐색 트리(BST)에서 바닥(Floor)과 천장(Ceiling) 값을 찾는 방법을 살펴봅니다. 예를 들어, 가용 노드들을 BST 형태로 배치한 메모리 관리 시스템을 만든다고 가정해 봅시다. 입력된 요청에 가장 잘 맞는(best fit) 노드를 찾으려면 키 값보다 큰 데이터 중 가장 작은 값을 향해 트리를 내려가게 되는데, 이 탐색 과정에서 다음의 세 가지 경우가 발생합니다.
천장(Ceiling) 값 탐색의 세 가지 경우
- 루트가 키와 같은 경우: 루트 값이 곧 천장 값입니다.
- 루트 데이터가 키보다 작은 경우: 천장 값은 왼쪽 서브트리에 존재할 수 없습니다. 따라서 오른쪽 서브트리로 이동하여 문제의 탐색 범위를 줄여 나갑니다.
- 루트 데이터가 키보다 큰 경우: 루트가 천장 값의 후보가 되지만, 왼쪽 서브트리 안에 키보다 크면서 루트보다는 작은 노드가 존재할 수도 있습니다. 왼쪽 서브트리를 탐색했을 때 그런 노드가 없다면 루트가 최종적인 천장 값이 됩니다.
설명을 위해 다음과 같은 트리를 가정합니다.
이 트리에서 0, 1, 2의 천장 값은 2이고, 3과 4의 천장 값은 4이며, 나머지 값들도 같은 방식으로 결정됩니다.
여기서는 천장 함수만 구현하지만, 비교 조건을 조금만 수정하면 바닥(Floor) 값도 동일한 방식으로 구할 수 있습니다. 바닥 값이란 키보다 작거나 같은 값 중에서 가장 큰 값을 의미합니다.
예제 코드
#include <iostream>
using namespace std;
class node {
public:
int key;
node* left;
node* right;
};
node* getNode(int key) {
node* newNode = new node();
newNode->key = key;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
int ceiling(node* root, int num) {
if (root == NULL)
return -1;
if (root->key == num)
return root->key;
if (root->key < num)
return ceiling(root->right, num);
int ceil = ceiling(root->left, num);
return (ceil >= num) ? ceil : root->key;
}
int main() {
node* root = getNode(8);
root->left = getNode(4);
root->right = getNode(12);
root->left->left = getNode(2);
root->left->right = getNode(6);
root->right->left = getNode(10);
root->right->right = getNode(14);
for (int i = 0; i < 16; i++)
cout << i << "\tCeiling: " << ceiling(root, i) << endl;
}실행 결과
0 Ceiling: 2 1 Ceiling: 2 2 Ceiling: 2 3 Ceiling: 4 4 Ceiling: 4 5 Ceiling: 6 6 Ceiling: 6 7 Ceiling: 8 8 Ceiling: 8 9 Ceiling: 10 10 Ceiling: 10 11 Ceiling: 12 12 Ceiling: 12 13 Ceiling: 14 14 Ceiling: 14 15 Ceiling: -1
출력에서 확인할 수 있듯이, 키와 동일한 값이 트리에 존재하면 그 값 자체가 천장 값이 됩니다. 반면 15처럼 트리에 키보다 크거나 같은 값이 전혀 없는 경우에는 -1이 반환됩니다. 이 알고리즘은 각 단계마다 한쪽 서브트리만 탐색하므로, 트리의 높이에 비례하는 O(h)의 시간 복잡도로 동작한다는 점도 주목할 만합니다.