如何以比 O(n^2) 更快的速度从节点列表更新树？

Question

给定：N 节点列表。每个节点由 2 个数字组成：nodeID 和 parentID。 parentID 可能为 null（如果它是根节点）。

是否有一种算法可以从这个节点列表中重新创建一棵树，其时间复杂度优于 O(N^2)？

每个节点可以有 0 个或多个子节点。

---

O(N^2) 复杂度算法的简短描述：

  find a root Node, put it to a Queue
  while Queue is not empty
      parentNode = Queue.pop()
      loop through nodes
          if currentNode.parentId = parentNode.id
              parentNode.addChild(currentNode)
              queue.push(currentNode)
              nodes.remove(currentNode)

看起来这个算法有 O(N^2) 时间复杂度（系数很小，可能是 0.25）。但我在这里的复杂度计算可能是错误的。

Answer 1

由于您已经有了树的外部结构（队列），因此我假设您不介意使用一点额外的内存来更快地完成工作。

使用哈希表分两个概念步骤完成此操作：

1. 首先创建一个将节点 ID 与其实际节点相关联的哈希表。
2. 然后根据哈希表中父节点的 ID 查找节点的父节点，并将子节点添加到该父节点中。

更编程化：

for each node
    add node to hash table indexed by node's parent
for each node
    if parent is null set node as the root
    otherwise look up in the hash table the parent from the parent ID of the node
    add the node as a child of the found parent

这种技术的唯一潜在问题是，直到最后你不一定会得到一棵有效的树。 （也就是说，根节点在最后一个链接之前可能没有子节点。）根据您对树所做的操作，这可能是一个问题。

如果这是一个问题，您最终可以对不存在该问题的数据结构（只是没有附加数据的普通树）执行相同的操作，然后镜像该结构。

总而言之，平均起来应该是O(N)。

Answer 2

对于每个节点初始化一个子节点列表，并为每个节点更新父节点的子节点列表。复杂度 O(n)。

For node in NodeList:
    node.childList = []

For node in NodeList:
    if node.parent is not NULL:
        node.parent.childList.append(&node)

如果父链接不易获得，则创建哈希映射。 FWIW，对于每次插入或查找，哈希映射的最坏情况复杂度是 O(logn)。所以最终的复杂度就变成了O(nlogn)。

Answer 3

我不知道您的输入是什么，但我们假设它是某种无序列表。

然后，您可以通过将它们放入允许通过其 nodeID 查找的数据结构中来创建树结构。例如，数组就可以做到这一点。然后你就有了一棵只在父母的方向上链接的树。假设节点 ID 是唯一的，则可以在线性时间内从无序列表转换为该数组。

为了使树也沿着子节点的方向链接，您可以使用数据结构（例如列表）准备节点来保存子节点，然后执行第二遍将每个节点添加到其父节点的子节点列表中。这在线性时间内也是可能的。