K-D stablo

K-D stablo (skracenica za K-dimenziono stablo) u informatici predstavlja strukturu podataka koja deli prostor i organizuje tacke u K-dimenzionom prostoru. K-D stabla su veoma korisna struktura podataka za mnoge aplikacije, kao sto su pretraživanja koja ukljucuju vižedimenzionu pretragu ključeva (npr. opseg pretraživanja i najbliži sused pretrage). K-D stablo je posebna vrsta binarnog stabla.

Trodimenzionalno K-D stablo. Prva podela (crvena) deli osnovnu ćeliju (bela) na dva jednaka dela, zatim druga podela (zelena) na dve podćelije. Poslednja podela (plava) deli sve četiri ćelije na dve podćelije. Ovih osam ćelija se nazivaju ćelije listovi.

Neformalni opis

K-D stablo je binarno stablo u kome je svaki čvor K-dimenzionalna tačka. Svaki ne list čvor može da se posmatra kao implicitno generisana podela hiperravni koja deli prostor na dva dela, poznata kao polu-prostor. Tačke sa leve strane ove hiperravni prestavljaju levo podstablo, a tačke sa desne, desno podstablo K-D stabla. Pravac hiperravni je izabran na sledeci nacin: svaki čvor u stablu je povezan sa jednom od K dimenzija, sa heperravni koja je normalna na osu te dimenzije. Tako, na primer, ako je za određenu podelu uzeta osa "x", u levom podstablu će se nalaziti čvorovi sa manjom vrednošću "x", a u desnom podstablu čvorovi sa većom vrednošću "x". U tom slučaju, hiperravan ce biti postavljana od strane x-vrednosti tačke, a njena normala ce biti x-osa.

Konstrukcija

Postoji mnogo različitih načina na koji se može napraviti K-D stablo. Kanonski način konstruisanja K-D stabla ima sledeća ograničenja:

• Kako se krećemo niz drvo, jedna petlja se koristi za određivanje ravni. (Npr. U trodimenzionalnom stablu, koren će imati ravan poravnatu po x-osi, njegova deca ce imati ravan poravnatu po y-osi, unuci će imati ravan poravnatu po z-osi, pra-unuci će imati ravan poravnatu po x-osi, pra-pra-unuci po y-osi i tako dalje).
• Čvorovi se ubacuju u stablo izborom tačke srednje vrednosti za koren, i zatim se tačke ubacuju u levo, odnosno desno podstablo, uzimajući u obzir njihove vrednosti. (Treba imati na umu pretpostavku da treba smestiti n tačaka u algoritmu unapred.)

Ovaj metod dovodi do stvaranja balansiranog K-D stabla, u kom je svaki list na istom rastojanju od korena. Međutim, izbalansirano stablo ne mora biti optimalno za sve aplikacije.

Treba imati na umu da nije potrebno izabrati srednju tačku. U tom slučaju nema garancije da ce rezultat biti balansirano stablo. Najčešće se koristi jednostavan algoritam sortiranja (O(n logn)) radi nalaženja tačke sa srednjom vrednosti koja će služiti za deljenje ravni. U praksi, ova tehnika često dovodi do stvaranja lepo izbalansiranog stabla.

Sledeći algoritam koristi određivanje tačke srednje vrednosti za pravljenje balansiranog K-D stabla. Kao ulaz prima listu od n tačaka koje bi trebalo da se nalaze u stablu.

function kdtree (list of points pointList, int depth)
{
    // Odabir ose zasnovan na dubini, tako da osa prolazi kroz sve validne vrednosti 
    var int axis := depth mod k;
        
    //  Sortiranje tačaka i odabir medijana kao pivot element
    select median by axis from pointList;
        
    // Kreiranje čvora i konstrukcija podstabla
    var tree_node node;
    node.location := median;
    node.leftChild := kdtree(points in pointList before median, depth+1);
    node.rightChild := kdtree(points in pointList after median, depth+1);
    return node;
}

Dodavanje čvorova

Dodavanje novih elemanata u K-D stablo je identično kao i dodavanje elemenata u bilo koje drugo stablo pretrage. Prvo se kreće od korena i u zavisnosti od toga da li se tačka nalazi u levoj i desnoj poluravni, kretanje se obavlja u levo, odnosno desno podstablo. Kada se stigne do čvora kom bi trebalo dodati novi čvor kao dete, ponovo u zavisnosti od toga da li je čvor u levoj ili desnoj poluravni, dodaje se novi list.

Dodavanje čvorova na ovakav nacin moze da dovede do stvaranja neizbalansiranog stabla, što dovodi do smanjenja performansi stabla. Brzina degradacije performansi stabla zavisi od prostornog rasporeda dodatih čvorova stabla, i broja dodatih čvorova u odnosu na veličinu stabla. Ako stablo postane previše neuravnoteženo, onda je neophotno uraditi ponovno uravnoteživanje stabla kako bi se povratile performanse stabla za određene operacije, kao sto je traženje najbližeg suseda.

