平成27年秋期試験午後問題 問3

問3 プログラミング

⇱問題PDF
2分探索木に関する次の記述を読んで,設問1~4に答えよ。
 2分探索木とは,全てのノードNに対して,次の条件が成立している2分木のことである。
  • Nの左部分木にある全てのノードのキー値は,Nのキー値よりも小さい。
  • Nの右部分木にある全てのノードのキー値は,Nのキー値よりも大きい。
 ここで,ノードのキー値は自然数で重複しないものとする。2分探索木の例を図1に示す。図中の数はキー値を表している。
pm03_1.png
 2分探索木を実現するために,ノードを表す構造体 Node を定義する。構造体 Node の構成要素を表1に示す。
pm03_2.png
 構造体の実体を生成するためには,次のように書く。
  new Node(key)
 生成した構造体への参照が戻リ値となる。構造体の構成要素のうち,keyは引数keyの値で初期化され,leftとrightはnullで初期化される。
 変数pが参照するノードをノードpという。ノードを参照する変数からそのノードの構成要素へのアクセスには"."を用いる。例えば,ノードpのキー値には,p.keyでアクセスできる。
 なお,変数pの値がnullの場合,木は空である。

〔2分探索木でのノードの探索〕
 与えられたキー値をもつノードを探索する場合,親から子の方向へ,木を順次たどりながら探索を行う。
 探索する2分探索木にノードがない場合は,目的のノードが見つからず,探索は失敗と判断して終了する。探索する2分探索木にノードがある場合は,与えられたキー値と木の根のキー値を比較し,等しければ,目的のノードが見つかったので探索は成功と判断して終了する。与えられたキー値の方が小さければ左部分木に,大きければ右部分木に移動する。移動先の部分木でも同様に探索を続ける。
 この手順によって探索を行う関数 search のプログラムを図2に示す。このプログラムでは,探索が成功した場合は見つかったノードへの参照を返し,失敗した場合はnullを返す。
pm03_3.png
〔2分探索木へのノードの挿入〕
 2分探索木にノードを挿入する場合,探索と同様に,親から子の方向へ,木を順次たどりながら,適切な位置にノードを挿入する。
 挿入する2分探索木にノードがない場合は,挿入するキー値のノードを作成する。挿入する2分探索木にノードがある場合は,挿入するキー値と木の根のキー値を比較し,挿入するキー値の方が小さければ左部分木に,大きければ右部分木に移動する。移動先の部分木でも同様の処理を続ける。
 この手順によって挿入を行う関数 addNode のプログラムを図3に示す。このプログラムでは,挿入の結果として得られた2分探索木の根のノードへの参照を返す。ただし,このプログラムは,挿入するキー値と同じキー値をもつノードが2分探索木に既に存在するときは何もしない。
pm03_4.png
〔2分探索木からのノードの削除〕
 2分探索木から,あるキー値をもつノードを削除する場合,次の(1)~(3)の手順を行う。
  • 2分探索木にノードがない場合は,何もしないで処理を終了する。
  • 削除するキー値と木の根のキー値を比較し,削除するキー値の方が小さければ左部分木に,大きければ右部分木に移動する。移動先の部分木でも同様の処理を続ける。
  • 削除するキー値と木の根のキー値が等しい場合,削除するキー値をもつノードを削除するため,次の(3-1)~(3-3)を実行する。
    (3-1)
    削除するノードが子ノードをもたない場合,そのノードを削除する。
    (3-2)
    削除するノードが子ノードを一つだけもつ場合,削除するノードの位置にその子ノードを置く。
    (3-3)
    削除するノードが左右両方に子ノードをもつ場合,削除するノードの左部分木の中で最大のキー値をもつノードを左部分木から取り除き,削除するノードの位置に置く。
 この手順を使って2分探索木からノードの削除を行う関数 removeNode のプログラムを図4に示す。このプログラムでは,削除した後の2分探索木の根のノードへの参照を返す。ただし,このプログラムは,削除するキー値をもつノードが2分探索木に存在しないときは何もしない。
 図4中の関数 extractMaxNode は,引数で指定されたノードを根とする2分探索木の中で最大のキー値をもつノードを木から削除し,削除されたノードへの参照を大域変数 extractedNode に設定した上で,削除した後の2分探索木の根のノードへの参照を返す。関数 extractMaxNode のプログラムを図5に示す。
