이진 탐색 트리(Binary Search Tree, BST)는 다음 세 가지 조건을 만족하는 이진 트리 자료구조입니다.
노드의 왼쪽 서브트리에는 그 노드의 키보다 작은 키를 가진 노드만 포함됩니다.
노드의 오른쪽 서브트리에는 그 노드의 키보다 큰 키를 가진 노드만 포함됩니다.
왼쪽 서브트리와 오른쪽 서브트리 역시 각각 이진 탐색 트리의 조건을 만족해야 합니다.
확인 알고리즘
이 문제는 각 노드가 가질 수 있는 값의 허용 범위(최솟값~최댓값)를 전달하면서 트리를 재귀적으로 순회하는 방식으로 해결할 수 있습니다.
- BSTUtil 함수에 현재 노드와 허용 범위(min, max)를 전달합니다.
- 노드가 NULL이면 더 이상 확인할 노드가 없으므로 1(유효함)을 반환합니다.
- 노드의 데이터가 최솟값보다 작거나 최댓값보다 크면 BST 조건을 위반한 것이므로 0을 반환합니다.
- 왼쪽 서브트리로 내려갈 때는 max를 (노드 값 − 1)로, 오른쪽 서브트리로 내려갈 때는 min을 (노드 값 + 1)로 좁혀가며 재귀적으로 탐색합니다.
예제 코드
#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);
int isBST(n* node) {
return(BSTUtil(node, INT_MIN, INT_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() {
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;
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입니다. 그런데 노드 6의 오른쪽 자식이 4인데, 4는 6보다 작습니다. “오른쪽 서브트리에는 더 큰 키만 있어야 한다”는 규칙을 위반했기 때문에 첫 번째 트리는 BST가 아닙니다.
반면 두 번째 트리는 루트 10을 기준으로 왼쪽 서브트리(6, 2, 7)의 모든 값이 10보다 작고, 오른쪽 서브트리(11)는 10보다 큽니다. 또한 노드 6의 자식들도 왼쪽(2)은 작고 오른쪽(7)은 커서 모든 조건을 만족합니다. 따라서 두 번째 트리는 BST입니다.
이 방식은 각 노드를 한 번씩만 방문하므로 시간 복잡도는 O(n)이며, 재귀 호출 깊이는 트리의 높이에 비례하므로 공간 복잡도는 O(h)(h는 트리의 높이)입니다.