Brisanje čvorova

Da bi se postojeci čvor uklonio iz K-D drveta, bez razbijanja invarijanti, najlakši način je da se formira skup svih čvorova i listova ciljanog čvora, i ponovo napraviti samo daj deo stabla.

Drugi pristup je nalaženje zamene za cvor koji treba ukloniti. Prvo se nađe čvor P koji treba izbrisati. U baznom slucaju, ako je čvor P list, ne traži se zamena, vec se čvor direktno brise iz stabla. U opštem slučaju, nalazi se čvor zamena (npr. čvor R) iz podstabla kom je koren čvor P. Vrsi se zamena R i P, i zatim se rekuzivno briše čvor R.

Za tačku zamene se najčešće uzima ili čvor sa najmanjom vrednosti iz desnog podstabla ili čvor sa najvecom vrednosti iz levog podstabla.

Balansiranje K-D stabla

Balansiranje K-D stabla zahteva pažnju jer su čvorovi sortirani u više dimenzija, tako da se rotacija drveta ne može koristiti za balansiranje, jer može izazvati pucanje invarijante.

Postoji nekoliko načina balansiranja K-D stabla. Ona uključuju podeljeno K-D stablo, pseudo K-D stablo, KDB stablo, hB stablo i BKD stablo. Mnogi od ovih načina su adaptacija K-D stabla.

Traženje najbližeg komšije

Animacija pretrage najbližeg komšije kod K-D stabla sa dve dimenzije

Algoritam traženja najbližeg komšije ima za cilj da pronađe čvor u drvetu koji je najbliži datom čvoru. Ova pretraga se može efikasno uraditi uz pomoć osobine stabla da brzo eliminiše velike delove prostora za pretragu.

Algoritam se obavlja na sledeći način:

1. Počevši od korena, algoritam se pomera na dole u stablu rekurzivno, na isti način kao kod pretrage tokom unosa novog čvora u stablo (tj. ide se u levo ili desno podstablo u zavisnosti od toga da li je vrednost manja ili veća u odnosu na trenutni čvor).
2. Kada algoritam dostigne list, pamti taj list kao "trenutni najbolji".
3. Algoritam se rekurzivno vraća kroz stablo izvršavajući sledeće korake na svakom čvoru:

1. 1. Ako je trenutni čvor bliži zadatom čvoru od "trenutnog najboljeg", on postaje "trenutni najbolji".
   2. Zatim algoritam proverava da li postoji čvor bliži traženom čvoru tako što formira sferu (poluprečnika jednokog udaljenosti traženog čvora od trenutnog čvora) oko trenutnog čvora. Ako postoji tačka u toj sferi, onda ona postaje "trenutna najbolja".
2. Kada se algoritam završi za koreni čvor, proces pretrage je gotov.

Generalno ovaj algoritam koristi kvadrat rastojanja za poređenje, da bi se izbeglo računanje kvadratnog korena. Pored toga, može da se uštedi i čuvajući kvadratno rastojanje "trenutnog najboljeg", koje se koristi za poređenje.

Pronalaženje najbližeg čvora ima O(log N) operacija u slučaju slučajno raspoređenih tačaka. Međutim tvrdi se da algoritam daje složenost O(log N) u bilo kom slučaju.

Opseg pretrage

Analiza binarnog stabla pretrage je utvrdila da je najgori slučaj vremena opsega pretrage u K-D stablu koje sadrži N čvorova dat sledećom jednočinom:

$t_{najgore}=O(k\cdot N^{1-{\frac {1}{k}}})$

Višedimenzionalni podaci

K-D stablo nije pogodno za efikasno traženje najbližeg suseda u prostoru sa mnogo dimenzija. Po pravilu, ukoliko je prostor K-dimenzionalan, a broj čvorova u stablu N, trebalo bi da bude N >> 2^k.

Složenost

• Konstrukcija statičkog K-D stabla sa N čvorova je složenosti:
  • O(n log² n), ako se koristi algoritam kao što je Hip sort, složenosti O(n log n), za traženje medijana.
  • O(n log n), ako se koristi algoritam linearne složenosti.
  • O(kn log n) + O([k-1]n log n), ako je N čvorova sloritrano u K dimenzija primenom algoritma slozenosti O(n log n) tokom izgradnje K-D stabla.
• Ubacivanje novog čvora u balansirano stablo: O(log n).
• Brisanje čvora iz balansiranog stabla: O(n log n).
• Traženje najbližeg komšije u balansiranom stablu, sa slučajno raspoređenim čvorovima: u proseku O(n log n).

Види још

• Стабло (структура података)
• Бинарно стабло
• Стабло у теорији графова
• Структура података
• Листа