高效的算法来创建一个你知道每个元素路径的树

Question

这可能是一个很容易回答的问题，但由于某种原因，我的大脑一片空白，一直无法想出有效的解决方案。

任务是这样的：我有一些元素，其中包含一个数组（它们的路径）和它们的名称。我想从这个列表中以格式创建一棵树（带符号的特定语法并不重要）

Elements:
  ( name: Element 1,
    Elements:
      ( name: Element 1.1
      )
    Name: Element 2,
    Elements: 
      ( ... )
  )

鉴于以下样式的项目，您对尽可能高效地解决此任务的算法有什么建议吗？

商品样式为：[ Great Grandfather, Grandfather, Father ], Element Name.

并且路线的元素数量可以是任意数量。我能想到的唯一明显的解决方案是从每个父数组中的第一项开始，如果它们不存在则将它们添加到树中，然后移动到 Parents[1] 然后 Parents[2] 等... 有任何想法吗？

Answer 1

我看到至少有两种方法。比较简单的是O(n d ln b)，d是最大深度，b是分支因子，即maximum/average个children每parent.您可能会假设这些常量（因此使用 O(n)），但它们可能在功能上依赖于 n.

另一个是 O(n) 时间，但可能会由于哈希函数错误和其他原因而降级为二次。

版本 1

每个节点保留其 children 的有序列表。
从根向下，找到下一个child，即如果路径是 A.B.C，找到 A，然后递归到 A 并找到 B。最后插入 C 作为 B 的 child（如果 C 不存在）。

使用binarySearch()查找插入点（或匹配元素）。

由于children的列表是排序的，所以个人搜索是O(ln(b))，其中b最大的是children。您最多需要深入 d 个级别，因此 O(d ln(b))。整个过程需要重复 n 次。

版本 2

这会占用更多内存，实际上可能不会更快。

在构建树的同时，保留一个映射 path-to-node -> 节点.

每当你遇到一个节点输入

如果你假设散列 table 像宣传的那样工作，你会得到 O(n) （或者 O(n ln(n)) 如果 children 已排序）但需要有足够的内存对于散列 table.

由于版本 2 似乎并没有那么好，我会坚持使用实施起来更简单的版本 1。

Efficient algorithm to create a tree where you know each elements path