令和5年度秋期応用情報技術者試験午後問題問3 AVL木の回転操作と計算量

この問題は2023(R5)秋応用情報技術者午後に出題されたものです。出題時点の法令・制度に基づく内容のため、現行の内容と一致しない場合があります。

本ページの問題文・選択肢は、原本の体裁を Web 表示用に正規化しています（改行・記号・数式・図表参照の調整）。設問の趣旨および正解に影響する変更は加えていません。

学習ガイド

2分探索木の一種であるAVL木を題材に、木構造・再帰・計算量を横断して問うアルゴリズムの問題です。ノードを挿入すると左右の高さの差が崩れ、回転操作で平衡を取り戻すという動作を正確に追えるかが中心で、空欄には回転の向きや高さの条件を判断する式が入ります。単に語句を埋めるのではなく、なぜ回転で探索効率が対数オーダーに保たれるのかまで説明できることを目標に、この記事では小さな木の変形を一段ずつたどりながら各設問の根拠を確認します。

この記事で押さえる論点

2分探索木が平衡を失うと探索効率が落ちる理由を説明できる
AVL木の回転操作で木の高さを保つ仕組みを追跡する
再帰的アルゴリズムの空欄を前後の処理から埋める
平衡木の計算量オーダーを木の高さから判断する

出題情報

出題: 2023(R5)秋応用情報技術者午後問3
配点: 20点満点
模範解答: 公表(設問ごとに掲載)

出題趣旨・採点講評(IPA 公表)

2分探索木は最も基本的かつ幅広く応用されているデータ構造であり，効率良く探索するための様々な方法が考案されている。本問では，2分探索木の一種である平衡2分探索木のうちAVL木を題材として，木構造，再帰的アルゴリズム，計算量に関する理解を問う。

問3では，2分探索木の一種である平衡2分探索木のうちAVL木を題材として，木構造，再帰的アルゴリズム，計算量について出題した。全体として正答率は平均的であった。

問題本文

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

2分探索木とは，木に含まれる全てのノードがキー値をもち，各ノードNが次の二つの条件を満たす2分木のことである。ここで，重複したキー値をもつノードは存在しないものとする。

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

2分探索木の例を図1に示す。図中の数字はキー値を表している。

2分探索木をプログラムで表現するために，ノードを表す構造体Nodeを定義する。構造体Nodeの構成要素を表1に示す。

構成要素	説明
key	キー値
left	左側の子ノードへの参照
right	右側の子ノードへの参照

構造体Nodeを新しく生成し，その構造体への参照を変数pに代入する式を次のように書く。

