0

我正在寻找一种有效的方式来表示和检索地理关系，例如。地区->州->美国。这应该适应任何层次的层次结构，例如。地区->地区->州->大地区（东/西/南/北）->美国。

我的要求是

  1. 我主要在最低级别操作 - 所以让他们快速完成应该是第一要务。优选恒定时间。
  2. 然后，我想轻松地在州级别执行聚合，例如合并地区数据（因此获取节点的所有子节点） - 这是第二个标准。
  3. 一个级别的订单无关紧要 - 例如。对于北卡罗来纳州，我不介意我先得到罗利还是费耶特维尔。

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

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

我的直觉是应该有有效的解决方案，因为 Windows 或任何文件系统都会这样做。文件->文件夹->大文件夹->C->我的电脑。这种计算也必须在数据挖掘中完成，比如说集群（我记得读过这类的东西）

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

谢谢

4

2 回答 2

1

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

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

于 2009-06-02T14:10:16.750 回答
0

创建一个节点树，其中每个节点包含：

  • 指向父节点的指针（或根节点为空）
  • 子节点的集合（例如 Java 中的 HashMap 或 ArrayList）
  • 与节点关联的任何数据负载（例如地理坐标，以便您进行距离搜索）

如果您愿意，您可以使用基于 HashMap 的 String -> Node 索引来扩充它，以便对节点进行 O(1) 访问。但是对于这个问题，我不会担心树搜索成本，因为您最多可能拥有超过 5-10 个级别。

于 2010-06-15T16:20:11.877 回答