因此，在平衡 KD 树时，您应该找到中位数，然后将所有较小的元素放在左子树上，将较大的元素放在右边。但是，如果您有多个元素的值与中位数相同，会发生什么？它们进入左子树，右子树还是丢弃它们？
我问是因为我尝试过做多件事，它会影响我最近邻搜索算法的结果，并且在某些情况下，树的给定部分的所有元素都将具有完全相同的值，所以我不知道在这种情况下如何将它们分开。
问问题
2848 次
3 回答
5
你把它们放在哪里并不重要。最好保持你的树平衡。因此，根据需要在左侧放置尽可能多的位置以保持最佳平衡！
如果您当前的搜索半径触及中位数，您将不得不检查另一部分，这就是您在另一侧处理捆绑对象所需的全部内容。这通常比在任何地方附加多个元素的复杂处理便宜。
于 2012-12-24T23:12:02.077 回答
2
在进行搜索风格算法时，将等于中位数的元素放在中位数的两侧通常是一个好主意。
一种方法是将中值相等的元素放在与分区之前相同的位置。另一种方法是将第一个放在左侧，将第二个放在右侧，依此类推。
另一种解决方案是拥有一个集群数据结构，它只是“计算”相等的事物，而不是单独存储每个事物。（如果他们有额外的状态，那么你可以存储额外的状态而不仅仅是一个计数）
不知道哪个适合你的情况。
于 2012-12-18T00:59:30.667 回答
0
这取决于你的目的。
对于精确匹配或范围搜索等问题，在两边重复相同值的可能性会使查询复杂化，并且在两个叶子上重复相同值会增加时间复杂度。
一个解决方案是在节点上存储所有的中位数（等于中位数的值），既不左也不右。kd 树的大多数变体都将中值存储在内部节点上。如果它们碰巧很多，您可以考虑使用另一棵 (k-1)d 树作为中位数。
于 2013-06-23T19:37:35.027 回答