问题标签 [range-tree]

我正在尝试实现一个范围树，但我真的很困惑，这是我的文字：

现在假设我有一棵这样的树：

我想找到 14 和 19 之间的点。V_Split这里是 17，从 17 移动到 14，根据算法，我应该报告 17 的右子树，即 23 和 19。但是 23 不在 14 之间和 19. 我应该在这里做什么？

如果我不考虑 17，则不会报告 17 本身。再说一次，如果我想找到 12 到 19 之间的点，14 将不包括在内！

我阅读了几张幻灯片，比如这个的最后一页，其中描述了搜索算法。但是，我有一个基本问题。数据位于二维空间中。

我首先根据点的 x 值构建一个二叉搜索树。每个内部节点都持有一个基于位于该内部节点子树中的点的 y 值的 BST。

然后我想我应该搜索位于范围查询 [x1, x2] 中的点，然后检查是否满足请求的 [y1, y2] 范围查询。但是，该算法建议您应该在内部节点的基于 y 的 BST 中搜索，如果内部节点的范围在 [x1, x2] 内，但我不明白。

如果我们这样做，那么在我的一个例子中，我们将搜索（没有理由）根的基于 y 的 BST。检查示例：

我希望执行的范围查询是 (-oo, 1) x (0, 5) ^*。

如果我查看根，它的值为 0，因此它包含在 (-oo, 1) 中，所以如果我遵循算法，我将搜索整个根的基于 y 的树？

那应该是一棵包含所有点的树，因此在基于 x 的树中继续搜索是没有意义的。此外，这将导致访问的节点多于必要的节点。

_{如果这很重要，我正在c++中实现它。}

*_{对 [-inf, 1] 范围内的 x 和 [0, 5] 范围内的 y 执行范围查询。}

我找到的唯一合理的幻灯片集是this，在第 15 页中说，用于构建：

• 将所有点按其 x 坐标值排序，并将它们存储在平衡二叉树（即范围树）的叶节点中
• 从根开始，每个节点都包含其子树中的点，其 y 坐标的最大值尚未存储
  在树中较浅的深度；如果不存在这样的节点，则节点
  为空

我之前实现了一个范围树，所以根据我在那里使用的示例，我现在有（对于优先搜索树）：

在这里，每个内部节点都具有以下形式：

我提出的范围查询是（-inf，1）x（-0.5，5），即（x_low，x_high）x（y_low，y_high）。

1. 所以，让我们从根开始，我检查 x (=0) 是否在 (-inf, 1) 中，如果 7 > (-0.5, 5)。是的，因此我在两个孩子中进行，但为简单起见，让我跟随左边的孩子（从现在开始）。
2. 我检查 -3 是否是 x 范围，以及 6 是否大于或等于查询的 y 范围的上限（即 5）。是的，所以我继续。
3. 下一层也一样，因此我们进入下一层，现在请关注这个内部节点。它有 as max ya 0，表示子树的最大 y 为 0，这是不正确的（左孩子为 (-5, 6)) ^*。

我在构建/搜索过程中缺少什么？

换句话说：

检查树的最左边的分支；它的max_y值（引用中的第 2 个项目符号）为 7、6、4、0。

但是那个值不是表示存储在内部节点下的子树中的最大 y 值吗？0如果是这样，这对于和点不成立(-5, 6)（不使用 6，因为它用于第 2 级）。

*_{我提出的特定查询可能不会因此而受损，但另一个可以。}

我遇到了一个问题，高维区间树可能会有所帮助。我可以理解一维区间树是如何工作的。但我看不出应该如何在更高的维度上实现。

区间树和范围树

Wikipedia上的解释说对每个维度使用范围树和区间树。但我看不到它是如何工作的！我不清楚那里的解释......请检查“更高维度”部分：

首先，构建一个 N 维的范围树，它允许有效地检索具有查询区域 R 内起点和终点的所有区间。一旦找到相应的范围，剩下的就是那些将区域包围在某个范围内的范围。方面。

如果范围树更有效，为什么我们需要区间树？

