K-d drevesa

Iz MaFiRaWiki

Vsebina

Definicija in lastnosti

Včasih želimo imeti dostop do elementov v slovarjih po več različnih ključih. Če imamo k ključev, potem lahko uporabimo k-dimenzionalno drevo ali na kratko k-d drevo. k-d drevo je binarno iskalno drevo, kjer velja:

  • Eno vozlišče vsebuje k ključev.
  • Za vozlišče na i-tem nivoju velja, da so v levem poddrevesu samo elementi, ki imajo manjši ali enak (i%k)+1-vi ključ, kot ga ima element v vozlišču, ter da so v desnem poddrevesu samo elementi, ki imajo ta ključ večji, kot ga ima element v vozlišču.

Zgoraj omenjene lastnosti nam ne zagotavljajo, da lahko določen element iščemo vedno le v enem poddrevesu, tako kot pri binarnem isklalnem drevesu. Vsakič je treba preiskati vsa poddrevesa, razen na vsakih k nivojev, kjer je odločitev za levo in desno poddrevo enolična. Zato pa lahko k-d drevo uporabljamo za učinkovito iskanje elementov, katerih ključi se nahajajo na določenem intervalu, pri čemer za vsak ključ lahko izberemo drugačen podinterval.

Primer

Primer 2-d drevesa:


Uporaba

k-d drevo se najpogosteje uporablja za iskanje najbližjega elementa.

Glej tudi

Osebna orodja