探索木ってなんだろう？
「探索木（たんさくぎ）」という言葉を聞いたことがありますか？ 一見難しそうに聞こえるかもしれませんが、これはコンピュータが大量のデータの中から目的のものを素早く見つけ出したり、最善の選択をしたりするために使われる、非常に重要な考え方です。
実は「探索木」には、大きく分けて2つの意味があります。一つはプログラミングで使われる「データ構造」としての探索木、もう一つはAI（人工知能）などが答えを見つける思考プロセスを表す「問題解決のモデル」としての探索木です。
このブログでは、この二つの「探索木」について、初心者の方にも分かりやすく、具体的な例を交えながら解説していきます。
1. データを効率よく管理！「データ構造」としての探索木
まず、データを整理整頓するための箱、つまり「データ構造」としての探索木について見ていきましょう。ここでの探索木は、たくさんのデータを効率的に「探索」「追加」「削除」できるように工夫された、木のような階層構造を持つデータ形式のことです。
最も基本的！二分探索木
探索木の中で最も有名で基本的なものが「二分探索木（にぶんたんさくぎ）」です。二分探索木は、すべてのデータ（ノードと呼びます）が以下のシンプルなルールに従って配置されています。
- あるノードから見て、左側の子孫のノードは、必ずそのノードの値より小さい。
- あるノードから見て、右側の子孫のノードは、必ずそのノードの値より大きい。
このルールがあるおかげで、何かデータを探したいとき、非常に効率的に見つけ出すことができます。 例えば、根（一番上のノード）から始めて、探している値が今いるノードの値より小さければ左へ、大きければ右へと進むだけで、探す範囲をどんどん半分に絞り込めるのです。
二分探索木のメリットとデメリット
メリットは、なんといってもデータの探索・追加・削除が高速であることです。 一方で、デメリットもあります。データを追加する順番によっては、木が左右均等に成長せず、片方にばかり伸びて一本道のような形になってしまうことがあります。 これでは、せっかくの高速性が失われてしまいます。この問題を解決するために、木が偏らないように自動でバランスを調整する「平衡二分探索木」（AVL木や赤黒木など）といった、より高機能な探索木も存在します。
Pythonコードで見る二分探索木のイメージ
実際に二分探索木がどのようにデータを保持し、探索を行うのか、Pythonの簡単なコードで見てみましょう。
# 各データを格納するノードの設計
class Node: def __init__(self, value): self.value = value # ノードが持つ値 self.left = None # 左の子ノード（自分より小さい） self.right = None # 右の子ノード（自分より大きい）
# 簡単な二分探索木の例
#
# / \
#
# / \ /
#
# 手動で木を組み立て
root = Node(10)
root.left = Node(5)
root.right = Node(15)
root.left.left = Node(3)
root.left.right = Node(7)
root.right.left = Node(12)
# 値を探索する関数の例
def search(node, value_to_find): # 目的のノードが見つからないか、値が一致したら終了 if node is None or node.value == value_to_find: return node # 探す値が今のノードより大きいなら右へ if node.value < value_to_find: return search(node.right, value_to_find) # 探す値が今のノードより小さいなら左へ return search(node.left, value_to_find)
# 「7」を探してみる
found_node = search(root, 7)
if found_node: print(f"値 {found_node.value} が見つかりました。")
else: print("値は見つかりませんでした。")
# 「20」を探してみる
found_node_2 = search(root, 20)
if found_node_2: print(f"値 {found_node_2.value} が見つかりました。")
else: print("値 20 は見つかりませんでした。") 2. AIの思考回路！「問題解決のモデル」としての探索木
もう一つの探索木は、AIやゲーム理論で使われる考え方です。こちらは、ある問題の「状態」と、そこから取りうる「選択肢（手）」を木構造で表現したものです。 「ゲーム木」とも呼ばれます。
例えば、チェスや将棋、○×ゲームなどの対戦ゲームを考えてみましょう。
- 現在の盤面が「根」ノードになります。
- そこから自分が指せるすべての「手」が、枝として伸びていきます。
- それぞれの「手」を指した後の盤面が、新しいノードになります。
- 今度は相手が、その盤面から指せるすべての「手」を考えます。
これを繰り返していくと、未来のあらゆる展開を網羅した、とてつもなく巨大な木ができます。 AIは、この木を探索することで「どの手を選べば最も勝利に近づくか」を計算しています。1997年にチェスの世界チャンピオンに勝利したIBMの「ディープ・ブルー」も、このような強力な探索能力を利用していました。
賢く探索するためのアルゴリズム
もちろん、ゲームのすべてのパターンを調べ上げるのは現実的ではありません。 そこでAIは、以下のような賢いアルゴリズムを使って、有望な手だけを効率的に探索します。
- ミニマックス法: 自分が最も得をして（max）、相手の得が最も少なくなる（mini）手を探す基本的な考え方です。
- アルファ・ベータ法: ミニマックス法を改良し、明らかに無駄な手の探索を省略（剪定）して計算量を減らす手法です。
- モンテカルロ木探索: ランダムなシミュレーション（プレイアウト）を何度も行い、勝率の高そうな手を重点的に探索する手法です。 近年、囲碁AIなどで大きな成果を上げています。
2つの探索木はどう違う？まとめの比較表
これら2つの「探索木」の違いを、表で整理してみましょう。
| 観点 | データ構造としての探索木 | AI・問題解決のモデルとしての探索木 |
|---|---|---|
| 目的 | データの高速な探索・追加・削除 | 問題の解や最善手を発見する |
| ノードが表すもの | データそのもの（数値、文字列など） | 問題の状態や選択肢（ゲームの盤面、次の一手など） |
| 主な種類・手法 | 二分探索木、B木、赤黒木、AVL木など | ミニマックス法、アルファ・ベータ法、モンテカルロ木探索など |
| 主な応用分野 | データベースのインデックス、辞書機能、ファイルシステムなど | ゲームAI（チェス、囲碁、将棋）、経路探索、最適化問題など |
このように、目的や使われ方は異なりますが、どちらも「木構造を使って選択肢を整理し、効率的に目的を達成する」という点で共通しています。
おわりに
「探索木」について、2つの側面から解説しました。
データ構造としての探索木は、私たちの使うソフトウェアやサービスの裏側で、データの高速な処理を支える縁の下の力持ちです。 一方、AIにおける探索木は、まるで人間の思考のように、複雑な問題に対して最適な答えを導き出すための骨格となっています。
この基本的な概念を理解することで、プログラミングやAIのニュースが、より一層面白く感じられるようになるかもしれません。