C++로 이진 트리 안에 존재하는 이진 탐색 트리(BST) 개수 구하기

이진 트리가 입력으로 주어졌을 때, 그 트리 내부에서 서브트리(subtree) 형태로 존재하는 이진 탐색 트리(Binary Search Tree, BST)의 개수를 찾는 것이 목표입니다. BST란 왼쪽 자식 노드의 값이 루트보다 작고, 오른쪽 자식 노드의 값이 루트보다 큰 규칙을 만족하는 이진 트리를 말합니다.

예제 1

입력

입력된 값들로 생성되는 트리는 아래와 같습니다.

출력

Count the Number of Binary Search Trees present in a Binary Tree are: 2

설명

정수 값 배열을 사용해 이진 트리를 구성한 뒤, 그 안에 BST가 존재하는지 확인합니다. 모든 리프(leaf) 노드는 스스로 하나의 BST가 되므로, 위 트리에서는 그 외에 별도의 BST 서브트리가 없습니다. 따라서 개수는 리프 노드의 총 개수인 2가 됩니다.

예제 2

입력

입력된 값들로 생성되는 트리는 아래와 같습니다.

C++로 이진 트리 안에 존재하는 이진 탐색 트리(BST) 개수 구하기

출력

Count the Number of Binary Search Trees present in a Binary Tree are: 6

설명

이 트리에는 리프 노드가 4개 있고, 추가로 BST 조건을 만족하는 서브트리가 2개 존재합니다. 따라서 전체 BST 개수는 6입니다.

C++로 이진 트리 안에 존재하는 이진 탐색 트리(BST) 개수 구하기

접근 방법

이 문제는 상향식(bottom-up) 순회를 활용해 해결할 수 있습니다. 각 노드 N에 대해 왼쪽 서브트리의 최댓값이 N보다 작은지, 오른쪽 서브트리의 최솟값이 N보다 큰지를 검사합니다. 두 조건이 모두 참이면 해당 서브트리는 BST입니다. 트리를 아래에서 위로 순회하며 이 조건을 확인하고, BST인 경우마다 카운트를 증가시킵니다.

각 노드의 정보(node_data)에는 해당 서브트리에 포함된 BST의 개수, 서브트리의 최댓값, 최솟값, 그리고 해당 서브트리가 BST인지 여부를 나타내는 불리언 값이 저장됩니다.
함수 BST_present(struct tree_node* parent)는 parent를 루트로 하는 이진 트리 안에 존재하는 BST의 개수를 반환합니다.
parent가 NULL이면 { 0, min, max, true }를 반환합니다. 이때 min은 INT_MIN, max는 INT_MAX입니다.
왼쪽과 오른쪽 자식이 모두 NULL이면 { 1, parent->data, parent->data, true }를 반환합니다.
node_data Left = BST_present(parent->left);와 node_data Right = BST_present(parent->right);로 왼쪽·오른쪽 결과를 얻습니다.
노드 n1의 최솟값을 n1.lowest = min(parent->data, min(Left.lowest, Right.lowest))로 설정합니다.
n1의 최댓값을 n1.highest = max(parent->data, max(Left.highest, Right.highest))로 설정합니다.
Left.check && Right.check && parent->data > Left.highest && parent->data < Right.lowest가 참이면 n1.check = true로 설정하여 해당 서브트리가 BST임을 표시합니다.
BST인 경우 개수를 n1.total_bst = 1 + Left.total_bst + Right.total_bst;로 증가시킵니다.
그렇지 않으면 n1.check = false로 설정하고, 개수는 n1.total_bst = Left.total_bst + Right.total_bst;로 계산합니다.
마지막으로 n1을 반환합니다.

C++ 코드 예제

#include <bits/stdc++.h>
using namespace std;
struct tree_node{
    struct tree_node* left;
    struct tree_node* right;
    int data;
    tree_node(int data){
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};
struct node_data{
    int total_bst;
    int highest, lowest;
    bool check;
};
node_data BST_present(struct tree_node* parent){
    if(parent == NULL){
        int max = INT_MAX;
        int min = INT_MIN;
        return { 0, min, max, true };
    }
    if(parent->left == NULL){
        if(parent->right == NULL){
            return { 1, parent->data, parent->data, true };
        }
    }
    node_data Left = BST_present(parent->left);
    node_data Right = BST_present(parent->right);
    node_data n1;
    n1.lowest = min(parent->data, (min(Left.lowest, Right.lowest)));
    n1.highest = max(parent->data, (max(Left.highest, Right.highest)));
    if(Left.check && Right.check && parent->data > Left.highest && parent->data < Right.lowest){
        n1.check = true;
        n1.total_bst = 1 + Left.total_bst + Right.total_bst;
    } else{
        n1.check = false;
        n1.total_bst = Left.total_bst + Right.total_bst;
    }
    return n1;
}
int main(){
    struct tree_node* root = new tree_node(3);
    root->left = new tree_node(7);
    root->right = new tree_node(4);
    root->left->left = new tree_node(5);
    root->right->right = new tree_node(1);
    root->left->left->left = new tree_node(10);
    cout<<"Count the Number of Binary Search Trees present in a Binary Tree are: "<<BST_present(root).total_bst;
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

Count the Number of Binary Search Trees present in a Binary Tree are: 2