对于Range Trees，我们可以看到它是为区间内的查询点制作的（树不存储区间）。因此，我假设维基百科的意思是：

首先，构建一个 N 维的范围树，它允许有效地检索查询区域 R 内具有开始或结束点的所有区间。

然后..什么？如果我从此时开始为每个维度创建一个区间树，即使原始对象不与我的查询相交，这些区间中的任何一个都将位于我的搜索框上。请检查以下图片以尝试可视化我在说什么。

也许，我不清楚的是：如何交叉两个区间树的区间结果以确保它位于一个实体上？

有人可以解释在这种情况下如何使用范围树吗？

R树

顺便提一下，我知道 R Tree 的存在。但我想先了解高维的区间树。此外，就像注释一样，在维基百科他们说：

区间树——一维（通常是时间）的退化 R 树。

我强烈不同意。否则，我们为什么要谈论高维区间树？如果我很好地理解这两种方法：

R Tree 使用 MBR 对实体进行分组，而 Interval Tree 使用点。

R Tree 可以存储任何类型的空间实体，而 Interval Tree 只存储区间。

R Tree 需要时不时地拆分节点，看起来很昂贵。区间树从不拆分节点。

注意：问题底部有一个重大编辑 - 看看

问题

假设我有一组要点：

我想找到它周围点最多的点，在半径内（即圆形）或在二维点的半径内（即正方形）。我将其称为最密集点函数。

对于这个问题中的图表，我将周围区域表示为圆圈。在上图中，中间点的周围区域显示为绿色。这个中间点具有半径内所有点中最周围的点，并将由最密集的点函数返回。

我试过的

解决此问题的一种可行方法是使用范围搜索解决方案；这个答案进一步解释了它有“最坏情况时间”。使用它，我可以获得每个点周围的点数，并选择周围点数最多的点。

但是，如果这些点非常密集（大约一百万），那么：

那么这百万个点（）中的每一个都需要执行范围搜索。对于以下点树类型，最坏情况时间（其中是范围内返回的点数）为真：

• 二维的 kd-trees（实际上稍微差一点，在 处），
• 二维范围的树，
• 四叉树，最坏情况时间为

因此，对于组内所有点的半径内的一组点，它给出了每个点的复杂度。这产生了超过一万亿次操作！

关于实现这一目标的更有效、更精确的方法的任何想法，以便我可以在合理的时间内（最好或更少）找到一组点周围点最多的点？

编辑

原来上面的方法是正确的！我只需要帮助实现它。

(半)解决方案

如果我使用二维范围树：

• 一个范围报告查询成本，对于返回的点，
• 对于具有分数级联的范围树（也称为分层范围树），复杂度为，
• 对于 2 维，即，
• 此外，如果我执行范围计数查询（即，我不报告每个点），那么它的成本为.

我会在每一点上执行这个 - 产生我想要的复杂性！

问题

但是，我无法弄清楚如何为二维分层范围树的计数查询编写代码。

我找到了关于范围树的一个很好的资源（从第 113 页开始），包括二维范围树伪代码。但是我不知道如何引入分数级联，也不知道如何正确实现计数查询，因此它很O(log n)复杂。

我还在这里和这里在 Java 中找到了两个范围树实现，在 C++ 中找到了一个，尽管我不确定这是否使用分数级联，因为它在countInRange方法上方指出

它返回最坏情况下此类点的数量 * O(log(n)^d) 时间。它还可以在最坏的情况下返回矩形中的点 * O(log(n)^d + k) 时间，其中 k 是矩形中的点数。

这对我来说表明它不应用分数级联。

提炼的问题

因此，要回答上述问题，我只需要知道是否有任何具有分数级联的二维范围树的库具有复杂的范围计数查询，所以我不去重新发明任何轮子，或者你能帮我吗？编写/修改上述资源以执行该复杂性的查询？

如果您可以为我提供任何其他方法以任何其他方式实现二维点的范围计数查询，也不要抱怨！

