K-D strom (tiež nazývaný ako K-dimenzionálny strom) je binárny vyhľadávací strom, kde údaje v každom uzle sú K- dimenzionálny bod v priestore … Body vľavo tohto priestoru sú reprezentované ľavým podstromom tohto uzla a body napravo od priestoru sú reprezentované pravým podstromom.
Je strom KD presný?
Dátové body sú rozdelené v každom uzle do dvoch súborov. Rovnako ako predchádzajúci algoritmus, KD Tree je tiež algoritmus binárneho stromu vždy končiaci maximálne dvoma uzlami … Na pravej strane obrázku nižšie môžete vidieť presnú polohu dátové body, na ľavej strane ich priestorová poloha.
Ako sa robí KD strom?
Building KD-Stree
- Prvý vložený bod sa stáva koreňom stromu.
- Vyberte os na základe hĺbky tak, aby os cyklovala cez všetky platné hodnoty. …
- Zoraďte zoznam bodov podľa osi a vyberte medián ako otočný prvok. …
- Prechádzajte stromom, kým uzol nebude prázdny, potom uzlu priraďte bod.
- Opakujte krok 2-4 rekurzívne, kým sa nespracujú všetky body.
Prečo používame strom kd?
Stromy KD sú špecifická dátová štruktúra na efektívnu reprezentáciu našich údajov KD-stromy pomáhajú organizovať a rozdeľovať dátové body na základe špecifických podmienok. Teraz urobíme niekoľko osovo zarovnaných rezov a budeme udržiavať zoznamy bodov, ktoré spadajú do každého z týchto rôznych zásobníkov.
Je octree strom kd?
Údaje každého listového uzla v oktree tvoria miestny strom KD. V oktree uzly ukladajú iba informácie o ohraničujúcom rámčeku. Každý listový uzol má priradenú hodnotu indexu pre pohodlie výskumu.
