我怎麼能做這個KD樹？

我有一個很長的，半排序的緯度，經度和時區三連音列表。我希望能夠快速搜索這個列表以找到任何給定經度和緯度的最近時區，所以我想將這個列表變成KD樹。我怎麼能做這個KD樹？

我在想，我應該先讀取整個文件進入某種數據結構（數據結構是什麼？可能是ArrayList<Triplet<Double, Double, String>>？）。然後採用該結構中的中值元素，並將其作爲根，留下左右列表。然後繼續使用每個列表的中間元素並將其添加爲左側或右側的子元素。

對此的第一次嘗試似乎是緩慢和低效......但我覺得我做錯了。你可以爲我提供一個算法或僞代碼來處理我想要做的事嗎？

2012-10-01 Kalina

讓我知道你是否對KDTree有任何疑問。如果它仍然很慢/效率低下，請告訴我。我好奇！ – Justin

我將您的實現與Java-ML（http://java-ml.sourceforge.net/）中的KDTree實現進行了比較，而您在提取k個最近鄰居方面速度較慢。你的界面更好:) –

另外，這裏有一些更快的實現：http://robowiki.net/wiki/Kd-tree#Implementations –

如果有幫助，我有一個KD-Tree in Java它將XYZ視爲內部類中稱爲XYZPoint的雙打。您可以使用時區數據增加XYZ點，並使用X代表經度，Y代表緯度，Z代表零點。它至少可以作爲起點。

然後，您可以使用最近鄰居（歐氏距離）方法，該方法已經實施，用於距離某個點最近的時區。

另外..爲填充KD-Tree，wikipeda建議使用HeapSort (my Java implementation linked)並重復刪除中位數。

2012-10-01 01:08:58 Justin

回答