戦国IT - 情報処理技術者試験の過去問対策サイト
ブログお知らせお問い合わせ料金プラン

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

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

　 　2分探索木とは、全てのノードNに対して、次の条件が成立している2分木のことである。 　・Nの左部分木にある全てのノードのキー値は、Nのキー値よりも小さい。 　・Nの右部分木にある全てのノードのキー値は、Nのキー値よりも大きい。 　ここで、ノードのキー値は自然数で重複しないものとする。2分探索木の例を図1に示す。図中の数はキー値を表している。
応用情報技術者試験（平成27年度 秋期 午後 問03 図01） ↩設問1 ↩設問4
　2分探索木を実現するために、ノードを表す構造体Nodeを定義する。構造体Nodeの構成要素を表1に示す。
応用情報技術者試験（平成27年度 秋期 午後 問03 表01）
　構造体の実体を生成するためには、次のように書く。 　new Node(key) 　生成した構造体への参照が戻り値となる。構造体の構成要素のうち、keyは引数keyの値で初期化され、leftとrightはnullで初期化される。 　変数pが参照するノードをノードpという。ノードを参照する変数からそのノードの構成要素へのアクセスには“.”を用いる。例えば、ノードpのキー値には、p.keyでアクセスできる。 　なお、変数pの値がnullの場合、木は空である。 　
〔2分探索木でのノードの探索〕 　与えられたキー値をもつノードを探索する場合、親から子の方向へ、木を順次たどりながら探索を行う。 　探索する2分探索木にノードがない場合は、目的のノードが見つからず、探索は失敗と判断して終了する。探索する2分探索木にノードがある場合は、与えられたキー値と木の根のキー値を比較し、等しければ、目的のノードが見つかったので探索は成功と判断して終了する。与えられたキー値の方が小さければ左部分木に、大きければ右部分木に移動する。移動先の部分木でも同様に探索を続ける。 　この手順によって探索を行う関数searchのプログラムを図2に示す。このプログラムでは、探索が成功した場合は見つかったノードへの参照を返し、失敗した場合はnullを返す。
応用情報技術者試験（平成27年度 秋期 午後 問03 図02） ↩設問2
〔2分探索木へのノードの挿入〕 　2分探索木にノードを挿入する場合、探索と同様に、親から子の方向へ、木を順次たどりながら、適切な位置にノードを挿入する。 　挿入する2分探索木にノードがない場合は、挿入するキー値のノードを作成する。挿入する2分探索木にノードがある場合は、挿入するキー値と木の根のキー値を比較し、挿入するキー値の方が小さければ左部分木に、大きければ右部分木に移動する。移動先の部分木でも同様の処理を続ける。 　この手順によって挿入を行う関数addNodeのプログラムを図3に示す。このプログラムでは、挿入の結果として得られた2分探索木の根のノードへの参照を返す。ただし、このプログラムは、挿入するキー値と同じキー値をもつノードが2分探索木に既に存在するときは何もしない。
応用情報技術者試験（平成27年度 秋期 午後 問03 図03）
〔2分探索木からのノードの削除〕 　2分探索木から、あるキー値をもつノードを削除する場合、次の(1)～(3)の手順を行う。
　(1) 2分探索木にノードがない場合は、何もしないで処理を終了する。 　(2) 削除するキー値と木の根のキー値を比較し、削除するキー値の方が小さければ左部分木に、大きければ右部分木に移動する。移動先の部分木でも同様の処理を続ける。 　(3) 削除するキー値と木の根のキー値が等しい場合、削除するキー値をもつノードを削除するため、次の(3-1)～(3-3)を実行する。 　(3-1) 削除するノードが子ノードをもたない場合、そのノードを削除する。 　(3-2) 削除するノードが子ノードを一つだけもつ場合、削除するノードの位置にその子ノードを置く。 　(3-3) 削除するノードが左右両方に子ノードをもつ場合、削除するノードの左部分木の中で最大のキー値をもつノードを左部分木から取り除き、削除するノードの位置に置く。 　 　この手順を使って2分探索木からノードの削除を行う関数removeNodeのプログラムを図4に示す。このプログラムでは、削除した後の2分探索木の根のノードへの参照を返す。ただし、このプログラムは、削除するキー値をもつノードが2分探索木に存在しないときは何もしない。 　図4中の関数extractMaxNodeは、引数で指定されたノードを根とする2分探索木の中で最大のキー値をもつノードを木から削除し、削除されたノードへの参照を大域変数extractedNodeに設定した上で、削除した後の2分探索木の根のノードへの参照を返す。関数extractMaxNodeのプログラムを図5に示す。
応用情報技術者試験（平成27年度 秋期 午後 問03 図04）
応用情報技術者試験（平成27年度 秋期 午後 問03 図05）
〔2分探索木の計算量〕 　2分探索木における計算量は、木の高さに依存する。図2の関数searchを使ってn個のノードから成る2分探索木を探索する場合、想定される最大の計算量は、O(ク)である。木構造が完全2分木であれば、その計算量は最大でもO(ケ)である。

