Uvolněný strom k-d - Relaxed k-d tree

A uvolněný K.-d strom nebo uvolněný K.-rozměrný strom je datová struktura, která je variantou K-d stromy. Stejně jako K-dimenzionální stromy, uvolněný K-dimenzionální strom ukládá sadu n-vícerozměrných záznamů, z nichž každý má jedinečný K-dimenzionální klíč x = (x₀,... ,X_{K − 1}). Na rozdíl od stromů K-d jsou v uvolněném stromu K-d diskriminátoři v každém uzlu libovolní. Uvolněné stromy K-d byly představeny v roce 1998.^[1]

Definice

Uvolněný K-d strom pro sadu K-dimenzionálních klíčů je binární strom, ve kterém:

1. Každý uzel obsahuje K-dimenzionální záznam a má přidružený libovolný diskriminátor j ∈ {0,1, ..., K - 1}.
2. Pro každý uzel s klíčem X a diskriminující j, platí následující invariant: jakýkoli záznam v pravém podstromu s klíčem y vyhovuje y_j j a jakýkoli záznam v levém podstromu s klíčem y vyhovuje y_j ≥ x_j.^[2]

Li K = 1, uvolněný strom K-d je a binární vyhledávací strom.

Stejně jako u stromu K-d, uvolněný strom K-d velikosti n indukuje rozdělení domény D do n + 1 oblasti, z nichž každá odpovídá listu ve stromu K-d. Ohraničující rámeček (nebo ohraničené pole) uzlu {x, j} je oblast prostoru vymezeného listem, do kterého x spadne, když je vloženo do stromu. Ohraničující rámeček kořene {y, i} je tedy [0,1]^K., ohraničující rámeček kořene levého podstromu je [0,1] × ... × [0, y_i] × ... × [0,1] atd.

Podporované dotazy

Průměrné časové složitosti v uvolněném stromu K-d s n záznamy jsou:

• Dotazy na přesnou shodu: O (log n)
• Částečné dotazy na shodu: O (n^{1 − f (s / K)}), kde:
  • Jsou specifikovány s z K atributů
  • s 0
• Dotazy na nejbližšího souseda: O (log n)^[3]

Viz také

• k-d strom
• implicitní k-d strom, a k-d strom definovaný implicitní funkcí rozdělení spíše než explicitně uloženou sadou rozdělení
• min / max k-d strom, a k-d strom, který spojuje minimální a maximální hodnotu s každým z jeho uzlů

Reference