KD Tree- order 2

Unlike with the skiplist you are free to implement the kd tree any way you like with no particular interface. I will though recommend the use of java's point classes (point2d) which will allow you to easily make use of java's geometric algorithms later on. I would also suggest that you generally try to follow the java Collection interface. Standards are good things ;) Examining the command decoder, pay particular attention to the MAP_ALL() function, which represents to the most common historical use of a kd tree. The primary purpose of the kd tree is to perform 'orthogonal range search' (ie. the rectangle search in the command decoder), which with a balanced tree has guaranteed O(sqrt(n)+k) run time, where k is the number of elements actually found. You'll note that you can count the number of points without actually visiting them all in O(sqrt(n)) time.

Web Accessibility