設問1：

問題文を見る
図1中のアに入れる適切な数を答えよ。

模範解答

ア：11

解説

解答の論理構成

  1. まず2分探索木の定義より、 「Nの左部分木にある全てのノードのキー値は、Nのキー値よりも小さい。」
    「Nの右部分木にある全てのノードのキー値は、Nのキー値よりも大きい。」
    と【問題文】に明記されています。
  2. 図1では、根のキー値が「15」、その左部分木に「8」、さらに「10」「12」が右方向に並び、その子として［ア］が配置されています。
  3. 左部分木に属する時点で、［ア］は「15」より小さくなければなりません。
  4. 「10」の右部分木に位置するため、「10」より大きい必要があります。
  5. 「12」の左子（左部分木）であるため、「12」より小さくなければなりません。
  6. 以上より成り立つ不等式は
    10 ＜ ［ア］ ＜ 12
    です。キー値は自然数で重複しない条件から取り得る値は唯一「11」となります。
したがって
ア：11

誤りやすいポイント

  • 「左右」を取り違え、［ア］を「12」の右子と勘違いすると13や14を選びやすいです。
  • ルート「15」より小さいという制約を見落とし、25未満なら何でも良いと誤解するケースがあります。
  • 自然数で重複しないという前提を忘れ、既に木に存在する値を候補に挙げてしまうミスが散見されます。

FAQ

Q: もし「12」の右側にもう一つノードを追加するなら、どの値が入りますか？
A: 右部分木なので「12」より大きく、かつ「15」より小さい値のうち未使用のもの、例えば13や14が適切です。
Q: ルートが「15」でなかったら［ア］は変わりますか？
A: 左部分木か右部分木かで制約が変わるため、ルート値が変わると［ア］に許される範囲も変化します。
Q: 同じキー値が入るケースを考えなくてよいのはなぜですか？
A: 【問題文】で「ノードのキー値は自然数で重複しないものとする」と明示されており、重複キーは発生しません。
関連キーワード: 2分探索木、探索アルゴリズム、部分木、ノードキー、木構造

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

この設問をAIに質問する

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

設問2：

問題文を見る
図2〜4中のイ〜キに入れる適切な字句を答えよ。

模範解答

イ：kがp.keyより小さい ウ：new Node(k) エ：return p オ：p.left カ：p.right キ：p ← r

解説

