3

この質問によると、特定のサイズの異なる探索木の数はカタラン数に等しくなります。それらの木を列挙することは可能ですか？つまり、誰かが次の2つの機能を実装できますか。

Node* id2tree(int id); // return root of tree

int  tree2id(Node* root); // return id of tree

（ツリーのバイナリコード（この質問に対する答えの1つ）は、範囲が不明な任意の大きな整数を表すための非常に効率的なコード、つまり整数の可変長コードになるため、私は尋ねます 

0 -> 0
1 -> 100
2 -> 11000
3 -> 10100
4 -> 1110000
5 -> 1101000
6 -> 1100100
7 -> 1011000
8 -> 1010100
etc

各コード長の整数の数が1、1、2、5、..（カタラン数列）であることに注意してください。）。

4

2 に答える 2

2

IDをツリーに変換して元に戻すことができるはずです。

ID とビット文字列は次のとおりです。

0 -> 0 
1 -> 100 
2 -> 11000 
3 -> 10100 
4 -> 1110000 
5 -> 1101000 
6 -> 1100100 
7 -> 1011000 
8 -> 1010100

最初に、ビット文字列が与えられると、ツリーに簡単に移動でき (再帰的な方法)、その逆も可能であるという事実を考慮してください (事前注文、親に 1 を出力し、葉に 0 を出力します)。

主な課題は、ID をビット文字列に、またはその逆にマップしようとすることです。

次のように n ノードのツリーをリストしたとします。

Left sub-tree n-1 nodes, Right sub-tree 0 nodes. (Cn-1*C0 of them)
Left sub-tree n-2 nodes, Right sub-tree 1 node.  (Cn-2*C1 of them)
Left sub-tree n-3 nodes, right sub-tree 2 nodes. (Cn-3*C2 of them)
...
...
Left sub-tree 0 nodes, Right sub-tree n-1 nodes. (C0*Cn-1 of them)

Cr = rth catalan number.

あなたが与えた列挙は、次の手順から来ているようです。左のサブツリーを固定し、右のサブツリーを列挙します。次に、次の左のサブツリーに移動し、右のサブツリーを列挙します。最大サイズの左サブツリーから始めて、次は最大サイズ -1 などです。

id = S があるとします。まず、次のような n を見つけます。

C0 + C1 + C2 + ... + Cn < S <= C0+C1+ C2 + ... +Cn+1

その場合、S は n+1 個のノードを持つツリーに対応します。

ここで、P = S - (C0+C1+C2+ ...+Cn) を考えます。これは、n+1 ノードのツリーの列挙における位置です。

ここで、Cn*C0 + Cn-1*C1 + .. + Cn-r Cr < P <= Cn C0 + Cn-1*C1 + .. + Cn-r+1*Cr-1 となるような r を計算します。

これは、左側のサブツリーと右側のサブツリーが持つノードの数を示しています。

P - Cn*C0 + Cn-1*C1 + .. + Cn-r*Cr を考慮すると、正確な左サブツリー列挙位置 (そのサイズのツリーのみを考慮する) と正確な右サブツリー列挙位置を再帰的に計算できます。ビット文字列を形成します。

左側のサブツリーと右側のサブツリーがどのように見えるかを知っているので、ビット文字列を ID にマッピングする方法は似ているはずです。必要なのは、対応する位置を見つけて、ID を取得するための計算を行うことだけです。

ただし、それがどれほど役立つかはわかりません。あなたは常にかなり膨大な数を扱うことになります。

于 2010-02-16T00:23:35.317 に答える
0

一般的な (非検索) バイナリ ツリーの場合、ツリーを構築するときに、ノードごとに 3 つの選択肢 (子の量) があり、合計が正確に N に達することによってのみ制限されるため、これがどのように可能になるかがわかります。そのようなツリーを選択のシーケンスとして (特定の順序でツリーを構築することによって) 表現する方法を見つけ、そのシーケンスを 3 進数 (または、可変ベースの方がより適切であろう) として表現します。

しかし、二分探索木の場合、すべての要素の編成が受け入れられるわけではありません。数値順序の制約にも従う必要があります。一方、二分探索木への挿入は明確に定義されているため、N 個の数値のリストを特定の挿入順序で持つことにより、N 個の要素のツリー全体を表すことができます。数値を別の順序に並べ替えることで、別のツリーを生成できます。

もちろん、順列は可変基数を使用して簡単にカウントできます。最初の項目には N 個の選択肢があり、2 番目の項目には N-1 などがあります。 N から 1 へ。可変基数から 2 進数または 10 進数へのエンコードとデコードは、通常の固定基数変換アルゴリズムから自明に適応されます。(剰余演算と除算演算を使用するもの)。

したがって、数値を順列との間で変換したり、数値のリストを指定して、(そのリストの) 順列を二分探索木との間で変換したりできます。これで、整数 1 から N だけを並べ替えることで、サイズ N の可能なすべての二分探索木を取得できると思いますが、完全には確信が持てず、この投稿には少し多すぎることを証明しようとしています。

これが議論の良い出発点になることを願っています。

于 2009-09-27T11:59:04.330 に答える