二分探索木のパターン数
二分探索木とは、上の値より大きければ右に、小さければ左に子を作っていくツリー状のものです。
例えば
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で計算するのでしょうが、どのような式になるのでしょうか?
No.3ベストアンサー
- 回答日時:
ありがとうございます見れました。詳しく書いて下さりありがとうございます。
すごく計算ややこしいですね。やはり2分探索木の場合はカタラン数の(2n)!/((n+1)!n!)では駄目なんですね
No.4
- 回答日時:
>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
No.2
- 回答日時:
式はわからないですけれども、24,811,920とおりだと思われます。
計算結果はこちらに上げました。
http://blog.goo.ne.jp/admin/editentry?eid=aef7d7 …
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- C言語・C++・C# c言語の問題です 3 2023/01/10 16:15
- C言語・C++・C# C言語プログラム変更 2 2022/12/21 15:03
- 数学 特定の座標点を通る回帰を行う方法について。 2 2022/10/10 10:27
- 計算機科学 判定問題がPに属するなら探索問題はNPに属する。では判定問題がNPに属するとき探索問題は? 2 2023/05/20 19:10
- 数学 コインを投げて特定のパターンが出現する確率 5 2022/07/31 09:06
- K-POP 乃木坂46のことで3点質問です。 1 2022/10/06 11:00
- Instagram インスタで見かけた場所に行きたいのですがざっくりした(○○県)しか分かりません。他の方が何処かを尋ね 3 2022/12/03 19:22
- 数学 円周角の定理の証明では三つのパターンに分けて示す必要があるらしいのですが、一つのパターンでは不十分な 7 2023/06/28 08:58
- 邦楽 思い出せない歌のタイトル/歌詞について 質問が埋もれてしまったので二度目失礼します 学生時代(かなり 1 2022/04/08 23:21
- ホテル・旅館 ビジネスホテルのエアコンについて 先日1拍で新宿のビジネスホテルにアゴダサイトから泊まりました エア 4 2022/08/03 17:55
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
30パーセントオフで371円だった...
-
eのマイナス無限大乗
-
分数の計算で分子が0になったら...
-
中学生の数学を習う順番に並べ...
-
計算の問題を解いていただきた...
-
∫1/lnxdx について
-
映画を1.3倍速で見た時の時間計...
-
体積凹 理解しない 頭掻きむしる
-
2割負担の計算。
-
(-π,π)上で次の関数のフーリ...
-
ポパイの計算って?
-
n乗根計算でn値を逆算するには
-
楕円の円周の長さの計算の仕方...
-
ADHDだから
-
因数分解の問題が解けなくて、...
-
エクセルで休息時間計算したい
-
(x^2-x+1)^10の展開式におけるx...
-
公共工事の現場管理費率(%)...
-
正弦定理・余弦定理の問題
-
線形代数 線形従属の問題
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
30パーセントオフで371円だった...
-
公共工事の現場管理費率(%)...
-
「割る」と「割りかえす」の違い
-
eのマイナス無限大乗
-
中学生の数学を習う順番に並べ...
-
10進法で時間の計算で30分が0.5...
-
楕円の円周の長さの計算の仕方...
-
計算手順について
-
袋のサイズから容量を計算する方法
-
面積から辺の長さを出す計算式
-
2割負担の計算。
-
プール計算って何ですか?
-
一個当たり15秒の製品を1時間で...
-
金利の計算方法を教えてくださ...
-
クリストッフェル記号
-
分数の計算で分子が0になったら...
-
ラプラス変換に関して
-
半径の計算方法を教えてください。
-
映画を1.3倍速で見た時の時間計...
-
積分のエクセル計算式を教えて...
おすすめ情報