解答の論理構成

  1. イ
    【問題文】には「与えられたキー値の方が小さければ左部分木に、大きければ右部分木に移動する。」とあります。
    左部分木へ進む条件ですから、search／addNodeいずれも
    「kがp.keyより小さい」が成立する場合にp.leftへ進みます。
    よって イ は
    kがp.keyより小さい。
  2. ウ
    【問題文】には「構造体の実体を生成するためには、次のように書く。 new Node(key)」と明記されています。
    空木に対して最初のノードを作成する行なので、 new Node(k) が入ります。
  3. エ
    addNodeは「挿入の結果として得られた2分探索木の根のノードへの参照を返す」と説明されています。
    挿入処理後、局所変数pがその根を指していますから
    return p が正しい返却になります。
  4. オ と カ
    removeNodeで「削除するノードが子ノードを一つだけもつ場合」の処理です。
    • 右部分木を残すケースは「左部分木がnull」なので p.left がnull
    • 左部分木を残すケースは「右部分木がnull」なので p.right がnull
      したがって
      オ：p.left
      カ：p.right
  5. キ
    子ノードを二つもつ場合、【問題文】の（3-3）に従い「左部分木の中で最大のキー値をもつノードを…削除するノードの位置に置く」とあります。
    extractMaxNodeで取り除いたノードをrに保持し、左右ポインタを設定した後、pをそのrに置き換えれば完成です。
    よって p ← r。

誤りやすいポイント

  • 左右判定の条件を「≦」「≧」と書いてしまう
    2分探索木は「重複しない」ので、等しい場合は探索成功・挿入しない。
  • オ・カ を逆に書く
    “片方がnullなら残っている方を昇格させる”という基本を取り違えやすい。
  • キ を r ← p と逆にしてしまう
    置き換えるのは削除対象pであり、抽出したrではない点に注意。

FAQ

Q: 条件式を「k < p.key」と「kがp.keyより小さい」のどちらで書いても良いですか？
A: 本試験では日本語による擬似コード表記に合わせ「kがp.keyより小さい」と書くのが無難です。
Q: new Node(k) で生成したノードのleft／rightは初期化が必要ですか？
A: 【問題文】に「leftとrightはnullで初期化される」とあるので追加の代入は不要です。
Q: 削除で左右両方に子があるとき、なぜ“左部分木の最大値”を使うのでしょう？
A: 最大値は削除ノードより小さく、かつ右部分木のキーよりは小さいため、置き換えても2分探索木の順序が保てるからです。
関連キーワード: 2分探索木、再帰処理、ノード削除、擬似コード、ポインタ参照

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

この設問をAIに質問する

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

設問3：

問題文を見る
本文中のク、ケに入れる適切な字句を答えよ。

模範解答

ク：n ケ：log n

解説

解答の論理構成

  1. 問題文では「2分探素木における計算量は、木の高さに依存する」と明言されています。
    つまり、探索の比較回数 ≒ 木を下る回数 ≒ 木の高さです。
  2. さらに「図2の関数searchを使ってn個のノードから成る2分探索木を探索する場合、想定される最大の計算量は、O(ク)である」とあります。
    ・最悪の場合とは、木が片側にのみ伸びて“ひと続きの鎖”になるケースです。
    ・このとき高さはn − 1、比較回数はnオーダーなので 。
    よって ク には n が入ります。
  3. 次に「木構造が完全2分木であれば、その計算量は最大でもO(ケ)である」とあります。
    ・完全2分木では高さが 程度まで抑えられます。
    ・したがって比較回数は 。
    よって ケ には logn が入ります。
  4. 以上より
    ク：n
    ケ：logn

誤りやすいポイント

  • 「完全2分木」と「平衡木」を混同し、平均計算量を考えてしまう。問題文は“最大の計算量”です。
  • 対数の底を意識し過ぎてlog₂nやlog₁₀nと書きたくなるが、計算量記法では底は省略可。解答欄には「logn」と素直に書くのが安全です。
  • 最悪計算量を と誤記するケース。探索では一度に1本のパスしか通らないため、二重ループのような にはなりません。

FAQ

Q: “鎖状態”の木は具体的にどのような挿入順で発生しますか?
A: 昇順または降順にキーを連続挿入すると、常に右（または左）子に追加され続け、1本の鎖になります。
Q: 「完全2分木」と「平衡2分探索木」は同義ですか?
A: 厳密には異なりますが、計算量評価の観点ではどちらも高さが に抑えられる点が共通しています。
Q: 底が違う対数同士を比較するときはどうすればよいですか?
A: なので、定数倍が付くだけでオーダーは変わりません。したがって とまとめて表記します。
関連キーワード: BinarySearchTree, 時間計算量、最悪計算量、完全2分木、木の高さ

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

