クワッドツリーとは何ですか？

Quadtreeは、4つのパワーに基づいた木のような構造であり、データベース内のファイルを整理するために使用されます。各親、または開始ノードには4つの子ノードがあり、各子供には一定量のデータがあります。データ制限が境界に流出すると、そのノードから4人の子供が作成されます。 2つの主要なクアッドツリー構造があります。領域とポイントツリーは、それぞれ設計がわずかに異なります。 2D画像のピクセルは常に4つの部分に分離できるため、クアッドツリーはデータベースで最もよく使用されますが、2次元（2D）画像のピクセルを見つけるためにも使用できます。親は出発点であり、幅広いカテゴリベースのデータが含まれていますが、子供はファイルとドキュメントを保持しています。クワッドツリーには、すべての親が4人の子供を持たなければなりません。 4人の子供がいなければなりませんが、すべての子供がデータを封じ込める必要はありません。ないものはnullノードとして知られています。これらのヌルノードはしばしば残ります停滞してデータを待ちます。

Quadtreeの各子供ノードにはデータ制限があります。この制限は通常、データベース全体のサイズによって定義されます。限界を超えてプッシュする非常に多くの情報がある場合、子ノードは本質的に出産することで親ノードになります。通常、この作成から1つまたは2つのヌルノードがありますが、これはノード内のデータの量に完全に依存します。

領域とポイントの2つの主要なクワッドツリーがあります。リージョンクワッドツリーは、4、8、または16のパートなど、4つのパワーに基づいて2D領域全体を分解するために使用され、表現に使用されることがよくあります。この構造は、画像、またはデータフィールドグラフに最適です。ポイントバージョンはバイナリツリーのようなもので、順序付けられたポイントで使用するのが最適です。このバリアントは、からの中心的なポイントがあるため、真の木でもありますノードが散乱する領域バージョンとは異なり、すべてのノードが生まれます。

Quadtreeの最も一般的な使用は、データベースを分離して整理することですが、これはその唯一の使用ではありません。画像内の各ピクセルを4つの等しい部分に分離できるため、画像で特定のピクセルを見つけるように作られたアルゴリズムが一般的にクアッドトリーを使用します。これにより、Quadtreeはピクセルの検索に独自に適しています。