Fa kd

A k -d fa (vagy k -d fa , a k -dimenziós fa esetében ) egy térpartíciós adatstruktúra, amelyet a pontok tárolására , és a keresések ( tartomány szerinti keresés , legközelebbi szomszéd stb.) Gyorsabb elvégzésére használnak, mint a pontok tömbje. A k -d fák a BSP fák (bináris térpartíciós fák ) speciális esetei .

Ezt a struktúrát Jon Louis Bentley, a Stanford Egyetem javasolta 1975-ben.

Leírás

A k -d fák bináris fák , amelyekben minden csomópont tartalmaz egy pontot a k dimenzióban . Minden nem terminális csomópont két féltérre osztja a teret. A két féltér mindegyikében található pontok az aktuális csomópont bal és jobb ágában vannak tárolva. Például, ha egy adott csomópont oszt helyet szerinti normál síkjában irányára (O X ), az összes pont koordináta x kisebb, mint a koordináta a pont társított csomóponthoz lesz tárolva a bal oldali ágban a csomópont. Hasonlóképpen, az x koordináta pontok, amelyek nagyobbak, mint a figyelembe vett pontok, a csomópont jobb ágában kerülnek tárolásra.

Építkezés

A k -d fák felépítésére számos lehetőség áll rendelkezésre . A szokásos felépítés a következő két feltétel betartásával történik:

a hipersík irányát a fa pontjának magasságának függvényében választják meg; a 3. dimenzióban lévő k -d fa esetében a gyökér síkja például normális lesz az (1,0,0) vektorral, a két gyermek síkja pedig a (0,1,0) vektorral lesz normális. , a kisgyermekek normálisak lesznek a vektorral (0,0,1), majd újra normálak a vektorral (1,0,0), és így tovább ...
A kiegyensúlyozott fa érdekében az egyes lépésekben a fába beillesztett pont az, amelynek a medián koordinátája a figyelembe vett irányba esik .

A középpont kiválasztásának korlátozása nem kötelezõ, de lehetõvé teszi a fa kiegyensúlyozottságának biztosítását. A pontok rendezése az egyes szakaszokban időköltséggel jár, ami meglehetősen hosszú fa létrehozási időhöz vezethet. Lehetőség van egy véletlenszerűen kiválasztott rögzített pontok számának mediánjára a következő beillesztendő ponthoz, ami általánosságban kiegyensúlyozott fát ad.

N pont felsorolásából a következő algoritmus kiegyensúlyozott k -d fát épít :

function kdtree (liste de points pointList, int depth) { if pointList is empty return null; // Sélectionne l'axe de comparaison en fonction de la profondeur du nœud var int axis := depth mod k; // trie la liste de points et sélectionne le point médian select median by axis from pointList; // Crée le nœud courant, et construit récursivement les deux fils 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; }

A k -d fa felépítésének algoritmikus bonyolultsága O ( n log 2 n ), ha O ( n log n ) komplexitású medián algoritmust használunk. Ha algoritmust használunk a lineáris komplexitás mediánjának kiszámításához (O ( n ) -ben ), akkor a fa felépítése O-ban ( n log n ) bonyolult .

A hipersík metszet kiválasztásának módszere nagyban befolyásolja a legközelebbi szomszéd keresési algoritmus hatékonyságát. A fent bemutatott standard módszer (a középpont felhasználásával) nagyon vékony sejteket adhat egy dimenzióban; amikor legközelebbi szomszédot keresünk, sok cellánk lehet a keresőgömbben, ami megköveteli a fa sok ágának meglátogatását. Ha viszont a középpontot használjuk (geometriai középpont, a hipersík két egyenlő részre vágja a hiperkockát), akkor „vastag” cellákat kapunk, vagyis a legnagyobb dimenzió közötti arányban. A legnagyobb és a legkisebb a legrosszabb 2: 1, tehát a kereső labda korlátozott számú cellát takar; de sok cella lehet üres, ami üres területeken történő kereséshez vezet.

Maneewongvatana és Mount javasolja a csúszó középpont módszert, amely vékony sejteket képes létrehozni, de zsírsejtekkel körülvéve, és üres sejtek nélkül; ezért garantálja a keresési algoritmus jó hatékonyságát. Ez a módszer abból áll, hogy a középpontot veszik első szándékként; ha az összes pont a hipersík ugyanazon oldalán van (ezért ha egy cella üres), akkor a hipersíkot generáló pontot addig húzzuk, amíg meg nem felel a halmaz egy pontjának. Ezután egy cella legalább egy pontot tartalmaz. Az így létrehozott fa nem feltétlenül kiegyensúlyozott.

Alternatív

Készíthetünk egy k -d fát is , amelyben a pontok a fa levelei.

Megjegyzések és hivatkozások

(in) JL Bentley , " Asszociatív kereséshez használt multidimenzionális bináris keresési fák " , ACM közleményei , vol. 18, n o 9,1975, P. 509-517 ( DOI 10.1145 / 361002.361007 )
(en) Songrit Maneewongvatana és David M. Mount : „ Nem baj soványnak lenni, ha kövérek a barátaid ” , 4. éves CGC Workshop on Computational Geometry ,1999( olvasható online [PDF] )
Egy adott ponthoz és sugárhoz , valamint egy kiválasztott L m normához a keresőgömb a kielégítő pontok halmaza ; ha m = 2 (euklideszi norma), akkor a kereső labda a hiperszféra ${\ displaystyle C (c_ {1}, c_ {2}, ..., c_ {n})}$ $R$ ${\ displaystyle X (x_ {1}, x_ {2}, ..., x_ {n})}$ ${\ displaystyle \ left (\ sum _ {i = 1} ^ {n} (x_ {i} -c_ {i}) ^ {m} \ right) ^ {1 / m} \ leq R}$
(in) " Ortogonális tartomány keresése " , Számítási geometria , Springer,2008, P. 95-120 ( ISBN 978-3-540-77973-5 és 978-3-540-77974-2 , DOI 10.1007 / 978-3-540-77974-2_5 )

Lásd is