pm03_5.png
〔2分探索木の計算量〕
 2分探索木における計算量は,木の高さに依存する。図2の関数 search を使ってn個のノードから成る2分探索木を探索する場合,想定される最大の計算量は,O()である。木構造が完全2分木であれば,その計算量は最大でもO()で ある。

設問1

図1中のに入れる適切な数を答えよ。

解答例・解答の要点

ア:11

解説

について〕
図1「2分探索木の例」の[ア]に当てはまる数を考えます。
まず、問題文の5行目に「ここで,ノードのキー値は自然数で重複しないものとする」とあるため、[ア]には他のノードのキー値と重複しない自然数が入ることがわかります。そして、問題文の3行目と4行目より、2分探索木とは以下の条件が成立している2分木であることがわかります。
  1. Nの左部分木にある全てのノードのキー値は、Nのキー値よりも小さい。
  2. Nの右部分木にある全てのノードのキー値は、Nのキー値よりも大きい。
1つ目の条件より[ア]は12より小さく、2つ目の条件より[ア]は10より大きくなければならないことがわかります。よって、10より大きく12より小さい自然数である11が入ります。

=11
pm03_8.png

設問2

図2~4中のに入れる適切な字句を答えよ。

解答例・解答の要点

イ:k が p.key より小さい
ウ:new Node(k)
エ:return p
オ:p.left
カ:p.right
キ:p ← r

解説

について〕
図2「関数 search のプログラム」の[イ]に当てはまる字句を考えます。

[イ]の条件式の結果が真のとき、以下の処理が実行されます。
//8行目
return search(k, p.left) //左部分木を探索する
本文の〔2分探索木でのノードの探索〕の6行目に「与えられたキー値の方が小さければ左部分木に、大きければ右部分木に移動する」とあります。左部分木の探索に移るのは「木の根のキー値よりも与えられたキー値の方が小さい」場合です。木の根のキー値は「p.key」、探索しているキー値は「k」で参照できるため、[イ]には「kがp.keyより小さい」が入ります。

=k が p.key より小さい

について〕
図3「関数 addNode のプログラム」の[ウ]に当てはまる字句を考えます。[ウ]は、図3の3行目の条件式の「pとnullが等しい」ときに行うべき処理です。

本文中に「変数pの値がnullの場合,木は空である」と記載があるように、「pとnullが等しい」ときとは挿入先の2分探索木にノードが存在しない場合を表します。〔2分探索木へのノードの挿入〕を読むと、「挿入する2分探索木にノードがない場合は,挿入するキー値のノードを作成する」とあるので、[ウ]には「挿入するキー値のノードを作成する」処理が入ると判断できます。

ノード作成のための命令は、表1の次行に「構造体の実体を生成するためには、次のように書く。new Node(key)」と説明されています。挿入するノードのキー値は、変数 k が保持しているため、k を引数にして「new Node(k)」を実行すれば良いことになります。よって、[ウ]には「new Node(k)」が入ります。

=new Node(k)

について〕
図3「関数 addNode のプログラム」の「エ」に当てはまる字句を考えます。

問題文の〔2分探索木へのノードの挿入〕には、「このプログラムでは,挿入の結果として得られた2分探索木の根のノードへの参照を返す」とあります。図3のソースには関数の戻り値を指定する文が存在しませんから、[エ]には挿入の結果として得られた2分探索木の根のノードへの参照を返す処理が入ります。
関数 addNode は、挿入するキー値(k)と、根ノードの参照(p)を引数としていますので、戻り値として p を返せば良いことになります。よって、[エ]には「return p」が入ります。

=return p

について〕
図4「関数 removeNode のプログラム」の[オ]に当てはまる字句を考えます。

〔2分探索木からのノードの削除〕の(3)に説明されている処理が、図4のプログラムの8行目から21行目の処理に対応しています。
pm03_9.png
(3-2)の処理は、削除するノードが子ノードを(左右どちらか)1つだけ持つ場合に行われる処理です。このとき、存在する子ノードが左側であれば、削除するノードの位置に左部分木を移動し、存在する子ノードが右側であれば、削除するノードの位置に右部分木を移動します。
[オ]がnullのときに実行される「p←p.right」は、削除する位置に右側の部分木を移動させる処理ですから、条件式は「削除するノードの左の子ノードがない場合(=削除するノードが右の子ノードを持つ場合)」であることがわかります。よって、[オ]には「p.left」が入ります。

同様の考え方で、「p←p.left」を実行する条件式は「p.rightがnullと等しい」となります。よって、[カ]には「p.right」が入ります。

=p.left
 =p.right

について〕
図4「関数 removeNode のプログラム」の[キ]に当てはまる字句を考えます。

