応用情報技術者 2023年秋期午後問03

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

　2分探索木とは、木に含まれる全てのノードがキー値をもち、各ノードNが次の二つの条件を満たす2分木のことである。ここで、重複したキー値をもつノードは存在しないものとする。　・Nの左側の部分木にある全てのノードのキー値は、Nのキー値よりも小さい。　・Nの右側の部分木にある全てのノードのキー値は、Nのキー値よりも大きい。　2分探索木の例を図1に示す。図中の数字はキー値を表している。

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

　構造体Nodeを新しく生成し、その構造体への参照を変数pに代入する式を次のように書く。　p ← 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_{1}

～

t_{3}

は部分木を表している。また、根から

t_{1}

～

t_{3}

の最も深いノードまでの深さを、図4(a)では

d_{1}

～

d_{3}

、図4(b)では

d_{1}^{'}

～

d_{3}^{'}

でそれぞれ表している。ここで、

d_{1}^{'}

d_{1}

- 1、

d_{2}^{'}

d_{2}

、

d_{3}^{'}

d_{3}

+ 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：

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

模範解答

ア：n イ：log n

解説

解答の論理構成

まず【問題文】では、探索アルゴリズム search について
“関数searchを用いてノードの総数がn個の2分探索木を探索するとき、探索に掛かる最悪の場合の時間計算量（以下、最悪時間計算量という）はO(ア)である。”
と述べています。
最悪時間計算量は、左右のどちらかにしか子がないノードが続く「一本鎖」のような木構造が発生した場合です。ノードを順にたどるしかないため比較は最大 “n個” 行われ、従って $O (n)$ となります。したがって
ア：n
が入ります。
一方で同じ段落の後半には、 “葉を除く全てのノードに左右両方の子ノードが存在し、また、全ての葉の深さが等しい完全な2分探索木であれば、最悪時間計算量はO(イ)となる。”
とあり、完全二分木では高さが $lo g_{2} n$ オーダーに抑えられます。探索経路も高々その高さなので $O (lo g n)$ が上限です。従って
イ：log n
となります。

誤りやすいポイント

「最悪時間計算量＝高さ」と結び付けず、平均ケースと混同してしまう。完全二分木の平均高さも $Θ (lo g n)$ ですが、問題は“最悪”を問うています。
$O (lo g n)$ を「 $O (lo g_{2} n)$ 」「 $O (lo g_{2} (n))$ 」など底を明示して書きたくなりますが、ビッグオー表記では底は定数扱いなので “log n” で十分です。
一本鎖の木を「n−1 比較だから $O (n - 1)$ 」と細かく書くと、ビッグオーの意味を取り違えていると採点されることがあります。

FAQ

Q: 完全二分木でなくても「条件Bal」を満たせば必ず

O (lo g n)

になりますか？
A: はい。左右部分木の高さ差が高々1に保たれれば木の高さは

Θ (lo g n)

に収まるため、探索も同オーダーです。

Q: 平衡を保つ回転操作（rotateL / rotateR）を行うとキー順序が壊れませんか？
A: 壊れません。【問題文】で“回転操作後も2分探索木の条件は維持される”と明記されています。

Q: 平衡化アルゴリズムと AVL 木や Red-Black 木は同じですか？
A: 基本概念は共通ですが、具体的な条件と回転のタイミングが異なります。本問は“高さ差≦1”というAVL型の条件を採用しています。

関連キーワード: 2分探索木、ビッグオー記法、平衡木、回転操作、高さ解析

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

（1）図7中のウ〜カに入れる適切な字句を答えよ。

模範解答

ウ：h1が2と等しいエ：height(t.left.right) - height(t.left.left) オ：h1が-2と等しいカ：height(t.right.left) - height(t.right.right)

解説

解答の論理構成

“全てのノードについて左右の部分木の高さの差が1以下という条件（以下、条件Balという）”
─ 高さ差が $\pm 1$ 以内なら平衡、 $\pm 2$ になった時だけ回転が必要です。
図7の1行目
h1 ← height(t.left) − height(t.right)
で左右の高さ差を求めています。
2分探索木の不均衡を判定するので、 “左右の部分木の高さの差が2になるノード”
に一致するケースを検出する条件は
h1 が 2 と等しいまたは h1 が -2 と等しいです。
よって
ウ：h1が2と等しい
オ：h1が-2と等しい
回転方向の分岐
(1) 左部分木が高過ぎるときは右回転、 (2) 右部分木が高過ぎるときは左回転。
ただし“Uの右側の部分木の方がUの左側の部分木よりも高い場合は、先にUを根とする部分木に対して左回転を行う。”
これはＬＬ／ＬＲ判定のため、具体的には
height(t.left.right) - height(t.left.left) の符号で判断します。
よって
エ：height(t.left.right) - height(t.left.left)
右部分木が高過ぎる場合の対称操作
“Vの左側の部分木の方がVの右側の部分木よりも高い場合は、先にVを根とする部分木に対して右回転を行う。”
判定式は
height(t.right.left) - height(t.right.right)
なので
カ：height(t.right.left) - height(t.right.right)

以上から模範解答は
ウ：h1が2と等しい
エ：height(t.left.right) - height(t.left.left)
オ：h1が-2と等しい
カ：height(t.right.left) - height(t.right.right)

誤りやすいポイント

h1 と h2・h3 を混同して左右を逆に書く。height(t.left) − height(t.right) の符号が正なら“左が高い”です。
“高さ差が2” を “高さ差が-2” と同一視して単一の if にまとめてしまう。図7は左右で別々のブロックを持ちます。
子部分木の内外判定を簡易に != 0 と書くミス。ＬＲ／ＲＬケースは “どちらが高いか” を調べるため符号を見ます。
rotateL と rotateR の呼出し位置。誤って二重回転を行うと平衡条件が崩れます。

FAQ

Q: なぜ高さ差が3になるケースを考慮しないのですか？
A: 条件Balを保っていれば、新規挿入で差が広がるのは最大でも2です。3以上になる前に必ず balance が呼ばれるためです。

Q: h2・h3 の値が 0 のときに回転を入れ替える必要は？
A: 0 は左右が同じ高さを意味し、外側が高いＬＬ／ＲＲ型になります。この場合は単一回転で解決できるので追加の内側回転は不要です。

Q: 回転関数の戻り値を必ず親ノードに再代入する理由は？
A: 回転で部分木の根が変わるため、親からの参照を更新しないと木が分断されてしまいます。balance は常に return t で新しい根を返します。

関連キーワード: 2分探索木、平衡木、回転操作、高さ差、時間計算量

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

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

　insertB(insertB(r, 4), 8)

模範解答

（図を参照）

解説

解答の論理構成

初期状態の把握

根を参照する変数 “r” は【問題文】の「図1」に示される 2 分探索木を指しています。すなわち

  6
/   \

3 9 /
1 5

1回目の呼出し：insertB(r, 4)
1. 探索経路
  - 4 は “6” より小さい → 左部分木へ
  - 4 は “3” より大きい → 右部分木へ
  - “5” より小さい → 5.left が NULL なので挿入
2. 部分木のアンバランス検出
  - 挿入直後、根 “6” で左部分木の高さが 3、右部分木の高さが 1 となり差が 2
  - balance 手順(1) 【問題文】「Tの左側の部分木の高さがTの右側の部分木の高さより2大きい場合」に該当
3. 二段階回転
  - “U”＝3 の右部分木(高さ 2)＞左部分木(高さ 1) なので先に rotateL(3)
```
  5
/   \
```
    3 (null) /
    1 4
  - 続いて rotateR(6) を実行
```
  5
/   \
```
    3 6 / \
    1 4 9
4. これで条件Bal（左右部分木の高さ差≦1）が回復
2回目の呼出し：insertB(… 、8)
1. 探索経路
  - 8 は “5” より大きい → 右部分木 “6” へ
  - 8 は “6” より大きい → 右部分木 “9” へ
  - “9” より小さい → 9.left が NULL なので挿入
2. 部分木のアンバランス検出
  - ノード “6” で右部分木の高さが 2、左部分木 0 → 差は 2
  - balance 手順(2) 【問題文】「Tの右側の部分木の高さがTの左側の部分木の高さより2大きい場合」に該当
3. 二段階回転
  - “V”＝9 の左部分木(高さ 1)＞右部分木(高さ 0) なので先に rotateR(9)
    
    8
    9
  - 続いて rotateL(6) を実行
```
  8
/   \
```
    6 9
4. 全体像
```
    5
  /   \
 3     8
/ \   / \
```
  1 4 6 9

以上が模範解答図と一致します。回転は常に「高さ差＝2」を検知した親ノードを軸に発生し、その直下の部分木の形によって単回転か二重回転（左→右／右→左）の別が決まる点が要諦です。

誤りやすいポイント

回転の方向を逆に適用する
- 左右の高さ差を見た瞬間に「左が高いなら右回転」と機械的に覚えていると、“U” や “V” の二重回転判定を忘れがちです。
insertB と従来の insert を混同する
- insert は回転を行わないので高さ差 2 のまま終了します。必ず「挿入後に balance を呼ぶ」のが insertB の仕様です。
高さの数え方
- 葉を高さ 1 とするか 0 とするかを曖昧にすると、どこで差が 2 になるか勘違いします。本問では height(NULL)=0 として実装されています。

FAQ

Q: 二重回転を判定する基準は何ですか？
A: balance 手順では「高さ差が 2 になった親ノード T の高い側の子ノード（左なら U、右なら V）を調べ、その子の“内側”部分木の高さが“外側”より大きいとき二重回転」と定義されています。これは回転後に必ず高さ差が 1 以内に収まることを保証するためです。

Q: 挿入順序が違えば回転回数も変わりますか？
A: はい。平衡2分探索木（AVL木）の回転回数は挿入キー列に依存します。同じ集合でも順序が異なれば単回転だけで済む場合や二重回転が必要になる場合があります。

Q: rotateL と rotateR は部分木ポインタ以外に何か更新が必要ですか？
A: 本問の簡易実装では高さを逐次計算するため、回転時に高さフィールドを持っていません。しかし実装効率を上げる場合は各ノードに高さをキャッシュし、回転のたびにそのフィールドを更新します。

関連キーワード: 2分探索木、AVL木、回転操作、最悪時間計算量、高さバランス

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

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

模範解答

log n

解説

解答の論理構成

性質の整理
【問題文】には、平衡状態を次のように定義しています。
――「全てのノードについて左右の部分木の高さの差が1以下という条件（以下、条件Balという）」
条件Balを満たす木は AVL 木と同等であり、ノード数を $n$ とすると高さ $h$ が $O (lo g n)$ に抑えられることが知られています。
高さの上界
条件Bal の下で高さ $h$ の木に含まれる最小ノード数 $N (h)$ は
$N (h) = N (h - 1) + N (h - 2) + 1$
というフィボナッチ型の漸化式に従い、 $N (h) \geq F_{h + 2} - 1$
（ $F$ はフィボナッチ数列）。フィボナッチ数は指数関数的に増えるため
$h \leq c lo g_{2} (n + 1)$
が導け、よって高さは $O (lo g n)$ です。
挿入処理の流れ
【問題文】は次のように示しています。
――「条件Balを満たすノードの総数がn個の2分探索木に対して関数insertBを実行した場合、挿入に掛かる最悪時間計算量はO(キ)となる。」
挿入は
・通常の探索経路を下りながらノードを追加
・帰りがけに各親で balance を実行
という二段構えです。
計算量評価
・探索＋再帰呼出し回数＝木の高さ $h = O (lo g n)$
・各ノードでの処理は、【問題文】図7の balance から分かる通り比較・代入・回転（rotateR、rotateL）など定数回。
・【問題文】が「関数heightの処理時間は無視できる」と指示。
したがって総コストは $O (h) = O (lo g n)$ 。
結論
キに入る語は「log n」です。

誤りやすいポイント

「アンバランスな場合は回転が多発するので $O (n)$ になる」と誤解する
回転はパス上で高々2回／ノード、パス長自体が $O (lo g n)$ 。
height の計算コストを二重に数えてしまう
問題文が「無視できるものとする」と明示。
条件Bal と「完全二分木」を混同し、 $O (lo g n)$ ではなく $O (lo g_{2} n)$ などと書く
ビッグオー記法では底は省略可能なので「log n」で良い。

FAQ

Q: 回転操作は最悪で何回呼ばれますか？
A: 1挿入につきパス上の各ノードで高々2回、パス長が

O (lo g n)

なので

O (lo g n)

回以内です。

Q: balance が左右の高さを毎回計算すると遅くなりませんか？
A: 本問では height の計算を無視できる前提ですが、実装では各ノードに高さをキャッシュしておけば計算量は変わりません。

Q: 「log n」と「lg n」「log₂ n」は同じですか？
A: ビッグオー記法では定数倍を無視するため、底が2でもｅでも意味は同じです。本問の解答欄には「log n」と書くのが適切です。

関連キーワード: 2分探索木、平衡木、回転操作、時間計算量、再帰アルゴリズム

\ せっかくなら /

応用情報技術者を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！

応用情報技術者 2023年 秋期 午後 問03

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

.css-epvm6{white-space:nowrap;}設問1：

模範解答

解説

解答の論理構成

誤りやすいポイント

FAQ

設問2：.css-1hn4tij{display:inline;overflow-wrap:anywhere;word-break:break-word;min-width:0px;}〔回転操作を利用した平衡2分探索木の構成〕について答えよ。

模範解答

解説

解答の論理構成

誤りやすいポイント

FAQ

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

模範解答

解説

解答の論理構成

誤りやすいポイント

FAQ

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

模範解答

解説

解答の論理構成

誤りやすいポイント

FAQ

応用情報技術者 2023年秋期午後問03

設問1：

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