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.
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
mapwere 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.
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.
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
Note: the right-most leaf has a cost of 4 in case this would be a sub-tree of a larger tree.
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:
- During in-order traversal, is incrementing the iterator really O(1) for a balanced (and full) binary search tree ?
- May the result be extended to cover non-full binary search trees ?