PythonでnノードのBSTの数をカウントするプログラム

n個の異なるノードがあるとします。すべてが異なります。二分探索木を形成するためにそれらを配置できる方法の数を見つける必要があります。二分探索木で知っているように、左側のサブツリーは常に小さい値を保持し、右側のサブツリーは大きい値を保持します。

これを解決するために、カタラン数を見つけます。カタラン数C（n）は、n個の異なるキーを持つ二分探索木を表します。式は次のようになります

$$ C（n）=\ frac {（2n）！} {（n + 1）！\ times n！} $$

したがって、入力がn =3の場合、出力は5になります。

これを解決するには、次の手順に従います-

• 関数ncr（）を定義します。これにはn、rがかかります
• res：=1
• r> n --rの場合、
  • r：=n-r
• 0からr-1の範囲のiの場合、do
  • res：=res *（n --i）
  • res：=（res /（i + 1））のフロア
• return res
• メインの方法から、次の手順を実行します
• c：=ncr（2 * n、n）
• c /（n + 1）のリターンフロア

例

理解を深めるために、次の実装を見てみましょう-

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