Is STL RBTree inorder iteration O(N ln N)?

Question

Question: Is STL Red-Black tree (stl_tree.h) in-order iteration time complexity O(N ln N)? I searched the net and couldn't find the answer.

---

I thought any ADT's in-order iteration's time complexity should be O(N). If I am wrong, please let me know.

I reviewed the STL RB tree from this code (https://www.sgi.com/tech/stl/stl_tree.h)

It seems ++ operator of the iterator is not O(1) but O(ln N).

void _M_increment()
{
  if (_M_node->_M_right != 0) {
    _M_node = _M_node->_M_right;
    while (_M_node->_M_left != 0)
      _M_node = _M_node->_M_left;
  }
  else {
    _Base_ptr __y = _M_node->_M_parent;
    while (_M_node == __y->_M_right) {
      _M_node = __y;
      __y = __y->_M_parent;
    }
    if (_M_node->_M_right != __y)
      _M_node = __y;
  }
}

If I am not mistaken, above code is O(ln N) complexity not O(1).

Then the following ++ operator will have O(ln N) complexity as well.

_Self& operator++() { _M_increment(); return *this; }
_Self operator++(int) {
  _Self __tmp = *this;
  _M_increment();
  return __tmp;
}

This means even the simple iteration over a STL RBTree will be O(N ln N) instead of O(N).

Am I wrong or made some weird assumption?

---

By the way, I thought about stack based iterator stacking up the path. I think it can achieve O(1) time complexity but it will cost O(ln N) space complexity, just like recursion-based in-order traversal would cost.

However, the problem with stack approach is when different thread changes the tree structure and messed up the path stack by rotations. (But most of times, when we are thinking about multi-threaded programming with this type of ADT, we will usually lock the whole tree, so path messing up is not such a big concern... right?) Even this type of O(ln N) method is not thread-safe anyway.

Thanks in advance.

Answer 1

_M_increment is O(lg n) in worst case, yes, but amortized O(1). You may visit Wikipedia to learn more about Amortized Analysis.

I'm giving a intuitive explain here, not a proof:

Consider every edge in the tree. For each edge, it'll be used twice through the whole traversal, one for entering and one for leaving.

The number of edges is O(n). In _M_increment, the parts we care most are loops. Luckily, these loops consume edge visits, which means, for the whole traversal, the loop body will be executed O(n) times in total. so the amortized complexity for each increment is O(1).