노드들로 구성된 이진 탐색 트리(Binary Search Tree)와 하나의 범위가 주어졌을 때, 해당 범위 안에 포함되는 노드의 개수를 계산하고 그 결과를 출력하는 것이 이 글의 목표입니다.
이진 탐색 트리(BST)란?
이진 탐색 트리(BST)는 모든 노드가 다음 성질을 만족하는 트리 자료구조입니다.
- 노드의 왼쪽 서브트리에는 부모 노드의 키 값보다 작거나 같은 키를 가진 노드들이 위치합니다.
- 노드의 오른쪽 서브트리에는 부모 노드의 키 값보다 큰 키를 가진 노드들이 위치합니다.
따라서 BST는 모든 서브트리를 왼쪽 서브트리와 오른쪽 서브트리 두 영역으로 나누며, 다음과 같이 정의할 수 있습니다.
left_subtree(키들) ≤ node(키) ≤ right_subtree(키들)
예시
입력 −
범위: [11, 40]
출력 − 개수: 5
설명 − [11, 40] 범위 사이에 있는 노드 값은 14, 19, 27, 31, 35이므로, 주어진 이진 탐색 트리에서 조건을 만족하는 노드는 총 5개입니다.
알고리즘 접근 방식
아래 프로그램에서 사용한 접근 방법은 다음과 같습니다.
- 데이터(data), 왼쪽 포인터(left), 오른쪽 포인터(right)를 가지는 노드 구조체를 생성하고, 탐색할 범위를 지정합니다.
- 사용자가 입력할 새 노드(new node)를 삽입하는 함수를 만듭니다.
- 주어진 범위에 속하는 노드의 개수를 계산하는 또 다른 함수를 만듭니다.
- 루트(root)가 NULL이라면 즉시 반환합니다.
- 루트->data가 Start와 End와 동일하다면 1을 반환합니다.
- 루트->data가 high 이하이고 low 이상이라면, 1 + getCount(root->left, ...) + 재귀 호출(getCount(root->right, ...))을 반환합니다.
- 그렇지 않고 루트->data가 End보다 작다면 오른쪽 자식에 대해 함수를 재귀 호출합니다.
- 그 외의 경우에는 왼쪽 자식에 대해 함수를 재귀 호출합니다.
C++ 구현 예제
#include<iostream>
using namespace std;
// BST 노드 구조체
struct node{
int data;
struct node* left, *right;
};
// 새 노드를 생성하는 유틸리티 함수
node *newNode(int data){
node *temp = new node;
temp->data = data;
temp->left = temp->right = NULL;
return (temp);
}
int findcount(node *root, int low, int high){
// 기저 사례(Base case)
if (!root){
return 0;
}
if (root->data == high && root->data == low){
return 1;
}
// 현재 노드가 범위 안에 있다면 카운트에 포함하고,
// 왼쪽·오른쪽 자식에 대해 재귀 호출
if (root->data <= high && root->data >= low){
return 1 + findcount(root->left, low, high) +
findcount(root->right, low, high);
}
else if (root->data < low){
return findcount(root->right, low, high);
}
// 그 외의 경우 왼쪽 자식에 대해 재귀 호출
else{
return findcount(root->left, low, high);
}
}
// 메인 함수
int main(){
// 위 그림에 나타난 BST를 구성
node *root = newNode(27);
root->left = newNode(14);
root->right = newNode(35);
root->left->left = newNode(10);
root->left->right = newNode(19);
root->right->left = newNode(31);
root->right->right = newNode(42);
int low = 10;
int high = 50;
cout << "Count of nodes between [" << low << ", " << high
<< "] is " << findcount(root, low, high);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
Count of nodes between [10, 50] is 7
동작 원리 요약
이 알고리즘은 BST의 정렬된 구조 특성을 활용해 탐색 범위를 효율적으로 좁혀 갑니다. 현재 노드의 값이 범위보다 작으면 왼쪽 서브트리는 볼 필요 없이 오른쪽만 탐색하고, 반대로 범위보다 크면 오른쪽 서브트리를 건너뛰고 왼쪽만 탐색합니다. 덕분에 일반적인 전체 순회(O(n))보다 평균적으로 더 적은 노드만 방문하게 되며, 균형 잡힌 BST에서는 O(log n)에 가까운 성능을 기대할 수 있습니다.