平衡KD樹

Question

因此，當平衡KD樹時，您應該找到中位數，然後將左側子樹中較少的元素和右側較大的元素。但是如果你有多個與中位數相同的元素會發生什麼？他們進入左邊的子樹，右邊還是丟棄它們？

我問，因爲我試過做多件事情，它會影響我最近鄰搜索算法的結果，並且在某些情況下樹的給定部分的所有元素都將具有完全相同的值，所以在這種情況下，我不知道如何拆分它們。

Answer 1

在執行搜索風格算法時，在中間值的兩側放置元素等於中位數通常是個好主意。

一種方法是將「中間等值」元素放在「相同的一側」，與之前執行分區前的位置相同。另一種方法是將第一個放在左邊，第二個放在右邊等。

另一種解決方案是擁有一個聚合數據結構，它可以「統計」相同的事物，而不是單獨存儲每個數據結構。 （如果他們有額外的狀態，那麼你可以存儲該額外的狀態，而不是隻是一個計數）

我不知道哪個適合您的情況。

Answer 2

它放在哪裏並不重要。最好保持你的樹木平衡。因此，根據需要放置在左側儘可能多地保持最佳平衡！

如果您當前的搜索半徑觸及的中位數，您將不得不檢查另一部分，這就是所有您需要處理另一邊的綁定對象。這通常比一些在任何地方連接多個元素的複雜處理要便宜。

Answer 3

這取決於你的目的。

對於諸如精確匹配或範圍搜索，兩邊相同的值將相同值的查詢和重複兩個葉片複雜將增加的時間複雜度重複的可能性問題。

解決方案是在節點上存儲所有的中位數（等於中位數的值），既不左也不右。 kd-trees的大多數變體都將中位數存儲在內部節點上。如果它們碰巧很多，你可以考慮使用另一個（k-1）d樹作爲中間值。