21

これはしばらくの間私を悩ませてきました。二分探索木の形で配置するN個のキーが与えられた場合、作成できるツリーの可能な数は、カタラン数列のN番目の数に対応することを知っています。

私はこれがなぜであるかを決定しようとしてきました。それを直感的に説明しようとするかもしれないものを見つけることができない私はSOの集合的な知識に頼ります。可能な木の数を計算する他の方法を見つけましたが、それらは直感的ではないようで、使用方法以外の説明はありませんでした。さらに、wikiページ（上記のリンク）には、3つのキーを使用して可能な樹木形成の画像も表示されます。これにより、適切でわかりやすい説明が聞こえると思います（言うまでもなく、記事には含まれていません）。 ）。

前もって感謝します！

4

4 に答える 4

14

あなたが参照したウィキペディアの記事には4つの証明があるので、カタロニア語の数と二分木の順列との対応についての数学的な説明を探していないようです。

代わりに、カタロニア語のシーケンス (1、2、5、14、42、...) が組み合わせシステムでどのように発生するかを直感的に視覚化する 2 つの方法を次に示します。

多角形を三角形にさいの目に切る

辺Nの多角形の場合、多角形を完全に三角形に切り刻む頂点間にカットを描く方法は何通りありますか?

  • 三角形 (N=3): 1 (既に三角形です)
  • 正方形 (N=4): 2 (どちらの対角線でもスライス可能)
  • 五角形 (N=5): 5 (頂点から発する 2 つのスライス ライン。5 つの頂点から選択)
  • 六角形 (N=6): 14 (描いてみてください)
  • ...等々。

対角線を交差せずにグリッドを通るパスを描く

この場合、一意のパスの数はカタロニア語数です。

2x2 グリッド => 2 つのパス

  _|       |
_|       __|

3x3 グリッド => 5 つのパス

    _|       |       _|         |         |
  _|      _ _|      |          _|         |
_|      _|       _ _|      _ _|      _ _ _|

4x4 グリッド => 14 パス
5x5 グリッド => 42 パス

等々。

与えられた N に対して可能な二分木を描いてみると、木の順列がまったく同じであることがわかります。

ツリーとシーケンスの間の対応を盲目的に受け入れないというあなたの願望は立派です。残念ながら、二項数学を使わずに、この議論をさらに進めること (そして、カタロニア語の公式がそのようになる理由を説明すること) は困難です。組み合わせ論(順列のカウントを含む) 自体をより深く理解したい場合は、ウィキペディアの二項係数に関する議論が良い出発点になります。

于 2009-08-30T12:49:42.570 に答える
7

カタロニア語 http://www.nohre.se/publicImages/catalan.png

任意の二分探索木は、すべてのノードを事前順序付けしてアクセスし、すべての親に対して 1 を、すべての葉に対して 0 をエンコードすることによってエンコードできます。ツリーに n 個の親がある場合、n+1 個の葉があり、その結果、バイナリ コードには n 個の 1:s と (n+1) 個の 0:s があります。さらに、コードのプレフィックスには、少なくとも 0: と同じ数の 1: があります。したがって、可能なツリーの数は、対角線より下のパスの数に等しくなります。

于 2009-09-27T10:50:15.017 に答える
2

さて、ここに木を数える再帰的な解決策があります...

int countTrees(int numkeys){

if(numkeys > 1){
    int i =1;
    int sum=0;

    for(i = 1; i <= numkeys; i++){

        int lcount = countTrees(i-1);
        int rcount = countTrees(numkeys-i);
        sum += lcount*rcount;
    }
    return(sum);
}else
    return(1);
}
于 2010-01-10T03:11:00.940 に答える
0

なぜそれがたまたまカタロニア語の数なのかを知りたいという同じ欲求があります。今のところカタロニア語の数は忘れて、n ノードの一意のバイナリ ツリーの数を計算する式を見つけてください。

C(n) を、与えられた n 個の頂点を持つ可能な二分木の数、C(0) = 1 とすると、n > 0 の場合の C(n) を考えます。 n – 1 個の頂点を持つルート ノードの左右の子の両方で生成できるバイナリ ツリーの数になります。

答えを見つけるには、両側で考えられるすべてのツリーを列挙する必要があります。

C(n) = C(0) * C(n - 1) + C(1) * C(n - 2) + ... + C(n – 2) * C(1) + C(n - 1 ) * C(0)

ここに画像の説明を入力

これがカタロニア数の再帰形式です。ウィキペディアで式の代わりにこの再帰形式を見れば、それを受け入れるのは簡単です。

( https://coldfunction.com/mgen/p/3rからのテキストのほとんど)

于 2021-01-02T04:01:58.213 に答える