2分探索木に関する次の記述を読んで，設問に答えよ。
2分探索木とは，木に含まれる全てのノードがキー値をもち，各ノードNが次の二つの条件を満たす2分木のことである。ここで，重複したキー値をもつノードは存在しないものとする。
・Nの左側の部分木にある全てのノードのキー値は，Nのキー値よりも小さい。
・Nの右側の部分木にある全てのノードのキー値は，Nのキー値よりも大きい。
2分探索木の例を図1に示す。図中の数字はキー値を表している。
図1 2分探索木の例
2分探索木をプログラムで表現するために，ノードを表す構造体Nodeを定義する。構造体Nodeの構成要素を表1に示す。
| 構成要素 | 説明 |
| key | キー値 |
| left | right |
| 左側の子ノードへの参照 | 右側の子ノードへの参照 |
構造体Nodeを新しく生成し，その構造体への参照を変数pに代入する式を次のように書く。
p ← newNode(k)
ここで，引数kは生成するノードのキー値であり，構成要素keyの初期値となる。構成要素left及びrightは，参照するノードがないこと（以下，空のノードという）を表すNULLで初期化される。また，生成したpの各構成要素へのアクセスには“.”を用いる。例えば，キー値はp.keyでアクセスする。
〔2分探索木におけるノードの探索・挿入〕
キー値kをもつノードの探索は次の手順で行う。
（1）探索対象の2分探索木の根を参照する変数をtとする。
（2）tが空のノードであるかを調べる。
（2-1）tが空のノードであれば，探索失敗と判断して探索を終了する。
（2-2）tが空のノードでなければ，tのキー値t.keyとkを比較する。
・t.key=kの場合，探索成功と判断して探索を終了する。
・t.key>kの場合，tの左側の子ノードを新たなとして（2）から処理を行う。
・t.keyくkの場合，tの右側の子ノードを新たなとして（2）から処理を行う。
キー値kをもつノードKの挿入は，探索と同様の手順で根から順にたどっていき空のノードが見つかった位置にノードKを追加することで行う。ただし，キー値kと同じキー値をもつノードが既に2分探索木中に存在するときは何もしない。
これらの手順によって探索を行う関数searchのプログラムを図2に，挿入を行う関数insertのプログラムを図3に示す。関数searchは，探索に成功した場合は見つかったノードへの参照を返し，失敗した場合はNULLを返す。関数insertは，得られた木の根への参照を返す。
//tが参照するノードを根とする木から
//キー値がkであるノードを探索する
function search(t, k)
if(tがNULLと等しい)
return NULL
elseif(t.keyがkと等しい)
return t
elseif(tkeyがkより大きい)
returns earch(t.Left, k)
else//t.keyがkより小さい場合
returns earch(t.right, k)
endif
endfunction
図2 探索を行う関数searchのプログラム
//tが参照するノードを根とする木に
//キー値がkであるノードを挿入する
function insert(t, k)
if(tがNULLと等しい)
t ← new Node(k)
elseif(t.keyがkより大きい)
t.left ← insert(t.left, k)
elseif(t.keyがkより小さい)
t.right ← insert(t.right, k)
endif
return t
endfunction
図3 挿入を行う関数insertのプログラム
関数searchを用いてノードの総数がn個の2分探索木を探索するとき，探索に掛かる最悪の場合の時間計算量（以下，最悪時間計算量という）はO（ ア ）である。これは葉を除く全てのノードについて左右のどちらかにだけ子ノードが存在する場合である。一方で，葉を除く全てのノードに左右両方の子ノードが存在し，また，全ての葉の深さが等しい完全な2分探索木であれば，最悪時間計算量はO（ イ ）となる。したがって，高速に探索するためには，なるべく左右両方の子ノードが存在するように配置して，高さができるだけ低くなるように構成した木であることが望ましい。このような木のことを平衡2分探索木という。
〔2分探索木における回転操作〕
2分探索木中のノードXとXの左側の子ノードYについて，XをYの右側の子に，元のYの右側の部分木をXの左側の部分木にする変形操作を右回転といい，逆の操作を左回転という。回転操作後も2分探索木の条件は維持される。木の回転の様子を図4に示す。ここで，t₁〜t₃は部分木を表している。また，根からt₁〜t₃の最も深いノードまでの深さを，図4（a）ではd₁〜d3，図4（b）ではd₁'〜d₃'でそれぞれ表している。ここで，d₁'=d₁-1，d₂'=d₂，d₃'=d₃+1，が成り立つ。
図4 木の回転の様子
右回転を行う関数rotateRのプログラムを図5に，左回転を行う関数rotateLのプログラムを図6に示す。これらの関数は，回転した結果として得られた木の根への参照を返す。
//tが参照するノードを根とする木に対して
//右回転を行う
function rotateR(t)
a ← t.left
b ← a.right
a.right ← t
t.left ← b
return a
endfunction
図5 右回転を行う関数rotateRのプログラム
//tが参照するノードを根とする木に対して
//左回転を行う
functionrotateL(t)
a ← t.right
b ← a.left
a.left ← t
t.right ← b
return a
endfunction
図6 左回転を行う関数rotateLのプログラム
〔回転操作を利用した平衡2分探索木の構成〕
全てのノードについて左右の部分木の高さの差が1以下という条件（以下，条件Balという）を考える。条件Balを満たす場合，完全ではないときでも比較的左右均等にノードが配置された木になる。
条件Balを満たす2分探索木Wに対して図3の関数insertを用いてノードを挿入した2分探索木をW'とすると，ノードが挿入される位置によっては左右の部分木の高さの差が2になるノードが生じるので，W'は条件Balを満たさなくなることがある。その場合，挿入したノードから根まで，親をたどった各ノードTに対して順に次の手順を適用することで，条件Balを満たすようにW'を変形することができる。
（1）Tの左側の部分木の高さがTの右側の部分木の高さより2大きい場合
Tを根とする部分木に対して右回転を行う。ただし，Tの左側の子ノードUについて，Uの右側の部分木の方がUの左側の部分木よりも高い場合は，先にUを根とする部分木に対して左回転を行う。
（2）Tの右側の部分木の高さがTの左側の部分木の高さより2大きい場合
Tを根とする部分木に対して左回転を行う。ただし，Tの右側の子ノードVについて，Vの左側の部分木の方がVの右側の部分木よりも高い場合は，先にVを根とする部分木に対して右回転を行う。
この手順（1），（2）によって木を変形する関数balanceのプログラムを図7に，関数balanceを適用するように関数insertを修正した関数insertBのプログラムを図8に示す。ここで，関数heightは，引数で与えられたノードを根とする木の高さを返す関数である。関数balanceは，変形の結果として得られた木の根への参照を返す。
//tが参照するノードを根とする木を
//条件Balを満たすように変形する
function balance（t）
h1←height(t.left)height(t.right)
if( ウ )
h2 ← エ
if(h2が0より大きい)
t,.left ← rotateL(t, left)
endif
t ← rotateR(t)
elseif(( オ )
h3 ← カ
if(h3が0より大きい)
t.right ← rotateR(t.right)
endif
t ← rotateL(t)
endif
return t
endfunction
図7 関数balanceのプログラム
//tが参照するノードを根とする木に
//キー値がkであるノードを挿入する
function insertB(t, k)
if(tがNULLと等しい)
t ← newNode(k)
elseif(t.keyがkより大きい)
t.left ← insertB(t.left, k)
elseif(t.keyがkより小さい)
t.right ← insertB(t.right, k)
endif
t ← balance(t) //追加
returnt
endfunction
図8 関数insertBのプログラム
条件Balを満たすノードの総数がn個の2分探索木に対して関数insertBを実行した場合，挿入に掛かる最悪時間計算量はO（ キ ）となる。
設問1 本文中の ア 〜 イ に入れる適切な字句を答えよ。
解答・解説
解答例
ア：n
イ：log n
解説
ー
設問2 回転操作を利用した平衡2分探索木の構成〕について答えよ。
（1）図7中の ウ 〜 カ に入れる適切な字句を答えよ。
解答・解説
解答例
ウ：h1が2と等しい
エ：height(t.left.right) - height(t.left.left)
オ：h1が-2と等しい
カ：height(t.right.left) - height(t.right.right)
解説
ー
（2）図1の2分探索木の根を参照する変数をとしたとき，次の処理を行うことで生成される2分探索木を図示せよ。2分探索木は図1に倣って表現すること。
insertB(insertB(r, 4), 8)
解答・解説
解答例
⑤
／ ＼
③ ⑧
／ ＼ ／ ＼
① ④ ⑥ ⑨
解説
ー
（3）本文中の キ に入れる適切な字句を答えよ。なお，図7中の関数heightの処理時間は無視できるものとする。
解答・解説
解答例
log n
解説
ー
IPA公開情報
出題趣旨
2 分探索木は最も基本的かつ幅広く応用されているデータ構造であり，効率良く探索するための様々な方法が 考案されている。
本問では，2 分探索木の一種である平衡 2 分探索木のうち AVL 木を題材として，木構造，再帰的アルゴリズム，計算量に関する理解を問う。
採点講評
問 3 では，2 分探索木の一種である平衡 2 分探索木のうち AVL 木を題材として，木構造，再帰的アルゴリズム，計算量について出題した。全体として正答率は平均的であった。
設問 2(1)は，いずれも正答率がやや高かった。木構造を再帰的に表現する手法は一般的によく用いられており，是非理解を深めてほしい。
設問 2(2)は正答率が低く，平衡木や 2 分探索木の条件を満たしていない誤った解答が散見された。プログラミングにおいて重要な，アルゴリズムを理解しその操作を机上で再現する能力を身につけるとともに，注意深く解答してほしい。
設問 2(3)は，正答率が低かった。木構造を用いる場合，探索時の計算効率だけではなく，挿入時の計算効率も考慮することが重要である。
