이진 탐색 트리(Binary Search Tree, BST)는 다음 세 가지 핵심 성질을 만족하는 이진 트리 자료구조입니다.
노드의 왼쪽 서브트리에는 해당 노드의 키보다 작은 키를 가진 노드만 존재해야 합니다.
노드의 오른쪽 서브트리에는 해당 노드의 키보다 큰 키를 가진 노드만 존재해야 합니다.
왼쪽과 오른쪽 서브트리 각각도 반드시 이진 탐색 트리여야 합니다.
BST 판별 알고리즘
가장 널리 사용되는 방법은 각 노드가 가질 수 있는 허용 범위(min, max)를 전달하며 재귀적으로 검증하는 것입니다. 루트부터 시작해 내려갈수록 범위를 점차 좁혀 나가며, 모든 노드가 자신의 범위 안에 속하는지 확인합니다.
시작
함수 BSTUtill() 정의
만약 노드가 NULL이라면
1을 반환한다. (빈 트리는 유효한 BST)
만약 노드의 데이터가 최솟값보다 작거나 최댓값보다 크다면
0을 반환한다. (BST 조건 위반)
왼쪽과 오른쪽 서브트리를 재귀적으로 순회하여 검증한다.
종료.C++ 예제 코드
#include <iostream>
#include <cstdlib>
#include <climits>
using namespace std;
// 트리 노드 구조체 정의
struct n {
int d;
n* l;
n* r;
};
int BSTUtil(n* node, int min, int max);
// 루트 노드에서 BST 검증 시작 (정수 전체 범위로 초기화)
int isBST(n* node) {
return(BSTUtil(node, INT_MIN, INT_MAX));
}
// 각 노드가 허용 범위 [min, max] 내에 있는지 재귀적으로 확인
int BSTUtil(struct n* node, int min, int max) {
if (node==NULL)
return 1;
if (node->d < min || node->d > max)
return 0;
return BSTUtil(node->l, min, node->d - 1) && BSTUtil(node->r, node->d + 1, max);
}
// 새 노드 생성 및 초기화
n* newN(int d) {
n* nod = new n;
nod->d = d;
nod->l = NULL;
nod->r = NULL;
return nod;
}
int main() {
// 첫 번째 트리: BST 조건을 만족하지 않는 경우
n *root = newN(7);
root->l = newN(6);
root->r = newN(10);
root->l->l = newN(2);
root->l->r = newN(4);
if (isBST(root))
cout<<"주어진 이진 트리는 BST입니다"<<endl;
else
cout<<"주어진 이진 트리는 BST가 아닙니다"<<endl;
// 두 번째 트리: BST 조건을 만족하는 경우
n *root1 = newN(10);
root1->l = newN(6);
root1->r = newN(11);
root1->l->l = newN(2);
root1->l->r = newN(7);
if (isBST(root1))
cout<<"주어진 이진 트리는 BST입니다"<<endl;
else
cout<<"주어진 이진 트리는 BST가 아닙니다"<<endl;
return 0;
}실행 결과
주어진 이진 트리는 BST가 아닙니다 주어진 이진 트리는 BST입니다
동작 원리와 시간 복잡도
첫 번째 트리에서 루트는 7이지만 왼쪽 자식이 6인 상태에서 그 아래 노드들이 범위 조건을 위반하게 되어 BST가 아니라고 판단됩니다. 반면 두 번째 트리는 모든 노드가 자신의 허용 범위를 만족하므로 올바른 BST로 인식됩니다.
이 알고리즘은 트리의 모든 노드를 한 번씩만 방문하므로 시간 복잡도는 O(n)이며, 재귀 호출 깊이만큼의 스택 공간을 사용하므로 공간 복잡도는 균형 잡힌 트리 기준 O(log n), 최악의 경우(편향 트리) O(n)입니다.