Operation Cost that Varies: Our In-Order Iterator
Irregular Single-Operation Performance
In splay trees, insert and exists can take a variable amount of time, sometimes being very quick and occasionally being much slower. Rather than look at an example of code where operations vary in how expensive they are, let's look at a different example that you may have been thinking about….
In Homework 6, you implement a BST (with no tree-balancing algorithm) with an in-order iterator. Using this iterator, we can print out all of the values in the tree in order using a loop like
for (std::string key : myTree) {
std::cout << ">>> " << key << " <<<" << std::endl;
}
or this equivalent explicitly coded loop:
for (auto i = myTree.begin(); i != myTree.end(); ++i) {
std::cout << ">>> " << *i << " <<<" << std::endl;
}
But what is the complexity of this loop?
We'll look at that question by examining four trees containing the same nodes, but inserted in different orders to create different tree shapes:
- A, B, C, D, E, F, G, H, I, J, K, L, M, N, O (a stick leaning to the right, with A at the root)
- O, N, M, L, K, J, I, H, G, F, E, D, C, B, A (a stick leaning to the left, with O at the root).
- H, D, L, B, F, J, N, A, C, E, G, I, K, M, O (a well-balanced tree with H at the root).
- G, F, E, D, C, B, A, O, N, M, L, K, J, I, H (the shape is two left-leaning sticks one stacked atop the other).
Our iterator will print out the values in the tree in sorted order (A, B, C, D, E, F, G, H, I, J, K, L, M, N, O) but the debugging traces below show what goes on behind the scenes to make that happen for each of these differently shaped trees:
┌──────────────────┬──────────────────┬──────────────────┬──────────────────┐ │1: ABCDEFGHIJKLMNO│2: ONMLKJIHGFEDCBA│3: HDLBFJNACEGIKMO│4: GFEDCBAONMLKJIH│ ├──────────────────┼──────────────────┼──────────────────┼──────────────────┤ │ - push(A) │ - push(O) │ - push(H) │ - push(G) │ │ - top() [read A] │ - push(N) │ - push(D) │ - push(F) │ │ >>> A <<< │ - push(M) │ - push(B) │ - push(E) │ │ │ - push(L) │ - push(A) │ - push(D) │ │ - pop() [drop A] │ - push(K) │ - top() [read A] │ - push(C) │ │ - push(B) │ - push(J) │ >>> A <<< │ - push(B) │ │ - top() [read B] │ - push(I) │ │ - push(A) │ │ >>> B <<< │ - push(H) │ - pop() [drop A] │ - top() [read A] │ │ │ - push(G) │ - top() [read B] │ >>> A <<< │ │ - pop() [drop B] │ - push(F) │ >>> B <<< │ │ │ - push(C) │ - push(E) │ │ - pop() [drop A] │ │ - top() [read C] │ - push(D) │ - pop() [drop B] │ - top() [read B] │ │ >>> C <<< │ - push(C) │ - push(C) │ >>> B <<< │ │ │ - push(B) │ - top() [read C] │ │ │ - pop() [drop C] │ - push(A) │ >>> C <<< │ - pop() [drop B] │ │ - push(D) │ - top() [read A] │ │ - top() [read C] │ │ - top() [read D] │ >>> A <<< │ - pop() [drop C] │ >>> C <<< │ │ >>> D <<< │ │ - top() [read D] │ │ │ │ - pop() [drop A] │ >>> D <<< │ - pop() [drop C] │ │ - pop() [drop D] │ - top() [read B] │ │ - top() [read D] │ │ - push(E) │ >>> B <<< │ - pop() [drop D] │ >>> D <<< │ │ - top() [read E] │ │ - push(F) │ │ │ >>> E <<< │ - pop() [drop B] │ - push(E) │ - pop() [drop D] │ │ │ - top() [read C] │ - top() [read E] │ - top() [read E] │ │ - pop() [drop E] │ >>> C <<< │ >>> E <<< │ >>> E <<< │ │ - push(F) │ │ │ │ │ - top() [read F] │ - pop() [drop C] │ - pop() [drop E] │ - pop() [drop E] │ │ >>> F <<< │ - top() [read D] │ - top() [read F] │ - top() [read F] │ │ │ >>> D <<< │ >>> F <<< │ >>> F <<< │ │ - pop() [drop F] │ │ │ │ │ - push(G) │ - pop() [drop D] │ - pop() [drop F] │ - pop() [drop F] │ │ - top() [read G] │ - top() [read E] │ - push(G) │ - top() [read G] │ │ >>> G <<< │ >>> E <<< │ - top() [read G] │ >>> G <<< │ │ │ │ >>> G <<< │ │ │ - pop() [drop G] │ - pop() [drop E] │ │ - pop() [drop G] │ │ - push(H) │ - top() [read F] │ - pop() [drop G] │ - push(O) │ │ - top() [read H] │ >>> F <<< │ - top() [read H] │ - push(N) │ │ >>> H <<< │ │ >>> H <<< │ - push(M) │ │ │ - pop() [drop F] │ │ - push(L) │ │ - pop() [drop H] │ - top() [read G] │ - pop() [drop H] │ - push(K) │ │ - push(I) │ >>> G <<< │ - push(L) │ - push(J) │ │ - top() [read I] │ │ - push(J) │ - push(I) │ │ >>> I <<< │ - pop() [drop G] │ - push(I) │ - push(H) │ │ │ - top() [read H] │ - top() [read I] │ - top() [read H] │ │ - pop() [drop I] │ >>> H <<< │ >>> I <<< │ >>> H <<< │ │ - push(J) │ │ │ │ │ - top() [read J] │ - pop() [drop H] │ - pop() [drop I] │ - pop() [drop H] │ │ >>> J <<< │ - top() [read I] │ - top() [read J] │ - top() [read I] │ │ │ >>> I <<< │ >>> J <<< │ >>> I <<< │ │ - pop() [drop J] │ │ │ │ │ - push(K) │ - pop() [drop I] │ - pop() [drop J] │ - pop() [drop I] │ │ - top() [read K] │ - top() [read J] │ - push(K) │ - top() [read J] │ │ >>> K <<< │ >>> J <<< │ - top() [read K] │ >>> J <<< │ │ │ │ >>> K <<< │ │ │ - pop() [drop K] │ - pop() [drop J] │ │ - pop() [drop J] │ │ - push(L) │ - top() [read K] │ - pop() [drop K] │ - top() [read K] │ │ - top() [read L] │ >>> K <<< │ - top() [read L] │ >>> K <<< │ │ >>> L <<< │ │ >>> L <<< │ │ │ │ - pop() [drop K] │ │ - pop() [drop K] │ │ - pop() [drop L] │ - top() [read L] │ - pop() [drop L] │ - top() [read L] │ │ - push(M) │ >>> L <<< │ - push(N) │ >>> L <<< │ │ - top() [read M] │ │ - push(M) │ │ │ >>> M <<< │ - pop() [drop L] │ - top() [read M] │ - pop() [drop L] │ │ │ - top() [read M] │ >>> M <<< │ - top() [read M] │ │ - pop() [drop M] │ >>> M <<< │ │ >>> M <<< │ │ - push(N) │ │ - pop() [drop M] │ │ │ - top() [read N] │ - pop() [drop M] │ - top() [read N] │ - pop() [drop M] │ │ >>> N <<< │ - top() [read N] │ >>> N <<< │ - top() [read N] │ │ │ >>> N <<< │ │ >>> N <<< │ │ - pop() [drop N] │ │ - pop() [drop N] │ │ │ - push(O) │ - pop() [drop N] │ - push(O) │ - pop() [drop N] │ │ - top() [read O] │ - top() [read O] │ - top() [read O] │ - top() [read O] │ │ >>> O <<< │ >>> O <<< │ >>> O <<< │ >>> O <<< │ │ │ │ │ │ │ - pop() [drop O] │ - pop() [drop O] │ - pop() [drop O] │ - pop() [drop O] │ └──────────────────┴──────────────────┴──────────────────┴──────────────────┘
We've made an animated version of the data in the table above, but it's a bit distracting/mesmerizing/tall so you'll have to click the button below to show it:
- Animated Version (Opens in new window/tab.)
It always takes \( \Theta(n) \) time. Every node is pushed, read with top, and popped exactly once; there are exactly 15 of each. The operations may be ordered differently, but they always occur.
In Tree 2, we pushed all the nodes in the first step, and in Tree 4, we pushed about half the nodes initially and then the other half about halfway through. In both cases, we're doing \( \Theta(n) \) work in the worst case.
But much of the time we only have to do a constant amount of work. So, the best case is \( \Theta(1) \).
Overall, we can say that the time required for a single iteration of the loop is \( \mathrm{O}(n) \).
Whoa, whoa! We do \( \mathrm{O}(n) \) work for each of \( n \) iterations and overall it's \( \Theta(n) \)!!! How can that be?!!??
You saw the answers to the questions! It's clearly true!!
-
Hay! That doesn't mean I'm still not a bit confused about how.
If it were the case that every item in the tree took \( \Theta(n) \) time to process, then, yes, it wouldn't be possible.
But in this case, some items in the tree might take \( \Theta(n) \) time, but if that does happen, it won't happen often enough to be a problem.
-
The key thing is, we're shifting work around. If we make some loop iterations slower, we're making other ones faster.
(When logged in, completion status appears here.)