C++로 BST에서 두 노드 사이의 최댓값 구하기

문제 정의

N개의 원소를 가진 배열과, 해당 배열에 속한 두 개의 정수 A, B가 주어집니다. arr[0]부터 arr[n-1]까지의 원소를 순서대로 삽입하여 이진 탐색 트리(Binary Search Tree, BST)를 만들고, A에서 B로 가는 경로상에 존재하는 원소 중 최댓값을 찾는 것이 과제입니다.

예시

배열이 {24, 23, 15, 36, 19, 41, 25, 35}라고 가정하면, 다음과 같은 BST를 만들 수 있습니다.

여기서 A = 19, B = 41이라고 하면, 이 두 노드 사이 경로에서 최댓값은 41입니다.

알고리즘

이 문제는 최소 공통 조상(Lowest Common Ancestor, LCA)을 활용하면 효율적으로 해결할 수 있습니다.

노드 A와 노드 B의 최소 공통 조상(LCA)을 찾습니다.
LCA부터 A까지의 경로에서 최댓값을 구합니다. 이 값을 max1이라고 합니다.
LCA부터 B까지의 경로에서 최댓값을 구합니다. 이 값을 max2라고 합니다.
max1과 max2 중 더 큰 값을 반환합니다.

BST의 특성상 LCA를 찾는 과정은 루트에서 시작해 두 값이 모두 현재 노드보다 작으면 왼쪽으로, 모두 크면 오른쪽으로 이동하면 되므로 O(h) 시간 안에 처리할 수 있습니다. 여기서 h는 트리의 높이입니다.

구현 예제

이제 실제 C++ 코드로 살펴보겠습니다.

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

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

node *createNode(int x) {
    node *p = new node();
    p -> data = x;
    p -> left = NULL;
    p -> right = NULL;
    return p;
}

void insertNode(struct node *root, int x) {
    node *p = root, *q = NULL;
    while (p != NULL) {
        q = p;
        if (p -> data < x) {
            p = p -> right;
        } else {
            p = p -> left;
        }
    }
    if (q == NULL) {
        p = createNode(x);
    } else {
        if (q -> data < x) {
            q -> right = createNode(x);
        } else {
            q -> left = createNode(x);
        }
    }
}

int maxelpath(node *q, int x) {
    node *p = q;
    int mx = INT_MIN;
    while (p -> data != x) {
        if (p -> data > x) {
            mx = max(mx, p -> data);
            p = p -> left;
        } else {
            mx = max(mx, p -> data);
            p = p -> right;
        }
    }
    return max(mx, x);
}

int getMaximumElement(struct node *root, int x, int y) {
    node *p = root;
    while ((x < p -> data && y < p -> data) ||
           (x > p -> data && y > p -> data)) {
        if (x < p -> data && y < p -> data) {
            p = p -> left;
        } else if (x > p -> data && y > p -> data) {
            p = p -> right;
        }
    }
    return max(maxelpath(p, x), maxelpath(p, y));
}

int main() {
    int arr[] = {24, 23, 15, 36, 19, 41, 25, 35};
    int a = 19, b = 41;
    int n = sizeof(arr) / sizeof(arr[0]);
    struct node *root = createNode(arr[0]);
    for (int i = 1; i < n; i++) insertNode(root, arr[i]);
    cout << "Maximum element = " << getMaximumElement(root, a, b) << endl;
    return 0;
}

코드 설명

createNode: 새로운 트리 노드를 생성하고 초기화하는 함수입니다.
insertNode: BST의 규칙(왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큼)에 따라 새 원소를 삽입합니다.
maxelpath: 주어진 노드 q에서 값 x를 가진 노드까지 이동하면서 지나가는 노드들의 최댓값을 계산합니다.
getMaximumElement: 루트부터 탐색하여 A와 B의 LCA를 찾은 뒤, LCA에서 각각 A와 B까지의 경로 최댓값 중 더 큰 값을 반환합니다.

실행 결과

Maximum element = 41

복잡도 분석

시간 복잡도: LCA 탐색과 각 경로의 최댓값 계산 모두 트리의 높이에 비례하므로 O(h)입니다. 균형 잡힌 BST라면 O(log N), 최악의 경우(편향 트리)에는 O(N)입니다.
공간 복잡도: 추가적인 자료구조 없이 포인터만 사용하므로 O(1)입니다.