Databases
StackOverflow2013
Postsdbo
POIn-order traversal complexity in a binary search tree (using iterators)?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POIn-order traversal complexity in a binary search tree (using iterators)?
    primarykey
    data
    text
    <p>Related question: <a href="https://stackoverflow.com/questions/9658700/time-complexity-of-inorder-tree-traversal-of-binary-tree-on">Time Complexity of InOrder Tree Traversal of Binary Tree O(N)?</a>, 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.</p> <p>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 <code>map</code> and such, it seems a little more difficult.</p> <ul> <li>If a <code>map</code> were implemented as a skip-list, then the result would be obvious</li> <li>However they are often implemented as red-black trees (or at least as binary search trees)</li> </ul> <p>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 <code>depth</code> steps away.</p> <p>I have tried "proving" that the algorithmic complexity (in terms of "steps") was <em>amortized</em> O(1), which seems alright. However I don't have the demonstration down yet.</p> <p>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:</p> <pre><code> 3 2 2 1 1 1 1 1 2 1 3 1 2 1 4 </code></pre> <p><em>Note: the right-most leaf has a cost of 4 in case this would be a sub-tree of a larger tree.</em></p> <p>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:</p> <ul> <li>During in-order traversal, is incrementing the iterator really O(1) for a balanced (and full) binary search tree ?</li> <li>May the result be extended to cover non-full binary search trees ?</li> </ul>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USCommunity
    1. USMatthieu M.
    plurals
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POIn-order traversal complexity in a binary search tree (using iterators)?
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POIn-order traversal complexity in a binary search tree (using iterators)?
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POIn-order traversal complexity in a binary search tree (using iterators)?
      1. USHeisenbug
      1. VTFavorite
    1. CONot sure I am following, the "next node" of the second leaf from left - why is it 4? the next node after it is its grandparent when doing in-order traversal (so I'd expect only 2), same applies later on to other 4's. Is it a mistake or I am misunderstanding the diagram? :\
      singulars
      1. POIn-order traversal complexity in a binary search tree (using iterators)?
      1. USamit
    2. CODo you mean `O(1)` memory overall or amortized time to increment the iterator? in-order traversal cannot be `O(1)` time overall.
      singulars
      1. POIn-order traversal complexity in a binary search tree (using iterators)?
      1. USIVlad
    3. CO@IVlad: I meant O(1) for incrementing, obviously! The question would be rather silly otherwise, let me correct that ;)
      singulars
      1. POIn-order traversal complexity in a binary search tree (using iterators)?
      1. USMatthieu M.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload