ノードがn個の二分探索木の個数

math

1,2,...,nをノードに持つ二分探索木が何通りできるか考える.


n = 1のとき二分探索木の個数は1通り
n > 1のとき
根は1,2,...,nまでありうるから
異なるn個の値をノードに持つ二分探索木の個数をf(n)通りとすると
f(1) = 1
f(n) = 根が1の二分探索木の個数 + ... + 根がnの二分探索木の個数


根が1の二分探索木は

  • 左の子はない
  • 右の子は2,...,nをノードに持つ二分探索木の根がくっつく

根がnの二分探索木は

  • 左の子は1,...,n-1をノードに持つ二分探索木の根がくっつく
  • 右の子はない

根がr (1 < r < n)の二分探索木は

  • 左の子は1,...,r-1をノードに持つ二分探索木の根がくっつく.
  • 右の子はr+1,,...,nをノードに持つ二分探索木の根がくっつく.

よって
子がない場合もノードが0個の二分探索木がくっつくと見なしてf(0)=1とすれば
根がrの二分探索木はf(r-1)f(n-r)通りある.


したがって
f(1) = 1
f(n+1) = f(0)f(n)+f(1)f(n-1)+...+f(n)f(0) = Σ[r=0,n] f(r)f(n-r)


この漸化式はカタラン数の漸化式と同じであるから
1,2,...,nをノードに持つ二分探索木の個数は f(n) = \frac{1}{(n+1)} {{}_{2n} \mathrm{C}_n }