问题标签 [range-tree]

我目前正在实施一个二维范围树。我无法为我的 Node 类提出一个合理的模型（Java 中）。

树中的节点可能具有以下任何内容：中间值、左右子指针、子树、数据指针和/或前一个和下一个指针。

我已将节点分解为三个独立的逻辑部分

• a) 只有 midRange 值的节点 - 每个节点都有一个 midRange
• b) 具有左、右和子树点的节点。这表示一个非叶节点。
• c) 不适用于 next、prev 和 data 指针。这代表一个叶节点。

我尝试应用 Composite 和 Decorator 模式，但无济于事。我尝试制作：

1. 具有所有可能的 getter/setter 的节点接口，即：getMidRange、getLeft、getRight、setLeft、setRight 等...
2. 有两个类实现接口：Node2D 和 LinkedNode（叶节点）。Node2D 做了所有事情，除了保留下一个和上一个的链接。而 LinkedNode 只保留下一个和上一个的链接。

它是这样工作的，但是如果有更好的方法将其建模为一组类，我会徘徊吗？

编辑：范围树（简短信息）：在范围树中 - 所有数据都存储在叶节点中，并且树总是平衡的。此外，所有叶子都处于相同的高度。此外，叶子被排序，并通过双向链表链接在一起。最后但并非最不重要的一点是，每个非叶子节点都有一个子树——它也是一个范围树，但叶子按下一个属性排序（如果原始树按x排序，则说y）。

我正在寻找 Ruby 中的范围或段树实现。我找不到任何可用的样品或宝石。

有人有示例代码吗？

谢谢，

我正在做这个项目，我必须在 3d 空间中搜索对象，效率是一个巨大的问题，我认为Range Tree非常适合我正在尝试做的事情，Interval Tree 也可以，但我不是要从树中删除任何东西，一旦我在 3D 空间中添加了每个对象，我将只使用该结构进行搜索。

以下是我将如何使用该结构：

假设我有一个对象数组（我们称之为queryArr）（〜 10,000 个对象）每个对象都有 3 个参数（x，y，z）我有另一个非常大的对象数组（我们称之为totalArr）（> 5,000,000 个对象） ）。

我在这里尝试做的是给定queryArr的元素，找到最相似的（或 totalArr 中的相同元素）在某些情况下，在totalArr中会有一个具有相同参数的对象，但在大多数情况下，不会是具有相同参数的对象。

因此，我将搜索 和 之间的所有(x+10,y+10,z+10)值(x-10,y-10,z-10)。如果它没有产生任何结果，我将 x,y,z 乘以 2 并重试，直到它产生一些结果。

最简单的方法是简单的搜索方法，它具有复杂性， O(N*M) (N = size of queryArr, M = sie of totalArr)但这种方法非常缓慢和愚蠢。

我认为范围树是要走的路，但我自己从未实现过，而且我不太了解范围树如何在大于 2 的维度上工作。那么有人知道范围树的良好实现吗？我相信如果我有源代码，我将能够理解它们是如何工作的。

顺便说一句，如果您认为对于这项任务有比 Range Tree 更好的结构，请告诉我我愿意接受建议。（我已经考虑过 kd-Trees 和区间树）

谢谢，

一段时间以来，我一直在尝试理解范围树，但我仍然无法理解。

有人可以通过实现向我解释吗，因为我想用它来解决 2D RMQ，我知道分段树，我的老师告诉我范围树类似于 2d 分段树，但我就是想不出空间如何复杂度可以小于 n^2，如 2d 段树。

我不确定这一点，但它是真的吗，它就像合并排序，所以内存将小于 n^2 使用向量

谢谢 ：）

嗨，我正在尝试为 rmq-ing 实现 2D 范围树，这是我的代码，我认为它不够高效，有什么我可以做的优化。

ls 包含在每个节点上排序的 y 列表

rt 包含一个段树

p.fi.fi 包含 x 坐标

p.fi.se 包含 y 坐标

p.se 包含点的 id

loc 包含每个 id 的 x 节点和 y 节点

如果代码是一团糟，我很抱歉，因为这是我第一次实现范围树

我当前的实现运行了大约 4 秒，但我需要它运行不到 3 秒，这是我的完整 实现

谢谢 ：）

我在 7 维空间中有大约 10^4 个点。对于某个应用程序，我需要对此输入进行 ~10^6 范围查询，以查找位于给定范围内的所有点。在此应用程序中，所有查询都使用相同的范围大小。这个问题的合适数据结构是什么？

kd-tree 似乎很合适，但对于 7 维和小输出大小，它的查询时间复杂度几乎是线性的。另一种解决方案是范围树，但对于此应用程序中的少量输入而言，构建它似乎过于复杂。此外，我没有看到任何这些结构利用范围是恒定大小这一事实来发挥它们的优势。例如，如果这是一个 1D 问题，则所有查询都将要求位于大小为 10 的范围内的点，例如，沿数轴的不同位置。

家庭作业

我需要使用数据结构+算法返回由2个（x，y）值组成的范围内的元素数量（即返回在xy平面上的矩形范围内的元素数量）在O（logn *登录）。

我正在考虑两种可能性，kd-tree 和 range 树。kd-tree 非常适合这种情况，因为它可以在 O(logn + k) 范围内找到元素（对于需要报告的 k 个元素）。但我不需要报告元素，我只需要计算范围内的元素数量。

范围树可以在其中工作，我可以在每个节点中拥有一个属性，该属性包含多少小于自身。这样，我可以确定有多少元素小于 O(logn) 次中的特定值（通过转到两个边界并找到彼此小于的节点数的差异）。但是，我认为这不适用于同时具有 (x,y) 维度的数据集。

我在正确的轨道上吗？

我有一个要求，我必须根据某些属性值更新图形前端的颜色。属性值有不同的范围......比如说 -30 到 -45，-60 到 -80 等等...... .所以，我需要一个可以存储这些范围（预填充它们）的数据结构......当我确定点时，我想知道该点在 O(1) 时间或 O 中的范围（logN）时间......所以，我的查询将由一个点组成，输出应该是包含该点的唯一范围......

我对范围树和段树感到困惑......我想在 c++ stl 映射之上构建树。

我需要解决一个邻居搜索问题，即对于每个给定元素，找到固定距离内的所有邻居元素。

我刚刚学习了数据结构range tree，它似乎能够在 O(N*(log(N)^(d-1))) 复杂度中解决这个问题，其中 d 是空间的暗淡。

我对此一无所知R-tree，但只是从维基百科上看到了这个：

R-tree 在现实世界中的常见用法可能是……然后快速找到诸如“查找我当前位置 2 公里范围内的所有博物馆”之类的查询的答案，

这似乎正是我想要解决的问题。

那我应该学习和使用这个数据结构吗？</p>

我正在寻找一些用于范围搜索的数据结构。我认为范围树提供了很好的时间复杂度（但有一些存储要求）。

然而，在我看来，其他数据结构，如KD-trees，比范围树更受讨论和推荐。这是真的？如果是这样，为什么？