Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 이진 트리에서 가장 큰 BST(이진 탐색 트리) 찾기

이진 트리와 이진 탐색 트리(BST)의 개념

이진 트리(Binary Tree)는 각 노드가 최대 두 개의 자식 노드, 즉 왼쪽 자식과 오른쪽 자식만을 가질 수 있는 트리 구조입니다. 트리 구조는 데이터를 계층적으로 표현하는 대표적인 방법입니다. 그중에서도 이진 탐색 트리(Binary Search Tree, BST)는 다음 조건을 만족하는 특수한 형태의 이진 트리입니다.

  • 왼쪽 자식 노드는 항상 부모 노드보다 작은 값을 가집니다.

  • 오른쪽 자식 노드는 항상 부모 노드보다 큰 값을 가집니다.

문제 정의: 이진 트리에서 가장 큰 BST 찾기

하나의 이진 트리가 주어졌을 때, 그 안에서 가장 큰 이진 탐색 트리(BST)를 찾아야 합니다. 만약 주어진 이진 트리 전체가 BST라면 트리 전체의 노드 수가 곧 답이 되고, 그렇지 않다면 BST 조건을 만족하는 서브트리 중 가장 많은 노드를 가진 것의 크기를 반환해야 합니다.

입력 예시 1

      10
     /  \
    5    15
   / \     \
  1   8     7

위 트리에서 노드 5를 루트로 하는 서브트리({5, 1, 8})가 가장 큰 BST입니다. 서브트리의 크기는 '3'이므로 반환값은 3입니다.

입력 예시 2

        52
       /  \
      37    67
     /  \   /  \
    12   27 57   77
                 /  \
                72   87

출력

5

노드 52를 루트로 하는 전체 트리는 BST 조건을 만족하지 않습니다. 반면 노드 67을 루트로 하는 오른쪽 서브트리({67, 57, 77, 72, 87})는 BST 조건을 모두 충족하므로, 정답은 크기 5가 됩니다.

가장 큰 BST를 찾는 접근 방법

임의의 노드 x를 루트로 하는 이진 트리가 BST이기 위해서는 다음 조건들이 성립해야 합니다.

  • 노드의 왼쪽 서브트리에는 부모 노드보다 작은 값만 존재해야 합니다.

  • 노드의 오른쪽 서브트리에는 부모 노드보다 큰 값만 존재해야 합니다.

  • 왼쪽과 오른쪽 서브트리 각각도 이진 탐색 트리(BST)여야 합니다.

알고리즘

이진 트리의 루트에서 시작해 재귀적으로 순회를 진행합니다. 현재 노드 'ROOT'에 대해 다음과 같이 처리합니다.

  • 현재 노드를 루트로 하는 서브트리가 유효한 BST라면, 그 크기를 반환합니다.

  • 그렇지 않다면, 왼쪽 서브트리와 오른쪽 서브트리에서 각각 가장 큰 BST를 재귀적으로 찾아 더 큰 값을 반환합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    struct Node *left;
    struct Node *right;
};

struct Node *newNode(int data) {
    struct Node *node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return (node);
}

// 서브트리 정보를 저장하기 위한 구조체
struct Detail {
    int size;    // 서브트리의 크기
    int max;     // 서브트리의 최댓값
    int min;     // 서브트리의 최솟값
    int ans;     // 지금까지 찾은 가장 큰 BST의 크기
    bool isBST;  // 현재 서브트리가 BST인지 여부
};

// 주어진 범위(min ~ max) 안에서 해당 트리가 BST인지 확인
bool isBST(Node *root, int min, int max) {
    if (root == NULL) {
        return true;
    }
    if (root->data < min || root->data > max) {
        return false;
    }
    return isBST(root->left, min, root->data - 1) &&
           isBST(root->right, root->data + 1, max);
}

// 트리(서브트리)의 전체 노드 수를 계산
int size(Node *root) {
    if (root == NULL) {
        return 0;
    }
    return 1 + size(root->left) + size(root->right);
}

// 가장 큰 BST의 크기를 찾는 함수
int largestBST(Node *root) {
    // 현재 서브트리가 BST인 경우
    if (isBST(root, INT_MIN, INT_MAX) == true) {
        return size(root);
    }
    // 왼쪽과 오른쪽 서브트리에서 가장 큰 BST를 찾음
    return max(largestBST(root->left), largestBST(root->right));
}

int main() {
    struct Node *root = newNode(67);
    root->left = newNode(72);
    root->right = newNode(77);
    root->left->left = newNode(57);
    printf("Size of the largest BST is %d", largestBST(root));
    return 0;
}

실행 결과

Size of the largest BST is 2

예제 코드에서 루트(67)의 왼쪽 자식이 72로 루트보다 크기 때문에 전체 트리는 BST가 아닙니다. 하지만 노드 72와 그 왼쪽 자식 57로 이루어진 서브트리는 BST 조건을 만족하며 노드 수는 2개입니다. 따라서 가장 큰 BST의 크기인 2가 출력됩니다.

결론

이번 글에서는 이진 트리와 이진 탐색 트리(BST)의 개념을 살펴보고, 재귀를 활용해 주어진 이진 트리 안에서 가장 큰 BST의 크기를 찾는 방법을 알아보았습니다. 모든 노드를 재귀적으로 확인하면서 각 노드를 루트로 하는 서브트리가 BST인지 판별하고, 그 결과에 따라 적절한 크기를 반환함으로써 문제를 효율적으로 해결할 수 있습니다.