四分木

四分木（しぶんぎ、）は、各内部ノードが4個までの子ノードを持つ木構造のデータ構造である。四分木は主に、2次元空間を再帰的に4つの象限または領域に分割するのに使われる。領域は四角形または矩形の場合もあるし、任意の形状の場合もある。このデータ構造は1974年、Raphael Finkel と J.L. Bentley が四分木と名づけた。同様の分割手法はQ木 (Q-tree) とも呼ばれている。四分木に共通する特徴は以下の通りである。
 空間を適応可能セルに分割する。
 各セル（またはバケット）は容量の上限がある。容量が最大に達すると、バケットは分割される。
 木構造ディレクトリは四分木の空間分割に従う。

 種類 
四分木は表現するデータの型によって分類され、領域 (area)、点 (point)、線 (line)、曲線 (curve) などがある。また、木構造の形状とデータを処理する順序が独立しているかどうかでも分類される。典型的な四分木について以下に解説する。

 領域四分木 
領域四分木は、2次元の空間を同じ大きさの4つの象限に再帰的に分割していくもので、各ノードは特定の領域に対応したデータを保持する。各ノードは4つの子ノードを持つか、あるいは全く子ノードを持たないか（つまり葉ノード）のどちらかである。領域四分木は、分割位置がデータに依存していないため、厳密には木構造ではないとされる。より厳密に言えばTrieに近い。

深さ n の領域四分木は、 ピクセルで各ピクセルの値が0か1の画像を表現するのにも使われる。根ノードはその画像領域全体を表している。ある部分領域に属するピクセルが全て0あるいは1でない場合、その部分領域はさらに分割される。つまり、各葉ノードは全ピクセルが0あるいは1のブロックを表している。

領域四分木は、平面上のデータの分布を表すのにも使われる。例えば、ある領域の温度の分布を四分木に格納すると、葉ノードは同じ温度の領域を表すことになる。

座標データ群（例えば、都市の緯度と経度）を四分木に格納する場合、各葉ノードが最大1つの座標点を格納する状態になるまで分割が行われる。

 点四分木 
点四分木は、二分木を2次元座標データを表すように適応させたものである。分割の中心点には常に1つの点データが対応する。木構造の形状はデータを処理する順序に依存する。2次元座標データ列を効率的に比較することができ、一般的な処理時間は O(log n) である。

 点四分木のノード構造 
点四分木のノードは二分木のノードに似ているが、子ノードが4つあるところが大きく異なる（二分木は右と左の2つ）。またキーは2つの成分に分かれていて、一般にx座標とy座標に対応する。従って、ノードには以下の情報が格納されている。

 4つのポインタ - 北西象限、北東象限、南西象限、南東象限
 点 - さらに以下の内容が点データとして含まれる
 キー - x座標とy座標で表される
 値 - 名前など

 辺四分木 
辺四分木 (edge quadtree) は、点ではなく線を格納するのに使われる。曲線はセルを微細に分割することで近似的に表す。結果として得られる木構造は非常にアンバランスであり、インデックス付けの用途には向かない。

 主な用途 
 空間インデックス
 画像データ格納
 2次元における効率的当たり判定
 地形データの視野判定
 スプレッドシートまたは何らかの行列計算のためのフォーマッティング情報などの疎なデータを格納する。
 多次元の場を解く（数値流体力学、電磁気学）
 セル・オートマトン（ハッシュライフ）

四分木は八分木の2次元版と見ることもできる。

 注意点 
幾何学的分割で各象限のアイテム数が減らない場合（データがオーバーラップしている場合など）、四分木による分割は失敗し、アルゴリズムが続く限りメモリを消費し続けることになる。例えば、1つの象限の容量の上限が8の場合、(0, 0) に9つの点があるとすると、分割しても3つの象限は空で、残る1つに9つの点が含まれることになる。従って、再帰的に分割が必要になるが、どこまで分割しても上限を超えてしまう。そのような場合、1つの象限に8個以上の点を許容せざるを得ないので、四分木は任意の幾何学的データ群について O(N) の複雑性に漸近していく。

 参考文献 

  Chapter 14: Quadtrees: pp.291–306. 

 関連項目 
 八分木
 バイナリ空間分割
 kd木
 R木
 空間インデックス

 外部リンク 
 A discussion of the Quadtree and an application
 Considerable discussion and demonstrations of Spatial Indexing

Category:幾何学的データ構造
Category:ツリー (データ構造)
Category:データベース・インデックス技術