読み方 ： たんさくぎ

概要

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

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

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

この記事の著者 ： (株)インセプト IT用語辞典 e-Words 編集部
1997年8月より「IT用語辞典 e-Words」を執筆・編集しています。累計公開記事数は1万ページ以上、累計サイト訪問者数は1億人以上です。学術論文や官公庁の資料などへも多数の記事が引用・参照されています。