Pythonでn個のノードから構成できる二分探索木（BST）の数を求める方法

問題の概要

互いに異なるn個のノードが与えられたとき、それらを二分探索木（BST：Binary Search Tree）として配置する方法が何通りあるかを求めることを考えます。二分探索木には「左部分木には常に親より小さい値が、右部分木には常に親より大きい値が格納される」という重要な性質があります。

この問題を解くには、カタラン数（Catalan Number）を利用します。カタラン数 C(n) は、n個の異なるキーから構成できる二分探索木の総数を正確に表すことが知られています。計算式は次のとおりです。

$$C(n)=\frac{(2n)!}{(n+1)!\times n!}$$

例えば、入力が n = 3 の場合、出力は 5 になります。これは、3つのノードで作れる二分探索木の形状が5通り存在するためです。

アルゴリズムの手順

この問題は、以下の手順で解くことができます。

• 組み合わせの数を計算する関数 ncr() を定義します。引数は n と r です。
• 結果を格納する変数 res を 1 で初期化します。
• r > n − r の場合、r を n − r に置き換えます（対称性を利用して計算量を削減）。
• i を 0 から r−1 までループし、各回で res *= (n - i) を実行した後、res //= (i + 1) で割り切れるように更新します。
• res を返します。
• メイン処理では c = ncr(2 * n, n) を計算し、最後に c // (n + 1) を返します。

Pythonでの実装例

以下のコードで実際の動作を確認してみましょう。

from math import factorial

def ncr(n, r):
    res = 1
    if r > n - r:
        r = n - r

    for i in range(r):
        res *= (n - i)
        res //= (i + 1)

    return res

def solve(n):
    c = ncr(2 * n, n)
    return c // (n + 1)

n = 3
print(solve(n))

入力

3

出力

5

計算量について

この実装では、組み合わせの計算に O(min(r, n−r)) の時間がかかるため、全体の計算量は O(n) となります。階乗を直接計算して巨大な整数を扱う方法よりも、途中で割り算を行いながら値を小さく保つこの手法の方が、大きな n に対しても効率的に動作します。