木構造

データが親子関係を持つ階層的なデータ構造。最上位のノードを根（ルート）、末端のノードを葉（リーフ）と呼ぶ。ファイルシステムのディレクトリ構造が代表例である。

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

データを、根（ルート）から枝分かれする親子関係で階層的に表すデータ構造で、子を持たない節を葉という。ファイルシステムのディレクトリやデータベースの索引などに使われ、子が最大2つの2分木やB木など多くの種類がある。

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

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

1つの節点が3つ以上の子を持てる木で、m個までの子を持つものをm分木という。1つの節点に多くのキーと子を持たせると木の高さが低くなり、根から葉までにたどる節点が少なくて済む。この性質を使ったB木やB+木は、ディスクの1回の読込みで多くのキーを比較できるので、データベースの索引に使われる。

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

出現頻度の高い記号には短いビット列を、低い記号には長いビット列を割り当てる可変長の符号化方式。出現頻度を基に2分木を作って符号を決め、どの符号も他の符号の先頭部分にならないため、区切りなしで一意に復号できる。可逆圧縮の基本的な手法で、JPEGやZIPの中でも使われる。

B木を改良したデータ構造で、データ（またはその所在）は葉にだけ格納し、内部の節は探索のためのキーだけを持つ。葉どうしがポインタで順につながっているため、範囲を指定した検索や順次の読出しが速く、データベースの索引に広く使われる。