36
4.
then
sp lit
P
into
two
subsets
with
a
vertical
line
l
through
the
median
x-coordin ate of the p oints in P. Let P1 be the set of
p
oints to the left of l or on l, and let P2 b e the set of p oints
to the right of l.
5.
else
sp lit
P
into two subsets
with a
horizontal
line
l
through the
median
y
-coordinate of the p oints in P. Let P1 be the set of
p
oints below l or on l, and
let P2 be the set of p oints above
l.
6. v
left
?
BUILDKDTREE(P1,depth + 1)
7. vr
ight
?
BUILDKDTREE(P2,depth + 1)
8. Create a node v storing l , make v
left
the left child of
v, and
make vr
ight
the right child of v.
9. return v
Gambar 2.9
Algoritma pembentukan Pohon Berdimensi K
2.8.2
Algoritma kueri
Pada
saat
diber ikan
sebuah
rentan g (range)
d
alam
d
dimensional,
algoritma
ku eri
p
ada
p
ohon
berdimensi
k
ak an
melap orkan
titik
man a
saja
y
ang
berada dalam rentan g. Simp ul dalam p ohon berdimensi k
meny atakan
suatu daerah b erbentuk bidan g (d alam 2 d imensi)
atau
 |