更快地计算左偏树的节点

Question

我要遍历一棵树，我需要计算其中的节点总数。因此，以更简单的方式，我可以遍历树并执行一些 count++ 来计算树的节点。但这对于拥有数百万个节点的树来说是非常耗时的。这将花费 O(N) 时间，其中 N 是节点数。我想降低这种方法的时间复杂度。我怎样才能做到这一点？供大家参考，我分享一下我的想法的伪代码。

struct Node{
Node* left;
Node* right;
}
int traverse(Node* node){
  if (node == null) return 0; //base case
  count++;
  count += traverse (node->left) //recursive call
  count += traverse (node->right) //recursive call
  return count;
}

另请告诉我上述方法是否有效？如果不是那么为什么？请建议任何更快的方法。

Answer 1

没有其他方法可以计算节点，即您必须访问它们。但是你的递归函数中有一个未声明的变量 count 。相反，每次调用都从头开始，因为您只会 return 该节点以下的节点数（和 1 来说明节点本身），而不管其他节点该节点的环境：

int traverse(Node* node){
  if (node == null) return 0; //base case
  return 1 + traverse(node->left) + traverse(node->right);
}

但是如果您要在树的不同状态下重复计算节点数，那么您可能会受益于存储每个子树中的节点数，并保留该信息随着树的每个突变而更新。所以你会在每个节点实例中存储它是根的子树中的节点数（包括它自己）。

struct Node{
    Node* left;
    Node* right;
    int count;
}

对于每个插入操作，您都会增加该节点所有祖先的 count 成员，并给节点本身计数 1。这表示 O(logn) 时间复杂度不会增加插入操作可能已经具有时间复杂度。

对于每个删除操作，您都会递减该已删除节点的所有祖先的 count 成员。这表示 O(logn) 时间复杂度，它不会增加删除操作可能已经具有的时间复杂度。

当需要获取整棵树的计数时，只需读出根节点的count值即可。这只是一个 O(1) 操作。

更快地计算左偏树的节点

Computing the nodes of a left skewed tree faster

data-structures

tree

time-complexity

recursive-datastructures