探索木【search tree】

概要

木構造は各ノードが値と複数の子ノードへの参照を持つ構造で、単一の根本（根ノード）から階層的に枝分かれしていくようにノードが連なっている。子の数が2つまでに制限された「二分木」、任意の数持てる「多分木」（N分木）などの種類がある。

探索木は特定の値を高速に探し出すことができるようにした木構造である。最も単純な二分木を用いた「二分探索木」の場合、木にノードを追加する際、「左側の子孫（部分木）の値がすべて自分より小さく、右側はすべて大きい」という条件を満たす位置を探し出して、そこに追加する。

この木を用いてある検索値を探索するには、根本から順に「現在のノードの値より検索値が小さければ左の子ノードに、大きければ右に遷移する」というルールで木をたどっていき、値が一致するノードに到達すれば発見、見つからないまま末端（葉ノード）に到達すれば検索値は存在しないことがわかる。