Beskrivelse

KD-Træer bruges til at repræsentere en punktmængde således at der effektivt kan foretages forespørgsler på denne mængde. I den aktuelle implementation, som implementerer 2 dimensionelle træer, vil der kunne findes den mængde af punkter der ligger indenfor et givet rektangulært vindue. Algoritmen lader sig dog generalisere til højere dimensioner.
Algoritmen der er fulgt stammer fra bogen:

"Computational Geometry, Algorithms and Applications",
by M. de Berg et. al.
Springer Verlag 1997. ISBN3-540-61270-X

Se applet i aktion (java skal være aktiveret.)
Beregning af KD-Træ:

						input: A set of points: P, and the current depth: depth

						output: the root of a kd-tree storing P



						buildTree(P, depth)


						1:if P contains only 1 point then

						2:return a leaf storing this point.

						3:else if depth is even

						4:Split P into two subsets with a vertical line l through the

						5:median x-coordinate of the points of P. Let P1 be the

						6:point from P to the left of l, and P2 be the points in P to

						7:the right of P

						8:else (the depth is odd)

						9:Split P into two subsets through a horizontal line l.

						10:Let P1 the the points from P that lies below P, and 

						11:P2 the the points above P.

						12:VleftORbelow = BuildKDTree(P1, depth+1)

						13:VrightORabove = BuildKDTree(P2, depth+1)

						14:Create a node v storing l (the median point). Make VleftORbelow the

						15:left child of v, and VrightORabove the right child of v.

						16:return v
Variablen: depht i ovenstående algoritme sikre at der hver anden gang splittes horisontalt, og hver anden gang vertikalt.