37
hyperlane
dalam
d
dimensi.
Untuk
sebuah
simp ul
v,
daerah
y
ang
direp resentasikan oleh v diny atakan oleh region(v).
Region
y
an g
diny atakan
oleh
simp ul
dalam
p
ohon
berdimensi
k dap at
memiliki b atas
ataup un tidak. Sebuah titik berada d alam subtree dengan
root u, jika d an
hany a
jik a titik tersebut
berada dalam reg ion(u).
Dalam
algoritma kueri, d ilakuk an
den gan
menelusuri p ohon dengan
DFS(Depth
First
Search), suatu
simp ul
dikunjungi
h
any a
jika
region
dari
simp ul
tersebut berp otongan dengan rentan g kueri, R.
Algorithm SEARCHKDTREE(v,R)
Input. The root of (a subtree of) a kd-tree, and a ran ge R.
Output. All p oints at
leaves below v that
lie in the range.
1.
if v is a leaf
2. then
Rep ort
the p oint stored at v if it
lies in R.
3.
else if region (lc(v)) is fully contained in R
4. then REPORTSUBTREE((lc(v))
5. else if region (lc(v)) intersects R
6. then SEARCHKDTREE(lc(v),R)
 |