h2. kD-Tree

_kD-Tree_ este o structura de date care organizeaza o multime de puncte in $k$ dimensiuni, imparte spatiul in semispatii astfel ca fiecare nod din arbore reprezinta un paralelipiped si contine in el un punct. Noi suntem interesati de arbori 2D in special. Pentru cazul 2D, primului nod ii va fi asociat intreg planul. Se duce o linie verticala de abscisa $x$ care imparte planul in doua si punctele in doua multimi de cardinal egal. Subarborele din stanga va contine toate punctele din stanga acestei drepte verticale, iar subarborele din dreapta va contine toate punctele din dreapta acestei drepte verticale. Radacinei arborelui din stanga ii va fi asociat semiplanul stang determinat de dreapta verticala, si va contine punctul median dintre punctele din semiplanul stang sortate dupa $y$. Astfel, la nivel impar punctele vor fi mediane din sirul punctelor sortat dupa $x$, iar la nivel par punctele vor fi mediane din sirul punctelor sortat dupa $y$. Pentru mai multe dimensiuni ale spatiului ciclam dupa $d{~1~}$, $d{~2~}$,..., $d{~n~}$ si apoi iar $d{~1~}$ ca sa punem elementul median pe nivelul curent. In cazul 2D complexitatea crearii unui asemenea arbore e O(n log n). Pentru a raspunde la query-uri pe un dreptunghi coboram in arbore in fii pentru care domeniul asociat se intersecteaza cu dreptunghiul nostru. Se poate demonstra ca aceasta operatie are timpul de executie in cel mai rau caz O(sqrt(n)).

_kD-Tree_ este o structura de date care organizeaza o multime de puncte in $k$ dimensiuni, imparte spatiul in semispatii astfel ca fiecare nod din arbore reprezinta un paralelipiped si contine in el un punct. Noi suntem interesati de arbori 2D in special. Pentru cazul 2D, primului nod ii va fi asociat intreg planul. Se duce o linie verticala de abscisa $x$ care imparte planul in doua si punctele in doua multimi de cardinal egal. Subarborele din stanga va contine toate punctele din stanga acestei drepte verticale, iar subarborele din dreapta va contine toate punctele din dreapta acestei drepte verticale. Radacinei arborelui din stanga ii va fi asociat semiplanul stang determinat de dreapta verticala, si va contine punctul median dintre punctele din semiplanul stang sortate dupa $y$. Astfel, la nivel impar punctele vor fi mediane din sirul punctelor sortat dupa $x$, iar la nivel par punctele vor fi mediane din sirul punctelor sortat dupa $y$. Pentru mai multe dimensiuni ale spatiului ciclam dupa $d{~1~}$, $d{~2~}$,..., $d{~n~}$ si apoi iar $d{~1~}$ ca sa punem elementul median pe nivelul curent. In cazul 2D complexitatea crearii unui asemenea arbore e O(n log n). Pentru a raspunde la query-uri pe un dreptunghi coboram in arbore in fii pentru care domeniul asociat se intersecteaza cu dreptunghiul nostru. Se poate demonstra ca aceasta operatie are timpul de executie in cel mai rau caz O(sqrt(n)).
 
Unele implementari tin puncte numai in frunze, si in nodurile care nu sunt frunze tin numai informatia despre coordonata dreptei care imparte regiunea in doua. Dimensiunile regiunii asociate unui nod pot fi tinute in nod sau pot fi calculate la fiecare operatie pentru a salva spatiu. O alta idee pentru a mari viteza de cautare in arbori kD ar fi sa nu alegem ciclic pe ce directie impartim punctele, ci sa alegem la fiecare pas directia pe care punctele sunt cele mai imprastiate.
 
Pseudocod pentru constructie:
 
== code(cpp) |
==