algorithm - 表示地区->州->国家关系的高效数据结构

Question

我正在寻找一种有效的方式来表示和检索地理关系，例如。地区->州->美国。这应该适应任何级别的层次结构，例如。 district->region->states->big region(East/west/south/north) -> 美国。

我的要求是

1. 我主要在最低级别操作 - 所以让所有这些快速完成应该是第一要务。恒定时间优先。
2. 然后，我想在州级执行汇总，例如合并地区数据(因此获取节点的所有子节点)- 这是第二个标准。
3. 级别的顺序无关紧要 - 例如。对于 NC，我不介意我先去罗利还是费耶特维尔。

正如您几乎已经猜到的那样 - 树 数据结构在逻辑上有助于解决这个问题。但是我找不到有效获取所有叶子的方法。我可以在 O(log n) 时间内检查一个节点是否为叶节点，但我已经为此检查了每个节点。

我看过 B、B+ 树，但我不明白的是它们使用升序或降序等某种顺序来维持它们的顺序。

我的直觉是应该有有效的解决方案，因为 Windows 或任何文件系统都可以做到这一点。文件->文件夹->大文件夹->C -> 我的电脑。此外，这种计算必须在数据挖掘中完成，比如说聚类(我记得读过这类东西)

在此方向上的任何线索将不胜感激。

谢谢

Answer 1

您正在谈论检索匹配给定标准的 n 个唯一项目(在这种情况下，在给定节点下层次结构中特定级别的所有内容)。除非预先计算了所有可能的条件，否则无法在固定时间内从数据结构中获取 n 个唯一项。至少您必须遍历那些 n 项。

有许多数据结构和数据结构的组合，您可以使用它们来提高不同类型的使用效率。你说得对，B 树和 B+ 树在这种情况下工作得很好，这就是为什么我建议你为这个应用程序使用关系数据库，因为它们是你将能够实现的最好和最健壮的 B 树找到。匹配的叶节点和计算聚合几乎就是它们的用途。除非您有某些特殊原因不使用 RDBMS 子系统，否则这可能是您最好的选择。