問題プレビューID: ea0b7fd3応用情報技術者試験 2023年(令和5年度)秋期 午後

問 3
応用情報技術者試験 2023年(令和5年度)秋期 午後

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

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

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

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

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

図1 2分探索木の例

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

表1 構造体Nodeの構成要素

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

構造体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は,得られた木の根への参照を返す。

図2 探索を行う関数searchのプログラム

// tが参照するノードを根とする木から
// キー値がkであるノードを探索する
function search(t, k)
  if(tがNULLと等しい)
    return NULL
  elseif(t.keyがkと等しい)
    return t
  elseif(t.keyがkより大きい)
    return search(t.left, k)
  else // t.keyがkより小さい場合
    return search(t.right, k)
  endif
endfunction

図3 挿入を行う関数insertのプログラム

// 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

関数searchを用いてノードの総数がn個の2分探索木を探索するとき,探索に掛かる最悪の場合の時間計算量(以下,最悪時間計算量という)はO(O([ア]))である。これは葉を除く全てのノードについて左右のどちらかにだけ子ノードが存在する場合である。一方で,葉を除く全てのノードに左右両方の子ノードが存在し,また,全ての葉の深さが等しい完全な2分探索木であれば,最悪時間計算量はO(O([イ]))となる。したがって,高速に探索するためには,なるべく左右両方の子ノードが存在するように配置して,高さができるだけ低くなるように構成した木であることが望ましい。このような木のことを平衡2分探索木という。

〔2分探索木における回転操作〕

2分探索木中のノードXとXの左側の子ノードYについて,XをYの右側の子に,元のYの右側の部分木をXの左側の部分木にする変形操作を右回転といい,逆の操作を左回転という。回転操作後も2分探索木の条件は維持される。木の回転の様子を図4に示す。ここで,t1〜t3は部分木を表している。また,根からt1〜t3の最も深いノードまでの深さを,図4(a)ではd1〜d3,図4(b)ではd1'〜d3'でそれぞれ表している。ここで,d1'=d1−1,d2'=d2,d3'=d3+1,が成り立つ。

図4 木の回転の様子

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

図5 右回転を行う関数rotateRのプログラム

// tが参照するノードを根とする木に対して
// 右回転を行う
function rotateR(t)
  a ← t.left
  b ← a.right
  a.right ← t
  t.left ← b
  return a
endfunction

図6 左回転を行う関数rotateLのプログラム

// tが参照するノードを根とする木に対して
// 左回転を行う
function rotateL(t)
  a ← t.right
  b ← a.left
  a.left ← t
  t.right ← b
  return a
endfunction

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

図7 関数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

図8 関数insertBのプログラム

// tが参照するノードを根とする木に
// キー値がkであるノードを挿入する
function insertB(t, k)
  if(tがNULLと等しい)
    t ← new Node(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)  // 追加
  return t
endfunction

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

設問1

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

設問2

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

(1) 図7中の[ウ]〜[カ]に入れる適切な字句を答えよ。

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

insertB(insertB(r, 4), 8)

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

模範解答

設問1 ア nn,イ log⁡n\log n

設問2 (1) ウ h1が2と等しい,エ height(t.left.right) - height(t.left.left),オ h1が-2と等しい,カ height(t.right.left) - height(t.right.right) (2) 根5、左の子3(左の子1、右の子4)、右の子8(左の子6、右の子9) (3) log⁡n\log n

解説

2分探索木(AVL木)を題材に,木構造,再帰的アルゴリズム,計算量についての理解を問う。

設問1のアは,鎖状に偏った木では探索が線形走査になるのでO(n)O(n)である。イは,完全な2分探索木では高さがlog⁡n\log nのオーダになるのでO(log⁡n)O(\log n)である。

設問2(1)では,図7の関数balanceの空欄を問う。[ウ]は左部分木が2高い場合の条件であり,h1が2と等しいことである。[エ]はUの右部分木と左部分木の高さの差であり,height(t.left.right) - height(t.left.left)である。[オ]は右部分木が2高い場合の条件であり,h1が-2と等しいことである。[カ]はVの左部分木と右部分木の高さの差であり,height(t.right.left) - height(t.right.right)である。(2)では,図1の木に4と8を挿入しても条件Balは保たれるので,根5、左の子3(左の子1、右の子4)、右の子8(左の子6、右の子9)の木になる。(3)の[キ]は,平衡が保たれるので挿入の最悪時間計算量はlog⁡n\log nのオーダである。

関連問題

本文が同じ・似ている問題を表示しています