リラックスしたkdツリー

緩和K -dツリーまたは緩和K次元ツリーは、 Kdツリーの変形であるデータ構造です。K次元ツリーと同様に、緩和K次元ツリーはn次元レコードのセットを格納し、各レコードは一意のK次元キーx = (x ₀ ,... ,x _K−1 )を持ちます。Kdツリーとは異なり、緩和Kdツリーでは、各ノードの判別式は任意です。緩和Kdツリーは1998年に導入されました。^[1]

K 次元キーのセットに対する緩和 Kd ツリーは、次の条件を満たすバイナリ ツリーです。

1. 各ノードにはK次元のレコードが含まれており、任意の判別式j∈{0,1,...,K−1}が関連付けられています。
2. キーxと判別式jを持つすべてのノードに対して、次の不変条件が成り立ちます。キーyを持つ左サブツリーのレコードはいずれもy _j < x _jを満たし、キーyを持つ右サブツリーのレコードはいずれもy _j ≥ x _jを満たします。^[2]

K = 1の場合、緩和 Kd 木は二分探索木になります。

Kd ツリーと同様に、サイズnの緩和された Kd ツリーは、ドメイン D をn+1 個の領域に分割します。各領域は Kd ツリーのリーフに対応します。ノード {x,j} の境界ボックス (または境界配列) は、ツリーに挿入されたときに x が含まれるリーフによって区切られた空間の領域です。したがって、ルート {y,i} の境界ボックスは [0,1] ^K、左サブツリーのルートの境界ボックスは [0,1] × ... × [0,y _i ] × ... × [0,1] などとなります。

nレコードを持つ緩和 Kd ツリーの平均時間計算量は次のとおりです。

• 完全一致クエリ: O(log n)
• 部分一致クエリ: O(n ^1−f(s/K) )、ただし:
  • K個の属性のうちのsが指定されている
  • 0 < f(s/K) < 1 の場合、s/K の実数値関数
• 最近傍クエリ: O(log n) ^[3]

• k -d ツリー
• 暗黙のk -d ツリー、明示的に格納された分割セットではなく、暗黙の分割関数によって定義されたk -d ツリー
• 最小/最大k -d ツリー、各ノードに最小値と最大値を関連付けるk -d ツリー