データ構造の範囲ツリー

範囲ツリーは、ポイントのリストを保持するための順序付けられたツリーデータ構造として定義されます。これにより、特定の範囲内のすべてのポイントを効率的に取得でき、通常は2次元以上で実装されます。 O（log ^d のクエリ時間が速いことを除いて、kdツリーと同じです。 n + k）が、O（n log ^d-1 のストレージが悪い n）、dはスペースの次元を示し、nはツリー内のポイントの数を示し、kは特定のクエリで取得されたポイントの数を示します。範囲ツリーは、間隔ツリーで区別できます。ポイントを格納して特定の範囲内のポイントを効率的に取得できるようにする代わりに、間隔ツリーは間隔を保存し、特定のポイントを含む間隔を効率的に取得できるようにします。

データ構造

1次元の範囲ツリーの例。リーフ以外の各ノードは、左側のサブツリーに最大値を格納します。

1次元の点のセット上の範囲ツリーは、それらの点の平衡二分探索木として扱われます。ツリーに保存されているポイントは、ツリーの葉に保存されています。各内部ノードは、左側のサブツリーに含まれる最大値を格納します。 d次元の一連の点の範囲ツリーは、再帰的に定義されたマルチレベルの二分探索木です。データ構造の各レベルは、d次元の1つで二分探索木として扱われます。最初のレベルは、最初のd座標上の二分探索木です。このツリーの各頂点vは、vのサブツリーに格納されているポイントの最後の（d-1）座標上の（d-1）次元の範囲ツリーである関連する構造で構成されます。

操作

建設

n点のセット上の1次元範囲ツリーは、二分探索木であり、O（n log n）時間で構築できます。高次元の範囲ツリーは、ポイントの最初の座標上に平衡二分探索ツリーを構築することによって再帰的に構築され、その後、このツリーの各頂点vについて、含まれるポイント上に（d-1）次元の範囲ツリーを構築します。 vのサブツリーで。この方法で範囲ツリーを構築するには、O（n log ^d n）時間。