(3-3)の処理内容を確認します。
16行目
p.leftを根とする2分探索木の中で最大のキー値を持つノードを削除し、削除した後の2分探索木の根のノードへの参照をp.leftに返します。さらに、削除したノードへの参照を extractedNode に代入します。
17行目
rに削除したノードへの参照 extractedNode を代入します。
18行目
rの左の子ノードにpの左の子ノードへの参照を設定します。
19行目
rの右の子ノードにpの右の子ノードへの参照を設定します。
20行目
rは、削除するノードと差し替えるためのノードです。最後に削除するノード(p)の位置に入れ替えるノード(r)を置く必要があるので、20行目ではrをpに代入する処理を行う必要があります。よって、[キ]には「p ← r」が入ります。

=p ← r

設問3

本文中のに入れる適切な字句を答えよ。

解答例・解答の要点

ク:n
ケ:log n

解説

について〕
問題文の〔2分探索木の計算量〕には、「2分探索木における計算量は、木の高さに依存する」とあります。想定される最大の計算量を求めるには、比較回数が最大になる場合を考えます。

探索において比較回数が最大になるのは、全てのノードが一つの子ノードを持つ構造になっていて、探索するキー値が木の葉部分に位置している場合です。このときのノードの数をnとすると、木の高さはn-1です(木の高さは根から一番遠い葉までの枝の数です)。最大比較回数は「木の高さ+1」で求めることができるため、「n-1+1=n回」になります。以上より、計算量はO(n)となるので、[ク]には「n」が入ります。

=n

について〕
完全2分木とは、全てのノードが2つの子ノードを持ち、根から葉までの距離がどこでも等しい下図のような木構造です。
pm03_10.png
完全2分木の場合は、探索範囲を1/2ずつに狭めながら探索していきます。すなわち、n個のノードを1/2することをk回繰り返して、1つの値を見つけます。このことから、「n×1/2k=1」の式を導くことができます。

 n×1/2k=1
 n=1/(1/2k)
 n=1×2k
 n=2k

より「k=log2n」となります。O記法では通常、底を省略して記述しますので、[ク]には「log n」が入ります。

※完全2分木を探索する計算量は、2分探索の計算量と同じです。

=log n

設問4

次の順でキー値の挿入と削除を行った後でノードqを根とする2分探索木を答えよ。2分探索木は,図1の例に倣って表現すること。
pm03_6.png

解答例・解答の要点

pm03_7.png

解説

q ← null
2分探索木を空にするための処理です。
q ← addNode(5, q)
手順2から手順9は図3の関数 addNode を使用してノードを追加していく処理です。関数 addNode は、pのノードのキー値と挿入するノードのキー値を比較しながら、2分探索木として適切な位置に子ノードを追加していきます。
最初は、木にノードがないので、根の位置にノードを生成します。
pm03_11a.png
q ← addNode(2, q)
pm03_11b.png
q ← addNode(7, q)
pm03_11c.png
q ← addNode(1, q)
pm03_11d.png
q ← addNode(8, q)
pm03_11e.png
q ← addNode(4, q)
pm03_11f.png
q ← addNode(3, q)
pm03_11g.png
q ← addNode(12, q)
pm03_11h.png
ここまででノードを追加する処理は終了です。続いて removeNode で指定したキー値のノードを削除する処理を行います。
q ← removeNode(5, q)
キー値が5のノードを削除します。キー値が5のノードは2分探索木の根にあります。よって、removeNode関数の(3-3)の「削除するノードが左右両方に子ノードをもつ場合」に該当します。この場合は、「削除するノードの左部分木の中で最大のキー値をもつノードを左部分木から取り除き,削除するノードの位置に置く」という処理を行います。

左部分木の中で最大値は4ですから、
  1. 4を取り除く
  2. 4の位置に3を置く
  3. 4の左の子ノードとして2を設定する
  4. 4の右の子ノードとして7を設定する
  5. 5の位置に4を置く
という処理を行って2分探索木を再構成します。
pm03_11i.png
q ← removeNode(7, q)
キー値が7のノードを削除します。キー値が7のノードは右側の部分木のみをもっているため、(3-2)の「削除するノードが子ノードを一つだけもつ場合」に該当します。この場合は、「削除するノードの位置にその子ノードを置く」という処理を行います。つまり、7を取り除き、7の位置に8以降の部分木が収まります。
pm03_11j.png
最終的に出来上がった木が本問の答えとなります。
模範解答

Pagetop