A Java implementation of the K-d Tree data structure.
Given an arbitrary set of points in k
-dimensions, implement a data structure in which the runtime of range search and nearest-neighbor search is, on average, better than linear in the number of points.
In this implementation, k = 2
.
An excellent discussion of the Kd-Tree data structure can be found at Princeton's Algorithms and Data Structures, Part I website.
This project was completed for Algorithms, Part I.
If you're in that course or related course right now, obey all honor code requirements before viewing this code.
I recommend that this code should only be viewed after you've completed your own implementation.
If you're super stuck, take a break, take a walk, and it will come to you; good luck.