13

相关问题：InOrder Tree Traversal of Binary Tree O(N) 的时间复杂度？，但是它基于递归遍历（因此在 O(log N) 空间中），而迭代器只允许消耗 O(1) 空间。

在 C++ 中，通常要求递增标准容器的迭代器是 O(1) 操作。对于大多数容器，它被简单地证明了，但是对于map这样的，它似乎有点困难。

  • 如果 amap被实现为跳过列表，那么结果将是显而易见的
  • 然而，它们通常被实现为红黑树（或至少作为二叉搜索树）

因此，在有序遍历期间，有时不容易达到“下一个”值。例如，如果您指向左子树的右下叶，那么下一个要遍历的节点就是根，它离我们depth几步之遥。

我已经尝试“证明”算法复杂性（就“步骤”而言）是摊销O(1)，这似乎没问题。但是我还没有演示。

这是我为深度为 4 的树跟踪的一个小图，数字（代替节点）表示在有序遍历期间从该节点到下一个节点的步数：

       3
   2       2
 1   1   1   1
1 2 1 3 1 2 1 4

注意：最右边的叶子的成本为 4，以防这将是一棵较大树的子树。

总和为 28，节点总数为 15：因此平均每个节点的成本低于 2，这（如果它坚持的话）将是一个不错的摊销成本。所以：

  • 在中序遍历期间，对于平衡（和完整）二叉搜索树，增加迭代器真的是 O(1) 吗？
  • 可以将结果扩展到涵盖非完整二叉搜索树吗？
4

1 回答 1

12

O(1)是的，对于任何树，摊销成本确实是每次迭代。

证明基于您“访问”每个节点的次数。
叶子只被访问一次。无叶子最多访问 3 次：

  1. 从父节点到节点本身时。
  2. 从左子树回来时
  3. 从右子树回来时

不再有对任何节点的访问，因此如果我们将每个节点的访问次数相加，我们会得到一个小于 的数字3n，因此所有节点的总访问次数为O(n)，这使我们O(1)每步摊销。

（注意，由于在一棵完整的树中有 n/2 个叶子，我们得到了2n你遇到的，我相信可以证明访问的总和将小于2n任何树，但是这种“优化”在这里超出了范围国际海事组织）。

每一步最坏的情况是O(h)，它在平衡树中，但在某些情况下O(logn)可能是。O(n)

PS 我不知道红黑树是如何在 C++ 中实现的，但是如果你的树数据结构包含parent来自每个节点的字段，它可以替换递归堆栈并允许O(1)空间消耗。（这当然是“作弊”，因为存储n这些字段O(n)本身就是）。

于 2012-10-14T13:12:51.050 回答