C++で二分探索木（BST）の2つのノード間の最大要素を求める方法

問題文

N個の要素を持つ配列と、その配列に含まれる2つの整数 A、B が与えられます。まず、配列の要素 arr[0] から arr[n-1] を順番に挿入して二分探索木（BST：Binary Search Tree）を構築します。その上で、ノード A からノード B への経路上に存在する最大の要素を見つけることが本問題の目的です。

例

配列が {24, 23, 15, 36, 19, 41, 25, 35} の場合、構築されるBSTは次のようになります。

ここで A = 19、B = 41 とした場合、この2つのノード間の最大要素は 41 となります。

アルゴリズム

この問題は、BSTの性質を活かして最小共通祖先（LCA：Lowest Common Ancestor）を利用することで効率的に解くことができます。手順は以下の通りです。

• ノード A とノード B の最小共通祖先（LCA）を見つけます。
• LCA から A までの経路上の最大ノードを求めます（max1 とする）。
• LCA から B までの経路上の最大ノードを求めます（max2 とする）。
• max1 と max2 のうち大きい方を答えとして返します。

なぜLCAを使うのか

A から B への木の中の経路は、必ず「A → LCA → B」という形になります。そこで、A→LCA と LCA→B の2つの区間に分けてそれぞれの最大値を求めれば、経路全体の最大値が得られます。BSTでは値の大小関係によって進む方向が一意に決まるため、各区間の探索は木の高さ分のステップで完了します。

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;
}

出力

Maximum element = 41

計算量について

LCAの探索も、LCAから各ノードまでの経路上の最大値探索も、いずれも木の高さ h に比例するステップ数で完了します。したがって、全体の時間計算量は O(h) となります。バランスの取れたBSTであれば O(log N)、要素が片方向に偏り枝分かれしない最悪ケースでは O(N) になる点に注意してください。