テクノロジー編25: データ構造

2 分木: 各節点が高々 2 つの子を持つ木構造。
k 分木: 各節点が高々 k 個の子を持つ木構造。
多分木: 3 個以上の子を持つ節点があるような木。

葉の深さがなるべく均等になるように調整された木構造。
葉の深さの差の最大値がある値 (たとえば 1) 以内になるように操作する。

各節点間で順序がつけられている木構造。
数値の大小関係や、文字列の辞書順などで順序をつける。

データの効率的な検索を目的とした木構造。
順序木の一種であることが多い。

葉以外の節点がすべて 2 つの子を持ち、すべての葉が同じ深さにあるような木構造。
配列を用いて効率的に表現することができるなど、便利な性質がある。

すべての節点について「左の子の値 ≦ 親の値 ≦ 右の子の値」という条件を満たす木構造。
根から左右どちらかの子に進むことを繰り返すことで、探索を効率的におこなうことができる。
最悪の場合、 1 本線のような構造になってしまうことがある。

各節点について、左右の部分木の深さの差が 1 以内になるように調整される、バランス木かつ 2 分探索木の一種。
考案者のアデルソン・ヴェルスキーとランディスの名前に由来。

B 木は多分木やバランス木、探索木の性質を持つ。
外部記憶装置においてデータを効率的に格納するのに適した構造として知られる。
データベースやファイルシステムなどでよく利用されています。