カテゴリ：2.ソフトウェア > 2.2 木構造

 

１．木構造とは

木構造は、データ間の関係を階層的に表現します。
過去問（H16春FE午前問43）では、木構造に関して「ア 階層の上位から下位に節点をたどることによって,データを取り出すことができる構造である。」と述べられています。
tree
階層の○の部分ですが、最上位が「根」、最下位が「葉」、その間を「節」と呼びます。また、根や葉などを接続する線を「枝」と呼びます。

（１）2分木

すべての節が二つ以内の子（節や葉）をもつもの

（２）完全2分木

2分木の中で、「すべての葉が同じ深さであり,かつ,葉以外のすべての節点が二つの子をもつ（H19春SW午前問9）」ものである。別の過去問では、「根からどの葉に向かって木をたどっても,途中で通るノートの数が同じである完全2分木（H18秋SW午後Ⅰ）」という表現もされている。

（３）B木

枝が2つなのが2分木でしたが、枝が2つより多い場合を多分木と言います。
多分木の中で、葉までの階層が全て同じなどの特徴を持つものをB木と言います。
aaa

２．木構造の過去問を解いてみよう

（１）H29秋AP午前

問6　ノート1～5をもつグラフを隣接行列で表したもののうち，木となるものはどれか。ここで，隣接行列のi行j列目の成分は，ノートiとノートjを結ぶエッジがある場合は1，ない場合は0とする。
H29a-問6

↓
↓
↓
↓
↓
【正解】イ

（２）H25秋AP午前

問6　葉以外の節点は全て二つの子をもち，根から葉までの深さが全て等しい木を考える。
　　この木に関する記述のうち，適切なものはどれか。ここで，深さとは根から葉に至るまでの枝の個数を表す。また，節点には根及び葉も含まれる。

ア　枝の個数がnならば，節点の個数もnである。
イ　木の深さがnならば，葉の個数は2n-1である。
ウ　節点の個数がnならば，深さはlog2nである。
エ　葉の個数がnならば，葉以外の節点の個数はn-1である。

↓
↓
↓
↓
↓
【正解】エ

 

１．2分探索木とは

2分探索木に関して過去問（H18秋SW午後1問5）では、「ノードが一つずつデータをもつ2分探索木は,どのノートNから見ても,左側の部分木のノートがもつデータはすべてNのデータよりも小さく,逆に右側の部分木のノートがもつデータはすべてNのデータよりも大きい,という性質をもつ。」と述べられている。

２．2分探索木の過去問を解いてみよう

（１）H28秋FE午前

問6　2分探索木になっている2分木はどれか。
a

↓
↓
↓
↓
↓
【正解】イ

（２）H29秋AP午前

問5　配列A[1]，A[2]，・・・，A[n]で，A[1]を根とし，A[i]の左側の子をA[2i]，右側の子をA[2i＋1]とみなすことによって，2分木を表現する。このとき，配列を先頭から順に調べていくことは，2分木の探索のどれに当たるか。
ア　行きがけ順（先行順）深さ優先探索
イ　帰りがけ順（後行順）深さ優先探索
ウ　通りがけ順（中間順）深さ優先探索
エ　幅優先探索

↓
↓
↓
↓
↓
【正解】エ

（３）H18秋SW午後1

問５　2分探索木に関する次の記述を読んで，設問1~4に答えよ。

　ノートが一つずつデータをもつ2分探索木は，どのノートNから見ても，左側の部分木のノートがもつデータはすべてNのデータよりも小さく，逆に右側の部分木のノートがもつデータはすべてNのデータよりも大きい，という性質をもつ。ここでは，ノートがもつデータはすべて自然数で重複がないものとする。図1に2分探索木の例を示す。ノート内の数が，データを表している。
2分探索木に対して，表1に示す二つの操作を定義する。
18-SW問5-1
　2分探索木を扱うために，それぞれのノートの情報を保持するデータ構造nodeを定義する。データ構造nodeへは， nodeの場所を指す変数であるポインタによってアクセスする。nodeがもつ変数を表2に示す。ここで，nilは，どのnodeも指していないことを示すポインタである。
18-SW問5-2
　nodeとnodeへのポインタの関係を図2に示す。図2では，変数pはnode0へのポインタであり，また，node0の変数left，rightは，それぞれnode1，node2へのポインタである。
　このとき，node0の三つの変数はそれぞれp->value，p->left，p->rightと表す。また，図2に示す状況で，p->leftの値をpへ代入すると，変数pはnode1へのポインタとなる。
18-SW問5-3
　操作lookupでは，2分探索木を根から葉の方向へ順次たどりながら探索を行う。まず，探索するデータと木の根がもつデータとを比べて，等しければ探索は終了する。探索するデータの方が小さければ左の子のノートに，大きければ右の子のノートに移動する。ここで，移動しようとした先に子のノートが存在しない場合，探索するデータが2分探索木内に見つからなかったことになり，探索終了となる。移動した先のノートでも同様にデータを比較し，探索するデータが見つかるか，又は見つからないことが分かるまで繰り返す。



設問１ 　図1の2分探索木に，操作insertを使って40，34，38の順にデータを挿入したときの2分探索木を，解答欄に示せ。

↓
↓
↓
↓
↓
【正解】
18-SW問5-4

 

１．B木とは

多分木の中で、葉までの階層が全て同じなどの特徴を持つものをB木と言います。

B木に関しては、以下で簡単に解説をしました。

sm.seeeko.com

２．B木の過去問を解いてみよう

（１）H28秋AP午前問5　

問5　あるB木は，各節点に4個のキーを格納し,  5本の枝を出す。このB木の根（深さのレベル0）から深さのレベル2までの節点に格納できるキーの個数は，最大で幾つか。
ア　24　　イ　31　　ウ　120　　エ　124

↓
↓
↓
↓
↓
【正解】エ
雑ですが、問題文の内容を図にすると、以下のようになります。
aaaa
深さレベル0には4個。深さレベル１には４×５＝20個、深さレベル２には、２０×４＝８０個を格納できます。
結果、４＋２０＋８０＝１２４個、つまり、エが正解です。

（２）H28秋AP午前

問27　B＋木インデックスが定義されている候補キーを利用して，1件のデータを検索するとき，データ総件数Xに対するB＋木インデックスを格納するノートへのアクセス回数のオーダを表す式はどれか。

ア　√X
イ　logX
ウ　X
エ　X!

↓
↓
↓
↓
↓
【正解】イ

↑このページのトップヘ