$p \leftarrow \text{new Node}(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 の左側の子ノードを新たな t として(2)から処理を行う。
- t.key < k の場合，t の右側の子ノードを新たな t として(2)から処理を行う。

キー値 k をもつノード K の挿入は，探索と同様の手順で根から順にたどっていき，空のノードが見つかった位置にノード K を追加することで行う。ただし，キー値 k と同じキー値をもつノードが既に2分探索木中に存在するときは何もしない。

これらの手順によって探索を行う関数 search のプログラムを図2に，挿入を行う関数 insert のプログラムを図3に示す。関数 search は，探索に成功した場合は見つかったノードへの参照を返し，失敗した場合は NULL を返す。関数 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₁〜d₃，図4(b)では d₁'〜d₃' でそれぞれ表している。ここで，d₁'＝d₁－1，d₂'＝d₂，d₃'＝d₃＋1，が成り立つ。

右回転を行う関数 rotateRのプログラムを図5に，左回転を行う関数 rotateLのプログラムを図6に示す。これらの関数は，回転した結果として得られた木の根への参照を返す。

〔回転操作を利用した平衡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は，変形の結果として得られた木の根への参照を返す。

条件 Bal を満たすノードの総数が n 個の 2 分探索木に対して関数 insertB を実行した場合，挿入に掛かる最悪時間計算量は O(キ) となる。

設問と解答・解説

設問1

(1)

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

模範解答

採点基準(配点 3点)

正確性（内容）(3点)

3点: 正解となる計算量の式を正確に解答している。
1点: 計算量の式に関する字句を解答しているが、完全な正解ではない。
0点: 解答がない、または完全に誤っている。

解説

2分探索木において、ノード数が $n$ のとき、要素が偏って挿入されると木が一直線に伸びた状態になります。

探索や挿入における最悪の計算量は木の高さに比例するため、この場合の計算量は $O(n)$ となります。

高得点のポイント

2分探索木の構造上、要素がソートされた順に挿入された場合などに木が極端に偏ることを理解している。
その偏った状態の木の高さが $n$ に比例することを把握している。

(2)

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

模範解答

log n

採点基準(配点 3点)

正確性（内容）(3点)

3点: 正解となる計算量の式を正確に解答している。
1点: 対数時間であることは理解しているが、表記に誤りがある。
0点: 解答がない、または完全に誤っている。

解説

平衡2分探索木（AVL木など）では、要素の挿入や削除の際に木が極端に偏らないように回転操作を行い、左右の部分木の高さの差を一定以内に保ちます。

この仕組みにより、ノード数 $n$ に対して木の高さは常に $O(\log n)$ に抑えられます。したがって、最悪計算量も $O(\log n)$ となります。

高得点のポイント

平衡2分探索木が木の高さを常に $O(\log n)$ に保つデータ構造であることを理解している。
探索の計算量が木の高さに比例し、 $O(\log n)$ となることを論理的に把握している。

設問2

〔回転操作を利用した平衡 2 分探索木の構成〕について答えよ。

(1)

図7中のウに入れる適切な字句を答えよ。

模範解答

h1が2と等しい

採点基準(配点 2点)

正確性（内容）(2点)

2点: 正解となる条件式を正確に解答している。
1点: 条件式の意味は捉えているが、変数名や定数に誤りがある。
0点: 解答がない、または完全に誤っている。

解説

AVL木におけるバランス調整の判定条件に関する問題です。

図7の処理では、あるノードの左右の部分木の高さの差 $h1 = height(t.left) - height(t.right)$ を計算しています。

AVL木の定義として、高さの差が 2以上 または -2以下 になったときにバランスを崩したと判定します。

ここでは、左の部分木の方が高くバランスが崩れた場合、すなわち $h1$ が 2 と等しい場合の条件式が入ります。

高得点のポイント

再帰的アルゴリズムにおける木の高さの差の計算意図を正しく理解している。
AVL木のバランス崩壊の定義（高さの差の絶対値が2以上）を正確に把握している。

(2)

図7中のエに入れる適切な字句を答えよ。

模範解答

height(t.left.right) - height(t.left.left)

採点基準(配点 2点)

正確性（内容）(2点)

2点: 正解となる計算式を正確に解答している。
1点: 計算式の構造は概ね正しいが、プロパティの参照順序等に軽微な誤りがある。
0点: 解答がない、または完全に誤っている。

解説

左の部分木が重くてバランスを崩した場合、回転操作として LL回転（右回転）を行うか、LR回転（左回転のち右回転）を行うかを判定する必要があります。

この判定には、左の子ノードのさらに左右の部分木の高さの差を確認します。

図7の空欄エの右辺では、左の子の右部分木の高さから左部分木の高さを引いた値が0より大きい場合（LR回転が必要な場合）を判定するため、 $height(t.left.right) - height(t.left.left)$ と比較する記述となります。

高得点のポイント

LL回転とLR回転の分岐条件を正しく理解している。
再帰的データ構造の参照を適切に記述できる。

(3)

図7中のオに入れる適切な字句を答えよ。

模範解答

h1が-2と等しい

採点基準(配点 2点)

正確性（内容）(2点)

2点: 正解となる条件式を正確に解答している。
1点: 条件式の意味は捉えているが、符号や定数に誤りがある。
0点: 解答がない、または完全に誤っている。

解説

右の部分木が重くてバランスを崩した場合の条件に関する問題です。

左右の高さの差 $h1 = height(t.left) - height(t.right)$ において、右の部分木の方が2だけ高い場合、 $h1$ の値は -2 になります。

したがって、バランス崩壊を判定するために「 $h1$ が -2 と等しい」という条件式が入ります。

高得点のポイント

算出式に基づき、右部分木が高い場合の値が負の数になることを理解している。
平衡2分探索木における左右対称の操作のロジックを理解している。

(4)

図7中のカに入れる適切な字句を答えよ。

模範解答

height(t.right.left) - height(t.right.right)

採点基準(配点 2点)

正確性（内容）(2点)

2点: 正解となる計算式を正確に解答している。
1点: 計算式の構造は概ね正しいが、プロパティの参照順序等に軽微な誤りがある。
0点: 解答がない、または完全に誤っている。

解説

右の部分木が重い場合において、RR回転（左回転）を行うか、RL回転（右回転のち左回転）を行うかを判定する処理です。

ここでは右の子ノードについて、さらにその左部分木と右部分木の高さの差を調べます。

判定式としてRL回転が必要な条件を調べるため、 $height(t.right.left) - height(t.right.right)$ を用いて比較を行います。

高得点のポイント

RR回転とRL回転の分岐条件を正しく理解している。
対象となるノードを正確に指定し、適切な式を組み立てることができる。

(5)

図1の2分探索木の根を参照する変数を r としたとき、次の処理を行うことで生成される2分探索木を図示せよ。2分探索木は図1に倣って表現すること。

insertB(insertB(r, 4), 8)

模範解答

5 1 4 3 8 6 9

採点基準(配点 4点)

知識・理解度（内容）(2点)

2点: 平衡木や2分探索木の条件を満たすように、挿入と回転のアルゴリズムを正しく適用できている。
1点: アルゴリズムに基づく操作を試みているが、回転操作等に一部誤りがある。
0点: 操作の適用が不適切であるか、解答がない。

論理性（構造）(2点)

2点: 2分探索木の条件（左の子 < 親 < 右の子）を完全に満たし、各ノードの親子関係が明確に示されている。
1点: 木構造として表現されているが、一部で2分探索木の大小関係の条件を満たしていない箇所がある。
0点: 木構造として正しく表現されていないか、解答がない。

解説

初期状態のAVL木に対して、値 4 を挿入し、次に 8 を挿入した結果の木構造を求める問題です。

4の挿入: 4 は 5 の左、3 の右に挿入されます。挿入後、どのノードも高さの差の絶対値が1以下であるため、回転操作は発生しません。
8の挿入: 8 は 5 の右、9 の左、6 の右に挿入されます。

挿入後、9 のノードでは左の子の高さが 2、右の子の高さが 0 となり、高さの差が 2 となってバランスを崩します。

この原因は 9 の左の子 (6) の右の子 (8) にあるため、LR回転が行われます。

まず 6 を左回転して 8 を上に上げ、次に 9 を右回転して 8 を親にすることで、8 が親、6 が左の子、9 が右の子という構造になり平衡が保たれます。

高得点のポイント

指定された値の挿入位置を2分探索木の条件に基づき正しく特定できる。
挿入後に各ノードの平衡条件を確認し、どのノードでバランス崩壊が起きているかを正確に特定できる。
適切な回転操作を選択し、机上で正しくシミュレーションして新しい木構造を導出できる。

(6)

本文中のキに入れる適切な字句を答えよ。なお、図7中の関数 height の処理時間は無視できるものとする。

模範解答

log n

採点基準(配点 2点)

正確性（内容）(2点)

2点: 正解となる計算量の式を正確に解答している。
1点: 対数時間であることは理解しているが、表記に誤りがある。
0点: 解答がない、または完全に誤っている。

解説

AVL木に対して要素を挿入する際にかかる全体の計算量を問う問題です。

探索フェーズ: 挿入すべき位置を見つけるため根から葉へ木をたどります。AVL木では木の高さが $O(\log n)$ に保たれているため、探索には $O(\log n)$ の時間がかかります。
平衡化フェーズ: 挿入後の回転操作はポインタの付け替えのみであり、 $O(1)$ の時間で行われます。再帰的に木の根まで戻る過程を含めても全体の操作回数は制限されます。

したがって、全体の処理時間は探索フェーズの計算量に律速され、 $O(\log n)$ となります。

高得点のポイント

AVL木の挿入処理が「挿入位置の探索」と「回転による平衡化」の2ステップからなることを理解している。
平衡化にかかる時間が少なく、全体のオーダーが木の高さに依存する $O(\log n)$ となることを論理的に導ける。

設問2(1)は，いずれも正答率がやや高かった。木構造を再帰的に表現する手法は一般的によく用いられており，是非理解を深めてほしい。設問2(2)は正答率が低く，平衡木や2分探索木の条件を満たしていない誤った解答が散見された。プログラミングにおいて重要な，アルゴリズムを理解しその操作を机上で再現する能力を身につけるとともに，注意深く解答してほしい。設問2(3)は，正答率が低かった。木構造を用いる場合，探索時の計算効率だけではなく，挿入時の計算効率も考慮することが重要である。