我遇到一个问题,高维区间树可能会有所帮助。我可以理解一维区间树是如何工作的。但我看不出在更高维度应该如何实现。
区间树和范围树
维基百科的解释说对每个维度使用范围树和区间树。但我看不出它是如何工作的!我不清楚那里的解释......请检查“更高维度”部分:
首先,构建一个 N 维的范围树,它可以高效检索查询区域 R 内起点和终点的所有区间。一旦找到相应的范围,剩下的就是包含该区域的那些范围某个维度。如果范围树更高效,为什么还需要区间树?
对于“范围树”,我们可以看到它是为区间内的查询点创建的(树不存储区间)。因此,我假设维基百科的意思是:
首先,构建 N 维范围树,允许高效检索查询区域 R 内具有起点或终点的所有区间。
然后..什么?如果我从此时开始为每个维度创建一个区间树,则即使原始对象与我的查询不相交,这些区间中的任何一个都将位于我的搜索框上。请检查下面的图片,尝试形象化我所说的内容。
也许,我不清楚的是:如何交叉两个区间树的区间结果以确保它位于一个实体上?
R树
顺便提一下,我知道 R Tree 的存在。但我想先了解高维的区间树。此外,正如注释一样,在维基百科
他们说:R Tree 使用 MBR 对实体进行分组,而 Interval Tree 使用点。我强烈不同意。否则,为什么我们应该谈论高维区间树?如果我很好地理解这两种方法:
R Tree 可以存储任何类型的空间实体,而 Interval Tree 只存储间隔。
R Tree 需要时不时地分裂节点,这似乎很昂贵。区间树永远不会分裂节点。
范围树用于获取具有查询超立方体内顶点的轴对齐超立方体 - 所有这些超立方体都与查询超立方体相交。