[記事公開日]2014/12/11
[最終更新日]2016/11/26

基本情報技術者試験 2-5(木構造)


 

 

データの探索方法に「木構造」というものがあります。

 

ある値(データ)を探すのに、どの方法が一番早いのかという視点では、この方法が最も早いとされています。片方から探し始めるわけでもなく、ランダムに探すわけでもありません。ど真ん中に焦点をあて、そこから「その値よりも大きいなら左を探し、その値よりも小さいなら右を探す」という方法です。最短で1回目で見つけられますし、最長でも「データの数×2分の1」の探索数で探すことができます。仮に、どちらかの片方から探すとしたら、最短は1回で「木構造」と同じですが、最長では「データの数だけ検索」しなくてはなりません。

 

・二分木

・完全二分木

・二分探索木

・逆ポーランド

 

「木構造」は字の通り、「ツリー」を意味しており、

・「根」

・「枝」

・「葉」

を持っています。

 

●二分木

「親1人と子2人」がいくつも合わさってできた木構造のこと。子が3人いれば、「3分木」になるのでしょうが、それではデータ探索の方法にはなりませんね。

二分探索木1

・親の位置を「」といいます。

・棒の部分を「」といいます。

・子の部分を「」といいます。

・末端の節を「」と呼びます。

(上の絵だと、葉は2枚)

 

※節には、実際には何かのデータが入っていると考えてください。

 

●完全二分木

完全二分木
⇒深さが等しい二分木。とはいいつつも・・、右と左で深さが等しくないのに、「x階くらいまでは右と左で違っても完全二分木とよぶ」みたいなことがありますから、注意してください。

 

●二分探索木

二分探索木

左の葉>節>右の葉の順に、値が小<中<大となっています。このようにしておけば、データを探すときも比較的早くなります。

 

例えば「4」を見つけたければ、まず「6」とか「8」から探索します。4は6よりも値が小さいため、左へと探索していきます。次に「3」がでてきます。4は3よりも値が大きいため、右へ移動します。こんな風にして探索する仕組みです。

 

二分木で探索するから、「二分探索木」です。それだけです。

 

●ヒープ木

ヒープ木

・全ての親子関係で、値が「親>子(または同値)」であれば、「最大ヒープ」とよびます。

 

・全ての親子関係で、値が「子>親(または同値)」であれば、「最小ヒープ」とよびます。

 

※ちなみに「ヒープ」(heap)とは、日本語で「山」とか「重なり」、「積み上げ」という意味を持ちます。

 

※単純に「ヒープ」という場合、「二分木」と同じことを言っていると思ってよいです。

 

●逆ポーランド(超重要)

※ちょっと難しいです。

 

「1+2」は

「12+」と表記します。

「左→右→真ん中」の順で書き出します。

このように図を書いてみると分かりやすいです。

逆ポーランド

 

<例>

(4+3)×(2-2)

(43+)×(22-)

43+22-×

 

算数のやり方と同じで、
・カッコ内の計算を先にします。
・「+-」よりも、「×÷」を優先させます。

 

<例>

Y=(A+B)×(C-D÷E)


Y=(AB+)×(C-DE÷

逆ポーランド2

Y=(AB+)×(CDE÷-)

(AB+)(CDE÷-)×

AB+CDE÷-×

 

 

▲注意
「Y=」は最後に割り振ってください。

 

<例>

・どこかに値が挿入されたり、どこかの値が削除する出題がされます。そして、どのように二分木(ピープ)が動いたのかを問われます。

 

逆ポーランド挿入

 

この図では、「左<右<真ん中」の順になっています。

 

完成された二分木に値(例えば5とか)を挿入します。

どこに何が移動されたのか問われます。

 

やり方は簡単です。

 

問題文にある二分木を見て、そもそもどの順で値が大きくなっているのかを確認します。

・「左<右<真ん中」?

・「左<真ん中<右」?

 

 

そして、指定された箇所に挿入(または削除)をしてみます。

 

多くの場合、節(ノード)を3つ、4つ動かさないと二分木は作り直せません。

 

意外とわかっているつもりでも間違えてしまう問題です。

 

難しくなってきたら、絵を描いた方分かりやすいかと思います。

 

 

以上です。

 

 

yamatunes