如何处理r树和四叉树的重复点

Question

我正在考虑实现四叉树和r-树数据结构，以测试处理二维点分布的一些想法。我的问题是，这些算法是如何处理重复点的?或者处理重复点的技巧是什么?

Answer 1

最可能的是忽略/删除重复点

Answer 2

需要小心。朴素的实现将尝试继续分割，直到元素的最大数量小于m(默认m=1)。如果你有m+1个副本，它就会进入一个无限循环。因此，您需要删除和处理重复点。

r树更好。有重叠的页面是完全合理的。因此，即使只包含重复项的页面溢出，您也可以拆分它。R-tree拆分总是需要将数据拆分为两个相同大小的页面。