4分木とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > 4分木の意味・解説 

四分木

(4分木 から転送)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/06/19 08:05 UTC 版)

ナビゲーションに移動 検索に移動
領域四分木

四分木(しぶんぎ、: Quadtree)は、各内部ノードが4個までの子ノードを持つ木構造データ構造である。四分木は主に、2次元空間を再帰的に4つの象限または領域に分割するのに使われる。領域は四角形または矩形の場合もあるし、任意の形状の場合もある。このデータ構造は1974年、Raphael Finkel と J.L. Bentley が四分木と名づけた。同様の分割手法はQ木 (Q-tree) とも呼ばれている。四分木に共通する特徴は以下の通りである。

  • 空間を適応可能セルに分割する。
  • 各セル(またはバケット)は容量の上限がある。容量が最大に達すると、バケットは分割される。
  • 木構造ディレクトリは四分木の空間分割に従う。

種類

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

領域四分木

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

深さ n の領域四分木は、カテゴリ




英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「4分木」の関連用語

4分木のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



4分木のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの四分木 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS