Q&A
> 1を一番最後に挿入したとき。
なぜこの回答に至ったか質問に記載できますか？
2分探索木に関しての質問です。
空の木にデータ 1, 2, 3, 4, 5, 6, 7 をある順番で挿入して 2 分探索木を得る。このと
き，最小値の探索に最も手数のかかる（最も多くの節点を訪問しなければならない）よ
うな 2 分探索木が得られるのは，どのような順番でデータを挿入したときかを答えなさ
い。
解答：
1を一番最後に挿入したとき。
これで合ってますか？
よろしくお願いします。
もし間違っていましたら、正答をお願いします。
本当にこれだけしか情報がないのであれば問題は成立していません。
恐らくあなたが欠席した授業にその他の条件があります。ここではなく友達に聞いてください。
回答3件
0
解答：
1を一番最後に挿入したとき。これで合ってますか？
よろしくお願いします。
そのような問題文が出題されるときには，背景として「２分探索木への挿入というのはこれこれこういう処理である」という前提的な話が前もって与えられているハズと思うので，それに沿って考えれば良い．
（逆に言えば，その場に設けられているそういった前提を明示しなければ外部の者には答え難いということになる．）
さて，
「1を最後に挿入する」が正答か否かに関しては，1を最後とするパターンというのは何種類か考えられるから，それらのパターンを用いた挿入処理を実際に考えてみれば判定できるであろう．
例えば，
今私の頭の中にあるシンプルな挿入処理で考えてみる．
要素数が多いと話が面倒になるので，ここでは｛1,2,3,4｝の４要素だけの例で考えてみる．
- 4,2,3,1 の順で挿入することを考えると，ルートが4になり，1の場所へのルートからの経路は 4→2→1 となる．
- 2,3,4,1 の順で挿入することを考えると，ルートは2になり，1の場所へのルートからの経路は 2→1 となる．
この時点で1の深さが異なっているから，「1を最後に挿入する」では正答とはならないであろう．
投稿2020/12/07 01:44
編集2020/12/07 01:47
総合スコア11990
0
2分探索木の組み上げ方は何種もあるので一意には定まらない。
投稿2020/12/06 14:35
総合スコア16612
ご回答ありがとうございます。
大学の授業の問題で、
問題 2．空の木にデータ 1, 2, 3, 4, 5, 6, 7 をある順番で挿入して 2 分探索木を得る。このと
き，最小値の探索に最も手数のかかる（最も多くの節点を訪問しなければならない）よ
うな 2 分探索木が得られるのは，どのような順番でデータを挿入したときかを答えなさ
い。
という問題があるのですが、この場合はどのように解答すればよいのか、ご教授お願い致します。
いやだから、回答のとおり。
最も素朴(単純)な実装なら、そのデータ列を逆順に挿入したとき。
理由を考えるのはアナタ。
ご返答ありがとうございます。
では、大学で出されている問題は成立しないということですか？
問題にその他の情報が一切ないものなので...
7654321で挿入したときということですか？
大学で出されたのなら、問題に不備がある旨を説明すれば(心ある教師なら)合格にしてくれるんじゃないかな。
> 7654321で挿入したときということですか？
なぜそうなるかが説明できればいいんじゃない？
これでどうですか？
7654321で挿入したとき。
〇か×かで言うとどっちですか？
「7654321で挿入したとき」に最も手数がかかるか否かはあなたが考えることでしょ?
当該サイトは、分からないことがあったら聞くという認識で活用させていただいております。
従って、
「「7654321で挿入したとき」に最も手数がかかるか否かはあなたが考えることでしょ?」
という解答は不適切なものであると思います。自身で考えて分かるものは、こちらのサイトで質問などはしません。
今回の件は、次週の授業で解答が発表されると思われますので、しっかり、正答を発表させていただきます。では、この件においては、失礼いたします。
ご回答ありがとうございました。次回も機会があればよろしくお願いします。
> 自身で考えて分かるものは、こちらのサイトで質問などはしません。
https://teratail.com/help/avoid-asking
↑ココをご一読ください。
「何かを作りたいのでコードを書いてほしい、学校の課題を解いてほしい等の質問は、具体的にプログラミングで困っている質問ではないと考え、推奨していません。
問題や質問は実際に調査や作業に取り組み、具体的なところで生まれると考えるためです。
まずは実際に作業に取り組み、つまづいたところで投稿をしてみてください。」とあります。
二分探索木に要素を挿入/検索するコードを書いたことあるなら、
どんな場合に検索手順が大きくなるか理解できるはずですから。
0
最小値の探索に最も手数のかかる（最も多くの節点を訪問しなければならない）よ
うな 2 分探索木が得られるのは，どのような順番でデータを挿入したときかを答えなさ
い。
2分木の実装を、要素を追加したときにそのノードの値より小さい値は左、大きい値が右に追加するという実装と仮定します。
最小値を探す場合は、値が小さいノードが左側にあるので、全ノードを探索する必要はなく、左側のノードを葉に到達するまで辿っていけばよいことがわかります。
「最小値の探索に最も手数のかかる」ということは「左側のノードを辿っていったときの深さが最大」ということで、「全部の値が左側にぶら下がっているような木が作成される要素の挿入順序」が答えです。
そのような2分木が作成される挿入順序は「7, 6, 5, 4, 3, 2, 1」で深さが「7」となる一通りです。
1を一番最後に挿入したとき。
1を最後に挿入の条件だけではだめです。
例えば、(6, 2, 7, 4, 3, 5, 1) とした場合、深さ3なので、深さが最大とはなりません。
頭でイメージするのが難しい場合は、実際にプログラムを書いて確かめてはどうでしょうか。
要素数7ということは、7!=5040通り試せば答えが見つかるので、全探索でも計算可能です。
投稿2020/12/07 02:17
編集2020/12/07 02:18
総合スコア21956
あなたの回答
tips
プレビュー
