树标记算法的复杂性

Question

我有一个泛型加权树(无向图，没有圈，连通)，有n个节点和n-1边连接一个节点到另一个节点。

我的算法做了以下工作：

做

• 计算实际叶子(1级节点)
• 从树中删除所有的叶子及其边缘，用其连接的叶子成本的最大值给每个家长贴上标签(例如，如果一个内部节点连接到两片叶子上，成本为5,6，然后我们用6标记出叶子后的内部节点)。

直到树的大小为<= 2

返回具有最大成本标记的节点。

我是否可以说，计算叶子的复杂性是O(n)，而O(n)是用叶子消除每一条边，所以我有O(n)+O(n) = O(n)。

Answer 1

您可以通过一个简单的列表、队列或堆栈(处理顺序不重要)实现的集合在O(n)中很容易地做到这一点。

把所有的叶子都放在布景里。

在循环中，从集合中删除叶子，从图中删除它及其边缘。通过更新父级的最大值来处理标签。如果父现在是一片叶子，那么将它添加到集合中，然后继续进行。

当集合为空时，就完成了，节点标签也是正确的。

最初构造集合是O(n)。每个顶点都被放置在集合上，移除，并且它的标签处理了一次。这都是固定的时间。因此，对于n个节点，它是O(n)时间。所以我们有O(n) + O(n) = O(n)。

Answer 2

因为你的树是一棵艺术品。它也可以是一个链接列表，在这种情况下，您将在每次迭代中删除一个节点，并且需要(n-2)迭代的O(n)来找到叶子。

所以你的算法实际上是O(N^2)

下面是一个更好的算法，在O(N)中对任何树都这样做

deleteLeaf(Node k) {

 for each child do
     value = deleteLeaf(child)
     if(value>max)
       max = value
     delete(child)
 return max 
}
deleteLeaf(root) or deleteLeaf(root.child)