解説

〔アについて〕
図1「2分探索木の例」の[ア]に当てはまる数を考えます。
まず、問題文の5行目に「ここで，ノードのキー値は自然数で重複しないものとする」とあるため、[ア]には他のノードのキー値と重複しない自然数が入ることがわかります。そして、問題文の3行目と4行目より、2分探索木とは以下の条件が成立している2分木であることがわかります。

1. Nの左部分木にある全てのノードのキー値は、Nのキー値よりも小さい。
2. Nの右部分木にある全てのノードのキー値は、Nのキー値よりも大きい。

1つ目の条件より[ア]は12より小さく、2つ目の条件より[ア]は10より大きくなければならないことがわかります。よって、10より大きく12より小さい自然数である11が入ります。

∴ア＝11

解説

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

[イ]の条件式の結果が真のとき、以下の処理が実行されます。
本文の〔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行目の処理に対応しています。(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

解説

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

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

∴ク＝n

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

　n×1／2^k＝1
　n＝1／(1／2^k)
　n＝1×2^k
　n＝2^k

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

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

∴ク＝log n

解説

q ← null

2分探索木を空にするための処理です。

q ← addNode(5, q)

手順2から手順9は図3の関数 addNode を使用してノードを追加していく処理です。関数 addNode は、pのノードのキー値と挿入するノードのキー値を比較しながら、2分探索木として適切な位置に子ノードを追加していきます。
最初は、木にノードがないので、根の位置にノードを生成します。

q ← addNode(2, q)

q ← addNode(7, q)

q ← addNode(1, q)

q ← addNode(8, q)

q ← addNode(4, q)

q ← addNode(3, q)

q ← addNode(12, q)

ここまででノードを追加する処理は終了です。続いて 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分探索木を再構成します。

q ← removeNode(7, q)

キー値が7のノードを削除します。キー値が7のノードは右側の部分木のみをもっているため、(3-2)の「削除するノードが子ノードを一つだけもつ場合」に該当します。この場合は、「削除するノードの位置にその子ノードを置く」という処理を行います。つまり、7を取り除き、7の位置に8以降の部分木が収まります。

最終的に出来上がった木が本問の答えとなります。