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

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

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

↩設問2(2)

　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は、変形の結果として得られた木の根への参照を返す。

↩設問2(1) ↩設問2(3)

　条件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分探索木、ビッグオー記法、平衡木、回転操作、高さ解析

解説を読んでも分からないところは、AIに質問できます。この問題の本文と解説をふまえて答えます。

この設問をAIに質問する

クイズモードで開きます（AIへの質問は無料の会員登録で使えます）

設問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分探索木、平衡木、回転操作、高さ差、時間計算量

解説を読んでも分からないところは、AIに質問できます。この問題の本文と解説をふまえて答えます。

この設問をAIに質問する

クイズモードで開きます（AIへの質問は無料の会員登録で使えます）

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

問題文を見る

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

　insertB(insertB(r, 4), 8)

模範解答

（図を参照）

解説

（図を参照）

解答の論理構成

初期状態（図1）
図1 は根が 6、6 の左の子が 3、右の子が 9 で、3 の左の子が 1、右の子が 5 の 2分探索木です。全てのノードで左右の部分木の高さの差は 1 以下なので、条件Bal を満たしています。
1回目の呼出し insertB(r, 4)
(1) 挿入
図8 の insertB は、根から順にキー値を比べて空のノードの位置に追加します。4 は 6 より小さいので左へ、3 より大きいので右へ、5 より小さいので左へ進み、5 の左の子として 4 を追加します。
(2) balance による変形
insertB は再帰から戻るたびに、挿入したノードから根の方向へ順に balance を適用します。
・5：左の高さ 1、右の高さ 0 → 差は 1 なので変形しない
・3：左の部分木（1）の高さ 1、右の部分木（5 と 4）の高さ 2 → 差は 1 なので変形しない
・6：左の部分木（3 以下）の高さ 3、右の部分木（9）の高さ 1 → 左が 2 大きい
本文の手順(1)に当たります。6 の左の子 U は 3 で、3 の右側の部分木の方が高いので、先に 3 を根とする部分木を左回転し、5 が 3 の位置に上がります（5 の左に 3、3 の左に 1、右に 4）。続いて 6 を根とする木を右回転します。
結果は、根が 5、左の子が 3（子は 1 と 4）、右の子が 6（右の子が 9）になります。
2回目の呼出し insertB(…, 8)
(1) 挿入
8 は 5 より大きいので右へ、6 より大きいので右へ、9 より小さいので左へ進み、9 の左の子として 8 を追加します。8 は図1 の木にないので、挿入されます。
(2) balance による変形
・9：左の高さ 1、右の高さ 0 → 変形しない
・6：左の高さ 0、右の部分木（9 と 8）の高さ 2 → 右が 2 大きい
本文の手順(2)に当たります。6 の右の子 V は 9 で、9 の左側の部分木の方が高いので、先に 9 を根とする部分木を右回転し、8 が 9 の位置に上がります（8 の右に 9）。続いて 6 を根とする部分木を左回転し、8 の左に 6、右に 9 が付きます。
・5：左の部分木（3 以下）の高さ 2、右の部分木（8 以下）の高さ 2 → 変形しない
生成された木
```
    5
   / \
  3   8
 / \ / \
1  4 6  9
```
全てのノードで左右の高さの差が 1 以下になっており、解答例の図と一致します。

誤りやすいポイント

図1 の根を 6 ではなく別のノードと読み違える。最初の木を正しく読み取ることが出発点です。
回転を根だけで判定してしまう。balance は挿入位置から根に向かって、途中の全てのノードに適用されます。
二重回転を見落とす。6 での変形では、左の子 3 の右側が高いので、右回転の前に 3 の左回転が必要です。8 の挿入でも、右の子 9 の左側が高いので、左回転の前に 9 の右回転が必要です。
高さの数え方を誤る。本問の判定は左右の部分木の高さの差だけを見るので、数え方の基準（空の木を 0 とするか −1 とするか）がそろっていれば結果は変わりません。

FAQ

Q: 二重回転が必要なのはどんなときですか？
A: 高い側の子の、さらに内側（左の子なら右側、右の子なら左側）の部分木が高いときです。このとき一度の回転では高さの差が解消しないので、図7 のように先に子を回転してから親を回転します。

Q: 平衡にしたことで探索の計算量はどうなりますか？
A: 条件Bal を満たす木は高さが O(log n) に抑えられるので、探索や挿入の最悪時間計算量も O(log n) になります。

関連キーワード: 2分探索木、AVL木、回転操作、二重回転、平衡条件

解説を読んでも分からないところは、AIに質問できます。この問題の本文と解説をふまえて答えます。

この設問をAIに質問する

クイズモードで開きます（AIへの質問は無料の会員登録で使えます）

設問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分探索木、平衡木、回転操作、時間計算量、再帰アルゴリズム

解説を読んでも分からないところは、AIに質問できます。この問題の本文と解説をふまえて答えます。

この設問をAIに質問する

クイズモードで開きます（AIへの質問は無料の会員登録で使えます）

\ せっかくなら /

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

クイズ画面へ遷移する→

すぐに利用可能！

応用情報技術者 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分探索木の構成〕について答えよ。