データ構造のポイント四分木

ポイントクワッドツリーは、2次元のポイントデータを表すために実装されたバイナリツリーを応用したものです。すべての四分木の機能は、ポイント四分木によって共有されます。

多くの場合、2次元の順序付けられたデータポイントを比較するのに非常に効率的であり、通常はO（log n）時間で実行されます。ポイント四分木は完全性のために言及する価値がありますが、k-d木は、一般化された二分探索のツールとしてそれらを上回っています。

ポイント四分木は次のように構築されます。

次に挿入するポイントを指定して、それが存在するセルを計算し、ツリーに追加します。

新しいポイントは、それを含むセルが、ポイントを通る垂直線と水平線によって象限に分割されるように追加されます。したがって、セルは長方形ですが、必ずしも正方形である必要はありません。

これらのツリーでは、各ノードは入力ポイントの1つで構成されています。

平面の分割はポイント挿入の順序によって決定されるため、ツリーの高さは挿入順序に敏感であり、それに依存します。間違った順序で挿入すると、入力ポイントの数が線形の高さのツリーになる可能性があります（その時点でリンクリストになります）。

ポイントセットが静的な場合は、前処理を実行して、バランスの取れた高さのツリーを構築できます。

ポイント四分木のノード構造

ポイントクワッドツリーのノードは、バイナリツリーのノードと同じですが、主な違いは、2つ（「左」と「右」）ではなく、4つのポインター（各ポインターが各象限に使用される）に関連付けられていることです。通常の二分木で。また、キーは通常、x座標とy座標を参照して2つの部分に分割されます。

したがって、ノードは次の情報で構成されます

• 4つのポインタ：これらは、quad [‘NW’]、quad [‘NE’]、quad [‘SW’]、およびquad [‘SE’]
• 北西-北西、北東-北東、南西-南西、南東-南東
• ポイント;で構成されています
• キー;通常、x、y座標で表されます
• 値;名前など