平衡KD树

Question

平衡KD树

3

当平衡 KD 树时，按中位数分割元素，将小于中位数的元素放在左子树，大于中位数的元素放在右子树。但是，如果有多个元素与中位数相同怎么办？它们应该放在左子树、右子树还是丢弃？我问这个问题是因为我尝试了多种方法，但结果影响了最近邻搜索算法的结果，而且在某些情况下，给定部分树中的所有元素都具有完全相同的值，因此我不知道如何在这种情况下拆分它们。

- user1855952

你的搜索受到了多大的影响？可能会出现多个中位数元素，但我认为它们放置的位置不会有太大的区别。总会有情况下你的树结构并不是最优解，但在一般情况下应该是有效的。 - RonaldBarzell

3个回答

2

在进行搜索算法时，通常将等于中位数的元素放置在中位数两侧是一个好主意。

一种方法是将中位数相等的元素放置在“相同侧”，即在分区之前它们所在的位置。另一种方法是将第一个元素放在左侧，第二个元素放在右侧，以此类推。

另一种解决方案是使用聚合数据结构，仅“计数”相等的项目，而不是单独存储每个项目。(如果它们有额外的状态，则可以存储该额外的状态，而不仅仅是计数)

我不知道哪种方法适用于您的情况。

- Yakk - Adam Nevraumont

0

这取决于您的目的。

对于精确匹配或范围搜索等问题，两侧可能重复相同值的可能性会使查询变得复杂，并且两个叶子节点上相同值的重复将增加时间复杂度。

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

- Kartal Tabak

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Has QUIT--Anony-Mousse · Accepted Answer

放置节点的位置并不是非常重要，最好保持树的平衡。因此，尽可能将节点放在左侧，以保持最佳平衡！

如果您当前的搜索半径“触及”中位数，则必须检查其他部分，这就是您需要处理另一侧绑定对象的所有内容。这通常比在任何位置附加多个元素更便宜。