二分探索木のパターン数二分探索木とは、上の値より大きければ右に、小さければ左に子を作っていくツリー状のものです。例えば 6 ／＼ 4 9 ／＼／ 2 5 8 ／ 7 こんな感じです。 http://ja.wikipedia.org/wiki/%e4%ba%8c%e5%88%86%e6%9c%a8 で、問題なのですが、[1,2,3,4,5,6,7,8,9]といった9つの数値がある時、二分探索木は何通りできるか。というものです。図を書いて色々考えてみたのですが求め方が分かりません。全パターン書き出すのは量的に辛すぎますし、CやPで計算するのでしょうが、どのような式になるのでしょうか？

あれ？失礼しました。 http://blog.goo.ne.jp/osu_neko_runway09/e/aef7d70b705bb09778833f6e5396df59 こちらのURLならいかがでしょうか？

二分探索木のパターン数

解決済

質問者：areasd
質問日時：2010/08/12 22:22
回答数：4件

二分探索木のパターン数

二分探索木とは、上の値より大きければ右に、小さければ左に子を作っていくツリー状のものです。
例えば
　　　 6
　　／＼
　　4 　　　9
　／＼　／
　2 　5　8　
　　　／
　　 7
こんな感じです。
http://ja.wikipedia.org/wiki/%e4%ba%8c%e5%88%86% …

で、問題なのですが、[1,2,3,4,5,6,7,8,9]といった9つの数値がある時、二分探索木は何通りできるか。
というものです。図を書いて色々考えてみたのですが求め方が分かりません。
全パターン書き出すのは量的に辛すぎますし、CやPで計算するのでしょうが、どのような式になるのでしょうか？

通報する

この質問への回答は締め切られました。

質問の本文を隠す

回答 (4件)

ベストアンサー優先
最新から表示
回答順に表示

No.3ベストアンサー

回答者： osu_neko09
回答日時：2010/08/15 20:12

あれ？失礼しました。

http://blog.goo.ne.jp/osu_neko_runway09/e/aef7d7 …
こちらのURLならいかがでしょうか？

- 0
- 件

通報する

この回答へのお礼

ありがとうございます見れました。詳しく書いて下さりありがとうございます。
すごく計算ややこしいですね。やはり2分探索木の場合はカタラン数の(2n)!/((n+1)!n!)では駄目なんですね

通報する

お礼日時：2010/08/17 00:31

No.4

回答者： osu_neko09
回答日時：2010/08/17 05:48

＞2分探索木の場合はカタラン数の(2n)!/((n+1)!n!)？

n=3のとき、6!/4!3!=5で、形だけなら5通りですが、
以下の二分木を全て異なるものとして扱うと、5通りより多くなります。
　　　1　　　　　　　　2　　　　　　　　3　　　　　
　　／＼　　　　　／＼　　　　　／＼　　　
　　2　　　3　　　　1　　　3　　　　1　　　2　　
　　　　　　　　
　　　2　　　　　　　2
　　／　　　　　　　＼
　　1　　　　　　　　　　3
　　＼　　　　　　　／
　　　　3　　　　　　 1

　　1　　　　　　　　1
　　＼　　　　　　　＼
　　　　2　　　　　　　　3
　　　　＼　　　　　／
　　　　　　3　　　　2

　　　　　　3　　　　 3
　　　　／　　　　　／
　　　　2　　　　　　1
　　／　　　　　　　＼
　　1　　　　　　　　　　2