この設問をAIに質問する

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

設問4：

問題文を見る
次の順でキー値の挿入と削除を行った後でノードqを根とする2分探索木を答えよ。2分探索木は、図1の例に倣って表現すること。
応用情報技術者試験（平成27年度 秋期 午後 問03 設問04）

模範解答

（図を参照）
応用情報技術者試験（平成27年度 秋期 午後 問03 設問04 解答）

解説

解答の論理構成

  1. 初期状態
    • 【問題文】にあるとおり「変数 **pの値がnullの場合、木は空である。」
    • q ← null で空木からスタートします。
  2. 挿入処理（addNode）
    • 挿入アルゴリズムは【問題文】の説明通り
      「挿入する **2分探索木にノードがない場合は、挿入するキー値のノードを作成する。」
      「挿入するキー値と木の根のキー値を比較し、… 左部分木 / 右部分木に移動する。」
    • これを順番に適用すると
    挿入キー挿入後の部分的な木構造（根→子の順）根ノード
    555
    25 → 2(L)5
    75 → 2(L), 7(R)5
    15 → 2 → 1(L)5
    85 → … , 7 → 8(R)5
    42 → 4(R) を追加5
    34 → 3(L) を追加5
    128 → 12(R) を追加5
    （L: left child, R: right child）
    ここまでで高さ３の2分探索木が完成しています。
  3. 削除処理（removeNode）
    • 削除アルゴリズムは【問題文】「（3-1）〜（3-3）」の規定。
      特に二つの子をもつ場合は
      「削除するノードの左部分木の中で最大のキー値をもつノードを… 削除するノードの位置に置く。」
    ① removeNode(5, q)
    • キー 5 は左右2子をもつので (3-3) が適用。
    • 左部分木 {2,1,4,3} の最大キーは 4。
    • 4 をextractMaxNodeで取り除き、そのノードを根に据えます。
    • 結果：根が 4 になり、左部分木は {2,1,3}、右部分木は {7,8,12}。
    ② removeNode(7, q)
    • 現在の根は 4。キー 7 は右部分木側。
    • ノード 7 は右に一子 (8) のみで左子なしなので (3-2) が適用。
    • 7 の位置にその子 8 を昇格させます。
  4. 最終結果
    • 根：4
    • 左部分木：2 を根とし、左に 1、右に 3
    • 右部分木：8 を根とし、右に 12
      これが模範解答図と一致します。

誤りやすいポイント

  • 「二つの子をもつノード削除」で“左部分木の最大”か“右部分木の最小”かを混同しがち。問題文は明確に「左部分木の中で最大のキー値」と記載。
  • removeNode適用後の根の交代を忘れ、木全体の根を更新せずに描いてしまうミス。
  • addNodeで重複キーが来たとき「何もしない」仕様を失念し、誤って木構造が崩れる例を描いてしまう。

FAQ

Q: 子が一つしかないノードを削除する場合、左右どちらの子でも同じ処理ですか？
A: はい。【問題文】「削除するノードがノードを一つだけもつ場合、削除するノードの位置にその子ノードを置く。」とあり、左子でも右子でも同様に置換します。
Q: 左部分木の最大キー取得にextractMaxNodeを使う理由は？
A: 最大キーは常に最右端にあり、extractMaxNodeは【問題文】「最大のキー値をもつノードを木から削除し…返す」関数として再利用できるため、重複実装を避けコードを簡潔にできます。
Q: 高さバランスは考慮しなくて良いのですか？
A: 本問は平衡木ではなく通常の2分探索木です。【問題文】にも平衡化処理は示されておらず、計算量も「木の高さに依存する」とだけ記述されています。
関連キーワード: 2分探索木, ノード削除, 部分木, 計算量, 再帰処理

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

この設問をAIに質問する

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

戦国ITクイズ機能

\ せっかくなら /

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

クイズ画面へ遷移する→

すぐに利用可能！

©︎2026 情報処理技術者試験対策アプリ

このサイトについてブログプライバシーポリシー利用規約特商法表記開発者について