是否有任何库提供具有分数级联的 2d 范围树，具有O(log n)范围计数查询的复杂性（即，O(log^(d-1) n)对于 d 维度）？

我发现的一个有前途的代码片段是https://github.com/elazarl/RangeTree/blob/master/src/main/java/com/github/elazarl/rangetree/RangeTree.java - 但是我不知道如何修改此代码，以便我只计算范围计数，而不是报告范围计数。

我知道我可以通过为每片叶子添加一个计数，然后在我遍历时对叶子求和来做到这一点。但是我无法用分数级联来弄清楚！

假设您S在二维平面上有一组独特的点。现在，您期待着一堆“点p存在于S？”形式的问题。你决定建立一个范围树来存储你的S问题并回答这个问题。范围树背后的基本思想是，您首先Tree0在0-th坐标上构建平衡二叉搜索树，然后在此构建的每个节点上再Tree0构建另一个平衡搜索树Tree1，但这次使用1-st坐标作为键。Range Tree 的维基百科文章。

现在，我期待Tree1为 的每个节点构建的n0那些Tree0点将准确地保存其0-th坐标等于键 from 的那些点n0。但是，如果您阅读有关范围树的更多信息，您会发现情况并非如此。具体来说：

1. 的根r0包含Tree0包含Tree1所有点的 a。
2. 的左孩子r0包含 a Tree1，其中包含0-th坐标小于0-th处坐标的所有点r0。
3. 的右孩子r0包含 a Tree1，其中包含0-th坐标大于 from的所有点r0。

如果你继续这个逻辑，你会看到在 Range Tree 的每一层，所有的点都只存储一次。因此，每个级别都需要n内存，并且由于平衡的深度Tree0是logn，这O(nlogn)就是内存要求。

但是，如果您只存储其0-th坐标与节点处的键完全匹配的点，那么您将在整个树（而不是树的每个级别）中存储每个点一次，这会产生O(n)内存需求。

在范围树中每个级别存储一次点的原因是什么？它是否允许某种很酷的范围查询或其他东西？到目前为止，在我看来，您可以对该版本执行的任何查询O(nlogn)也适用于该O(n)版本。我错过了什么？

我试图弄清楚这个数据结构，但我不明白我们怎么知道有 O(log(n)) 子树代表查询的答案？

这是一张用于说明的图片：

谢谢！

我正在寻找一种算法，可以计算定义区域中二维空间中任意矩形占用的所有网格单元。矩形由它的 4 个角坐标定义。在下图中，我将其中两个标记为红色，网格单元格的坐标为黑色。我正在寻找一个通用案例，它还涵盖未对齐的网格（网格中心！= 底层坐标系的中心），但是在单元坐标 <=> 坐标系之间进行转换是微不足道的并且已经实现。所有单元格都是正方形。

计算在很短的时间内完成了数千次，并且需要尽可能快。

我现在在做什么：

现在我正在计算矩形的边缘（AB、BC、CD、DA）并每sampleRate = cellWidth / 4隔一段时间对它们进行采样。为了找到中间单元格，我从AB + sampleRate * xto构造新行CD + sampleRate * x并在 处再次对这些行进行采样sampleRate。我将在每个采样点找到的所有单元格放入 HashSet 以删除重复项。但我觉得这是非常低效的。

我还考虑将相关区域中的所有单元格抓取到缓冲区中并生成范围树或索引树。然后我可以对矩形的边界进行排队并在 O(log n+m) 处获取所有包含的单元格，但我不确定如何实现它，我什至找不到任何 C# 范围树实现。

我在计算机图形学方面的知识非常生疏，但不应该有一种简单的几何方法无需采样即可工作吗？

我有我用来构建索引RangeTreeIndex的RangeTreeNode类，在插入 2500 条记录之后，我试图将RangeTreeIndex对象保存在我正在接收的文件中StackOverflowError，下面是我的整个代码：

以下是我收到的例外情况：

即使我使用仅传递可序列化对象的Apache commons-lang库类，它也会引发相同的错误。SerializationUtils.serialize

任何人都可以用原始值来面对这个问题吗？