为了在二叉搜索树中遍历复杂度（使用迭代器）？

Question

相关问题：二叉树O（N）的有序树遍历的时间复杂性？，然而，它基于通过递归的遍历（因此在O（logn）空间中），而迭代器只允许消耗O（1）空间。

在C语言中，通常要求递增标准容器的迭代器是O（1）操作。对于大多数容器来说，这是微不足道的证明，但是对于map等等，这似乎有点困难。

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

因此，在顺序遍历过程中，有时“下一个”值不容易达到。例如，如果您指向左子树的右下叶，则下一个要遍历的节点是根，它距离depth步远。

我试着“证明”算法的复杂性（以“步数”的形式）是分摊到O（1）的，这似乎是正确的。然而，我还没有完成演示。

下面是一个小图，我追踪了一个深度为4的树，数字（在节点的地方）表示在有序遍历期间从该节点到下一个节点的步数：

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

注意：如果这是一棵较大的树的子树，最右边的叶子的代价是4。

对于15个节点的总数来说，总数是28个：因此平均每个节点的成本不到2个，这将是一个不错的摊销成本（如果它成立的话）。因此：

• 在按顺序遍历期间，递增迭代器对于平衡（和完全）二叉查找树来说真的是O（1）吗？
• 可以将结果扩展到覆盖非全二叉搜索树吗？

Answer 1

是的，对于任意树，每个迭代的摊余成本确实是O（1）。

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

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

对任何节点的访问都没有了，因此，如果我们将每个节点的访问次数相加，我们得到一个比3n小的数，因此所有节点的总访问次数加起来是O（n），这使得我们每一步摊销O（1）。

（注意，因为在一棵完整的树中有n/2片叶子，我们得到了您遇到的2n，我相信可以证明，对于任何树，访问量的总和都会小于2n，但这种“优化”在这里不适用）。

每个步骤的最坏情况是O（h），在平衡树中是O（logn），但在某些情况下可能是O（n）。

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