平衡KD树

Question

因此，当平衡KD树时，您应该找到中位数，然后将左侧子树中较少的元素和右侧较大的元素。但是如果你有多个与中位数相同的元素会发生什么？他们进入左边的子树，右边还是丢弃它们？

我问，因为我试过做多件事情，它会影响我最近邻搜索算法的结果，并且在某些情况下树的给定部分的所有元素都将具有完全相同的值，所以在这种情况下，我不知道如何拆分它们。

Answer 1

在执行搜索风格算法时，在中间值的两侧放置元素等于中位数通常是个好主意。

一种方法是将“中间等值”元素放在“相同的一侧”，与之前执行分区前的位置相同。另一种方法是将第一个放在左边，第二个放在右边等。

另一种解决方案是拥有一个聚合数据结构，它可以“统计”相同的事物，而不是单独存储每个数据结构。 （如果他们有额外的状态，那么你可以存储该额外的状态，而不是只是一个计数）

我不知道哪个适合您的情况。

Answer 2

它放在哪里并不重要。最好保持你的树木平衡。因此，根据需要放置在左侧尽可能多地保持最佳平衡！

如果您当前的搜索半径触及的中位数，您将不得不检查另一部分，这就是所有您需要处理另一边的绑定对象。这通常比一些在任何地方连接多个元素的复杂处理要便宜。

Answer 3

这取决于你的目的。

对于诸如精确匹配或范围搜索，两边相同的值将相同值的查询和重复两个叶片复杂将增加的时间复杂度重复的可能性问题。

解决方案是在节点上存储所有的中位数（等于中位数的值），既不左也不右。 kd-trees的大多数变体都将中位数存储在内部节点上。如果它们碰巧很多，你可以考虑使用另一个（k-1）d树作为中间值。