How could I make this KD-tree?

Question

I have a very long, semi-sorted list of latitude, longitude, and time zone triplets. I want to be able to search this list quickly to find the closest time zone to any given latitude and longitude, so I would like to make this list into a KD tree.

I'm thinking that I should read the entire file first into some sort of data structure (what data structure? Possibly ArrayList<Triplet<Double, Double, String>>?). Then take the median element in that structure and make it the root, leaving me with a left and right list. Then keep taking the median element of each list and adding it as a left or right child.

A first attempt at this seemed slow and inefficient... But I feel like I did it wrong. Can you provide me with an algorithm or pseudocode for what I'm trying to do?

Answer 1

If it helps, I have a KD-Tree in Java which takes in XYZ as doubles in a inner class called XYZPoint. You could augment the XYZ Point with the time zone data and use X for Longitude, Y for Latitude, and zero for Z. It could at least be a starting point.

You could then use a nearest neighbor (euclidean distance) method, which is already implemented, for the closest time zone to a point.

Also.. for populating the KD-Tree, wikipeda suggests using HeapSort (my Java implementation linked) and removing the median repeatedly.