이 문제에서는 이진 탐색 트리(Binary Search Tree)와 두 개의 경계값 k1, k2가 주어집니다. 우리가 해야 할 일은 트리에 존재하는 노드 중에서 k1과 k2 사이의 범위에 속하는 모든 값을 찾아 오름차순으로 출력하는 것입니다. 즉, k1보다 크거나 같고 k2보다 작거나 같은 값을 가진 모든 키를 정렬된 순서대로 출력해야 합니다.
이진 탐색 트리(BST)란?
이진 탐색 트리는 다음 세 가지 성질을 만족하는 트리입니다.
- 왼쪽 서브트리의 모든 노드는 부모 노드보다 작은 값을 가집니다.
- 오른쪽 서브트리의 모든 노드는 부모 노드보다 큰 값을 가집니다.
- 모든 서브트리 역시 이진 탐색 트리의 성질을 만족해야 하며, 트리에는 중복된 노드가 존재할 수 없습니다.
문제 예시
입력 : k1 = 12, k2 = 25 출력 : 15, 20, 24
설명 − 트리를 순회하면서 모든 요소를 검사하고, 그중 12 이상 25 이하의 범위에 속하는 노드 x(12 ≤ x ≤ 25)의 값만 출력합니다.
접근 방법
이 문제는 BST의 핵심 성질을 활용하면 효율적으로 해결할 수 있습니다. BST에서는 루트보다 작은 값들이 모두 왼쪽 서브트리에, 루트보다 큰 값들이 모두 오른쪽 서브트리에 위치한다는 점을 이용합니다.
또한 중위 순회(In-order Traversal)를 사용하면 트리의 값을 자동으로 오름차순으로 방문할 수 있으므로, 별도의 정렬 과정 없이 결과를 출력할 수 있습니다. 이제 문제를 해결하기 위한 알고리즘을 살펴보겠습니다.
알고리즘
Step 1 : 루트 노드의 값을 k1, k2와 비교한다. Step 2 : 루트의 값이 k1보다 크면, 왼쪽 서브트리를 재귀적으로 탐색한다. Step 3 : 루트의 값이 k2보다 작으면, 오른쪽 서브트리를 재귀적으로 탐색한다. Step 4 : 루트의 값이 [k1, k2] 범위 안에 있다면, 해당 값을 출력한다.
C++ 구현 예제
위 알고리즘을 바탕으로 문제를 해결하는 C++ 프로그램을 작성해 보겠습니다.
#include<bits/stdc++.h>
using namespace std;
class node{
public:
int data;
node *left;
node *right;
};
void nodesInRange(node *root, int k1, int k2){
if ( NULL == root )
return;
if ( k1 < root->data )
nodesInRange(root->left, k1, k2);
if ( k1 <= root->data && k2 >= root->data )
cout<<root->data<<"\t";
if ( k2 > root->data )
nodesInRange(root->right, k1, k2);
}
node* insert(int data){
node *temp = new node();
temp->data = data;
temp->left = NULL;
temp->right = NULL;
return temp;
}
int main(){
node *root = new node();
int k1 = 12, k2 = 25;
root = insert(20);
root->left = insert(10);
root->right = insert(24);
root->left->left = insert(8);
root->left->right = insert(15);
root->right->right = insert(32);
cout<<"범위 내에 있는 노드의 값 : ";
nodesInRange(root, k1, k2);
return 0;
}실행 결과
범위 내에 있는 노드의 값 : 15 20 24
동작 원리 정리
이 알고리즘의 시간 복잡도는 균형 잡힌 BST의 경우 O(log n + k)(k는 범위 내 노드 수)이며, 최악의 경우 편향된 트리에서 O(n)이 됩니다. BST의 성질 덕분에 범위 밖에 있는 서브트리 전체를 가지치기(pruning)하여 탐색하지 않아도 되므로, 단순히 전체 트리를 순회하는 것보다 훨씬 효율적입니다.