相关问题：Time的二叉树O（N）的InOrder树遍历的复杂性？，但它是基于通过递归（所以在为O（log N）的空间）遍历，而迭代器允许只有O（1）空间中的消耗。

Related question: Time Complexity of InOrder Tree Traversal of Binary Tree O(N)?, however it is based on a traversal via recursion (so in O(log N) space) while iterators allow a consumption of only O(1) space.

在C ++中，通常有一个要求，即递增一个标准容器的迭代器是一个O（1）操作。对于大多数容器它是平凡的证明，然而，随着地图键，这样，似乎有点困难。

In C++, there normally is a requirement that incrementing an iterator of a standard container be a O(1) operation. With most containers it's trivially proved, however with map and such, it seems a little more difficult.

如果一个地图被实现为一个跳跃列表，那么结果将是显而易见 但是它们经常实施为红 - 黑树（或至少为二分搜索树） If a map were implemented as a skip-list, then the result would be obvious However they are often implemented as red-black trees (or at least as binary search trees)

那么，一个在序​​遍历时有瞬间里的下一个值不那么容易达到。例如，你应该要指在左子树的右下叶，然后下一个节点遍历是根，这是深度几步之遥。

So, during an in-order traversal there are moments where the "next" value is not so easily reached. For example should you be pointing at the bottom-right leaf of the left subtree, then the next node to traverse is the root, which is depth steps away.

我试图证明，该算法的复杂性（在台阶换算）的摊销的O（1），这似乎是正常的。但是我没有示威尚未下来。

I have tried "proving" that the algorithmic complexity (in terms of "steps") was amortized O(1), which seems alright. However I don't have the demonstration down yet.

下面是一个小图我跟踪用于与深度为4，数字树（在节点处）重新present的步骤从该节点到下一个的期间去数阶遍历：

Here is a small diagram I traced for a tree with a depth of 4, the numbers (in the place of the nodes) represent the number of steps to go from that node to the next one during an in-order traversal:

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

注意：最右边的叶具有为4的成本的情况下，这将是一个更大的树的子树的

的总和是28，对于15个节点的总数量：这样一个成本不到2％的节点，在平均水平，这（如果它支撑着）将是一个不错摊销成本。所以：

The sum is 28, for a total number of nodes of 15: thus a cost less than 2 per node, in average, which (if it holds up) would be a nice amortized cost. So:

在中序遍历，是递增的迭代器真的O（1）平衡（及全）二叉搜索树？ 可将结果扩大到包括非全二叉搜索树？

推荐答案

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

Yes, the amortized cost is indeed O(1) per iteration, for a any tree.

证明是基于次你访问的每个节点的数目。 叶子被访问一次。 无叶被访问最多3次：

The proof is based on the number of times you "visit" each node. Leaves are visited only once. None leaves are visited at most 3 times:

从父去节点本身的时候。 从左子树回来的时候 从右子树回来的时候

有任何节点没有更多的访问，因此，如果我们总结每个节点的访问次数，我们得到一个数字，小则 3N ，所以总结合所有节点的访问次数为 O（N），这让我们 O（1）每步摊销。

There are no more visits to any nodes, thus if we sum the number of visits of each node, we get a number that is smaller then 3n, so the total number of visits of all nodes combined is O(n), which gives us O(1) per step amortized.

（注意：因为在一个完整的树有n / 2叶，我们所得到的 2N 你遇到，我相信可以证明访问的总和越小则 2N 的任何树木，但这种优化超出范围在这里IMO）。

(Note since in a full tree there are n/2 leaves, we are getting the 2n you were encountering, I believe one can show that the sum of visits will be smaller then 2n for any tree, but this "optimization" is out of scope here IMO).

每步最坏的情况是 0（H），这是 O（LOGN）在一个平衡的树，但可能是 O（N）在某些情况下。

The worst case per step is O(h), which is O(logn) in a balanced tree, but might be O(n) in some cases.

P.S。我不知道如何红黑树的C ++实现，但如果你的树数据结构包含一个父从每个节点字段，它可以代替递归堆栈，并允许 O（1）空间消耗。 （当然，这是欺骗，因为存储 N 这样的领域是 O（N）本身）。

P.S. I have no idea how Red-Black trees are implemented in C++, but if your tree data structure contains a parent field from each node, it can replace the recursive stack and allow O(1) space consumption. (This is of course "cheating" because storing n such fields is O(n) itself).