이진 트리(Binary Tree)는 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리 자료구조입니다. 두 자식 노드는 각각 왼쪽 자식(left child)과 오른쪽 자식(right child)라고 부릅니다.
BST(이진 탐색 트리, Binary Search Tree)는 왼쪽 서브트리에는 루트보다 작은 값을 가진 노드들이, 오른쪽 서브트리에는 루트보다 큰 값을 가진 노드들이 위치하는 트리 구조입니다. 이러한 정렬 특성 덕분에 탐색·삽입·삭제 연산을 평균적으로 O(log n)의 시간 복잡도로 빠르게 처리할 수 있습니다.
이진 트리가 BST인지 확인하는 방법
주어진 이진 트리가 BST인지 판별하려면 트리 전체에 대해 BST 조건을 검사해야 합니다. 자식 노드가 존재하는 모든 노드에서 다음 조건을 만족해야 합니다.
- 왼쪽 자식의 값은 부모 노드의 값보다 작아야 합니다.
- 오른쪽 자식의 값은 부모 노드의 값보다 커야 합니다.
- 모든 서브트리 역시 동일한 조건을 만족하는 BST여야 합니다.
주의할 점은 단순히 부모와 자식 노드만 비교해서는 안 된다는 것입니다. 각 노드가 가질 수 있는 값의 허용 범위(min, max)를 함께 추적하며 검사해야 올바르게 판별할 수 있습니다.
이진 트리가 BST인지 확인하는 프로그램
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
class node {
public:
int data;
node* left;
node* right;
node(int data) {
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
int isBSTUtil(node* node, int min, int max);
int isBST(node* node) {
return(isBSTUtil(node, INT_MIN, INT_MAX));
}
int isBSTUtil(node* node, int min, int max) {
if (node==NULL)
return 1;
if (node->data < min || node->data > max)
return 0;
return
isBSTUtil(node->left, min, node->data-1) && isBSTUtil(node->right, node->data+1, max);
}
int main() {
node *root = new node(8);
root->left = new node(3);
root->right = new node(10);
root->left->left = new node(1);
root->left->right = new node(6);
if(isBST(root))
cout<<"The given tree is a BST";
else
cout<<"The given tree is Not a BST";
return 0;
}출력 결과
The given tree is a BST
코드 설명
위 코드는 주어진 트리가 BST인지 검사합니다. main 함수에서 예제 트리를 생성한 뒤 isBST() 함수를 호출하고, 이 함수는 isBSTUtil()을 통해 왼쪽·오른쪽 자식이 BST 규칙을 따르는지, 그리고 만들어지는 모든 서브트리 역시 BST인지 재귀적으로 확인합니다.
isBST()는 루트 노드와 함께 INT_MIN부터 INT_MAX까지의 초기 허용 범위를 isBSTUtil()에 전달합니다. isBSTUtil()은 재귀 호출마다 왼쪽 서브트리에는 현재 노드 값보다 작은 값만, 오른쪽 서브트리에는 큰 값만 존재할 수 있도록 범위를 좁혀 나갑니다. 노드가 NULL이면 유효한 경우로 보고 1을 반환하며, 어떤 노드라도 허용 범위를 벗어나면 0을 반환해 BST가 아님을 알립니다. 이 알고리즘은 모든 노드를 한 번씩 방문하므로 시간 복잡도는 O(n)입니다.