多分木

キーを整列した状態で保持する平衡木（B木やB+木）で構成した索引で、根から葉までの深さがどのキーでも同じなので、データ量がnのとき探索・挿入・削除をO(log n)で行える。一致検索のほか範囲検索や並び替えにも使えるため、多くのDBMSで標準の索引方式になっている。値の種類が多い（カーディナリティが高い）列に向く。

推論の途中の考え（思考）を木構造で扱い、各段階で複数の候補を生成して見込みを評価し、有望なものを探索して行き詰まれば別の枝に戻る手法。1本の道筋で考えるCoTに比べ、試行錯誤や先読みが必要なパズルや計画の問題で正答率が上がるが、多くの候補を生成・評価するので計算の費用がかさむ。

データ（節点、ノード）を親子関係で階層的につないだ、閉路のないデータ構造。最上位の節点を根、子を持たない節点を葉といい、n個の節点の木の枝はn－1本である。ファイルシステムのディレクトリ、組織図、構文木、探索木（2分探索木、B木）などに使われる。

各節点の子の並び順に意味がある木。2分木の左の子と右の子のように、子を第1子、第2子と区別して扱う。子の順序が決まっているので、先行順・中間順・後行順といった節点の訪問順（走査）が定まり、構文木や2分探索木はこの性質を前提としている。

キーの大小関係に従って節点を配置し、根から比較しながらたどることで目的のキーを効率よく探せるようにした木。各節点で左の部分木に小さいキー、右に大きいキーを置く2分探索木が基本で、平均O(log n)で探索・挿入・削除ができる。偏った順にデータを入れると高さが増してO(n)に悪化するので、AVL木や赤黒木、B木のように高さを自動的に保つ平衡木が使われる。

各ノードが最大2つの子ノードを持つ木構造。左の子と右の子に分かれる。2分探索木、ヒープ、式木など多くの応用がある。探索や整列の効率的な実装に使われる。