이 글에서는 하나의 이진 트리(Binary Tree)가 주어졌을 때, 그 안에서 가장 큰 BST(이진 탐색 트리) 하위 트리를 찾는 방법을 다룹니다.
이진 트리는 데이터 저장을 위해 널리 사용되는 대표적인 자료구조로, 각 노드가 최대 두 개의 자식 노드만 가질 수 있다는 특수한 조건을 만족해야 합니다.
이진 탐색 트리(Binary Search Tree, BST)는 모든 노드가 아래 속성을 만족하는 트리입니다.
- 왼쪽 하위 트리의 키 값은 항상 부모(루트) 노드의 키 값보다 작아야 합니다.
- 오른쪽 하위 트리의 키 값은 항상 부모(루트) 노드의 키 값보다 크거나 같아야 합니다.
예제를 통해 문제를 살펴보겠습니다.
입력 :
출력 : 3
설명
전체 이진 트리가 BST입니다.
접근 방식 1: 중위 순회(In-order Traversal) 활용
가장 직관적인 해결 방법은 트리를 중위 순회하면서 각 노드를 기준으로 해당 하위 트리가 BST인지 검사하는 것입니다. 모든 노드에 대한 검사가 끝나면, BST 조건을 만족하는 하위 트리 중 가장 큰 것의 크기를 반환합니다. 이 방법은 구현이 간단하다는 장점이 있지만, 각 노드마다 하위 트리 전체를 다시 검사해야 하므로 최악의 경우 O(n²)의 시간 복잡도를 가질 수 있습니다.
구현 예제
#include<bits/stdc++.h>
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 findTreeSize(node* node) {
if (node == NULL)
return 0;
else
return(findTreeSize(node->left) + findTreeSize(node->right) + 1);
}
int isBSTree(struct node* node) {
if (node == NULL)
return 1;
if (node->left != NULL && node->left->data > node->data)
return 0;
if (node->right != NULL && node->right->data < node->data)
return 0;
if (!isBSTree(node->left) || !isBSTree(node->right))
return 0;
return 1;
}
int findlargestBSTSize(struct node *root) {
if (isBSTree(root)){
return findTreeSize(root);
}
else
return max(findlargestBSTSize(root->left), findlargestBSTSize(root->right));
}
int main() {
node *root = new node(5);
root->left = new node(2);
root->right = new node(8);
root->left->left = new node(1);
root->left->right = new node(4);
cout<<"The size of the largest possible BST is "<<findlargestBSTSize(root);
return 0;
}
출력
The size of the largest possible BST is 5
접근 방식 2: 상향식(Bottom-up) 탐색 활용
두 번째 방법은 트리를 아래에서 위로(bottom-up) 순회하면서 자식 노드들의 정보를 활용해 현재 노드까지가 BST인지 한 번의 순회로 판단하는 방식입니다. 이를 위해 각 노드마다 다음 정보를 추적합니다.
- 현재 노드를 루트로 하는 트리가 BST인지 여부
- 왼쪽 하위 트리의 최댓값
- 오른쪽 하위 트리의 최솟값 — 이 값들은 BST 검사 시 현재 노드의 값과 비교됩니다.
동시에 현재까지 발견된 BST의 크기와 비교하여 최대 BST 크기를 지속적으로 갱신합니다. 이 방식은 트리를 한 번만 순회하면 되므로 O(n)의 시간 복잡도로 동작하며, 첫 번째 방법보다 효율적입니다.
구현 예제
#include<bits/stdc++.h>
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 findlargestBSTSizeRec(node* node, int *minValRsubTree, int *maxValLsubTree, int *maxBSTSize, bool *isBSTree) {
if (node == NULL){
*isBSTree = true;
return 0;
}
int min = INT_MAX;
bool left_flag = false;
bool right_flag = false;
int leftSubtreeSize,rightSubTreeSize;
*maxValLsubTree = INT_MIN;
leftSubtreeSize = findlargestBSTSizeRec(node->left, minValRsubTree, maxValLsubTree, maxBSTSize, isBSTree);
if (*isBSTree == true && node->data > *maxValLsubTree)
left_flag = true;
min = *minValRsubTree;
*minValRsubTree = INT_MAX;
rightSubTreeSize = findlargestBSTSizeRec(node->right, minValRsubTree, maxValLsubTree, maxBSTSize, isBSTree);
if (*isBSTree == true && node->data < *minValRsubTree)
right_flag = true;
if (min < *minValRsubTree)
*minValRsubTree = min;
if (node->data < *minValRsubTree)
*minValRsubTree = node->data;
if (node->data > *maxValLsubTree)
*maxValLsubTree = node->data;
if(left_flag && right_flag){
if (leftSubtreeSize + rightSubTreeSize + 1 > *maxBSTSize)
*maxBSTSize = (leftSubtreeSize + rightSubTreeSize + 1);
return (leftSubtreeSize + rightSubTreeSize + 1);
}
else{
*isBSTree = false;
return 0;
}
}
int findlargestBSTSize(node* node){
int min = INT_MAX;
int max = INT_MIN;
int largestBSTSize = 0;
bool isBST = false;
findlargestBSTSizeRec(node, &min, &max, &largestBSTSize, &isBST);
return largestBSTSize;
}
int main(){
node *root = new node(5);
root->left = new node(2);
root->right = new node(8);
root->left->left = new node(1);
root->left->right = new node(4);
cout<<"The Size of the largest BST is "<<findlargestBSTSize(root);
return 0;
}
출력
The Size of the largest BST is 5