KD-Tree實現

Question

我正在嘗試編寫自己的KD-Tree實現並最終實現kNN。而且我很難理解KD-Tree如何構建搜索樹。

對維基百科而言，它表示它找到值的中位數並將其用作樹的根。

但是，如果有很多維度，你將如何計算中位數？

Answer 1

它不是需要找到位數：維基百科：

還要注意的是，不要求選擇中點。在那 的情況下，結果很簡單，不能保證樹 將被平衡。避免編碼複雜線性時間中間查找算法或使用O（n log n）種類的所有n個點的簡單試探法是使用排序來查找隨機選擇的點的固定數目的中值作爲分裂平面。在實踐中，這種技術通常會產生很好的平衡樹木。

KD-Tree from wikipedia

Answer 2

你沒有發現在幾個方面中位數（事實上，對於多維數字沒有意義的順序）。在kd樹的每一層，你都關注一個維度。您根據此維度選擇中位數，忽略其他組件。

請注意，除中位數外，您可以使用許多標準，具體取決於您想要執行的操作。同樣，選擇一個好的方案來決定每個節點的維度是一門藝術，但實際上每個方案都是正確的。

Answer 3

你可以簡單地根據排序爲一維的點，然後選擇 中位數爲根，然後遞歸構建子樹（與其他維度排序） 這裏是一個實現： https://github.com/tavaresdong/cs106l/blob/master/KDTree/src/KDTree.h