基本情報技術者試験とは
基本情報技術者試験は、情報処理推進機構（IPA）が実施し、「情報処理の促進に関する法律」に基づき経済産業省が認定する国家試験である。
ITエンジニアとしてキャリアをスタートする方のIT基礎力を問う試験で、「ITエンジニアの登竜門」とも言われる。
科目Aと科目Bの両科目で合格点を取らなければ、基本情報技術者試験の合格とはならない。
今回は、科目Aのサンプル問題を題材に、木構造の図を目で追って正解を探すだけでなく、Pythonで実際に木を組み立て、条件を満たしているかをプログラムで判定するというやり方で理解を深める。
なお、この記事で使用するコードは、学習用リポジトリ pc-labo-fe-exam-python の 02_2bun_tansaku_gi フォルダにまとめている。
まずは、基本情報技術者試験（科目A）のサンプル問題にチャレンジしてみよう。
サンプル問題（科目A）
問５
2 分探索木になっている2 分木はどれか。
正解：イ
木構造とは
木構造（きこうぞう）とは、階層構造を持つデータ構造である。
木構造は植物の木を逆さにしたような形をしている。
下の左図の〇で表される箇所を「節」という。節の中で、最上位の節を「根」と呼び、末端の節を「葉」と呼ぶ。
木構造の節同士には親子関係がある。分岐元を「親」、分岐先を「子」という。（右図参照）
木構造の中でも、親が0から2個の子を持つ木構造を2分木という。
2分探索木
2分木の中で、親子の値が次の関係になっているものを「2分探索木」という。
左の子孫 ＜ 親 ＜ 右の子孫
※子孫とは、親よりも下にあるデータという意味である。
設問で検討してみると、
この要件を満たしているのは「イ」となる。
左から順に 10、14、16、17、18、19 となっている。
選択肢イの節を左から順に並べると 10、14、16、17、18、19 となり、昇順に並んでいる。これが「2分探索木になっている」と判定できる理由である。
つまり、木を左から順（中間順）にたどって値を並べたとき、それが昇順になっていれば2分探索木だと判定できる。この考え方をそのままPythonのコードにしてみよう。
Pythonでつくって確かめてみよう
選択肢イと同じ値（10, 14, 16, 17, 18, 19）を持つ木をPythonで組み立て、実際に「2分探索木の条件を満たしているか」を判定するプログラムをつくってみよう。
class Node:
"""2分木の1つの節を表すクラス"""
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def inorder(node, result=None):
"""中間順（in-order）で節の値をリストに集める"""
if result is None:
result = []
if node is None:
return result
inorder(node.left, result)
result.append(node.value) # 親を「左をたどり終えたあと」に記録する
inorder(node.right, result)
return result
def is_bst(node, min_value=float("-inf"), max_value=float("inf")):
"""各節が「左の子孫 ＜ 親 ＜ 右の子孫」を満たしているかを再帰的に確認する"""
if node is None:
return True
if not (min_value < node.value < max_value):
return False
return (
is_bst(node.left, min_value, node.value)
and is_bst(node.right, node.value, max_value)
)
def check(name, root):
values = inorder(root)
print(f"[{name}] 中間順で並べると: {values}")
print(f"[{name}] 2分探索木か？ -> {is_bst(root)}")
print()
# 選択肢イの木をそのままコードで再現する
valid_tree = Node(
17,
left=Node(14, left=Node(10), right=Node(16)),
right=Node(19, left=Node(18)),
)
# 条件を満たさない木の例（14の右に、本来もっと右側にあるべき16を置いてしまっている）
invalid_tree = Node(
15,
left=Node(14, left=Node(10), right=Node(16)),
right=Node(19),
)
check("2分探索木の条件を満たす木", valid_tree)
check("条件を満たさない木", invalid_tree)実行結果
[2分探索木の条件を満たす木] 中間順で並べると: [10, 14, 16, 17, 18, 19]
[2分探索木の条件を満たす木] 2分探索木か？ -> True
[条件を満たさない木] 中間順で並べると: [10, 14, 16, 15, 19]
[条件を満たさない木] 2分探索木か？ -> Falseinorder() は「左の子孫をすべてたどってから親を記録し、そのあと右の子孫をたどる」という順番で値を集める関数である。木が2分探索木になっていれば、この順番で集めた値は必ず昇順になる。1つ目の木では中間順の結果が [10, 14, 16, 17, 18, 19] と昇順になっており、選択肢イと同じ並びが再現できていることが確認できる。
is_bst() は、各節について「今見ている節の値が、許される範囲（min_value より大きく max_value より小さい）に収まっているか」を再帰的に確認する関数である。左の子には「上限がその節の値」、右の子には「下限がその節の値」という条件を渡していくことで、木全体で「左の子孫 ＜ 親 ＜ 右の子孫」が保たれているかを厳密に判定できる。
2つ目の木では、節15の右部分木にある14の右に16を置いてしまっているため、16が本来満たすべき範囲（15より大きい必要がある）を満たさず、is_bst() が False を返している。中間順の結果も [10, 14, 16, 15, 19] と、16の後に15が来てしまい昇順が崩れていることが目で見てもわかる。
まとめ
- 2分探索木は「左の子孫 ＜ 親 ＜ 右の子孫」がすべての節で成り立つ2分木である
- 木を中間順（in-order）でたどって値を並べたとき、昇順になっていれば2分探索木だと判定できる
- Pythonで木を組み立て、
inorder()とis_bst()を使って実際に判定してみると、図を目で追うだけでは気づきにくい「どこが条件を破っているか」までコードの上で確認できる
暗記だけでなく、実際に木を組み立ててプログラムで判定してみることで、「2分探索木とは何か」がより具体的に理解できるだろう。
参考リポジトリ
この記事で扱ったコードは、以下のGitHubリポジトリで公開している。
コメント