STL RBTree 是有序迭代 O(N ln N) 吗？

Question

问题：STL红黑树(stl_tree.h)是否为有序迭代时间复杂度O(N ln N)？我在网上搜索了没找到答案。

我认为任何ADT的有序迭代的时间复杂度应该是O(N)。如果我错了，请告诉我。

我从这段代码中查看了 STL RB 树 (https://www.sgi.com/tech/stl/stl_tree.h)

迭代器的++运算符似乎不是O(1)而是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;
  }
}

如果我没记错的话，上面的代码是 O(ln N) 复杂度而不是 O(1)。

那么下面的 ++ 运算符也将具有 O(ln N) 复杂度。

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

这意味着即使是对 STL RBTree 的简单迭代也将是 O(N ln N) 而不是 O(N)。

我错了还是做出了一些奇怪的假设？

顺便说一句，我想到了基于堆栈的迭代器堆叠路径。我认为它可以实现 O(1) 的时间复杂度，但它会花费 O(ln N) space 复杂度，就像基于递归的中序遍历一样。

但是，堆栈方法的问题是当不同线程更改树结构并通过旋转弄乱路径堆栈时。（但大多数时候，当我们考虑使用这种类型的 ADT 进行多线程编程时，我们通常会锁定整棵树，所以路径混乱并不是一个大问题......对吧？）即使是这种类型的 O (ln N) 方法无论如何都不是线程安全的。

提前致谢。

Answer 1

_M_increment 在最坏的情况下是 O(lg n)，是的，但是分摊了 O(1)。您可以访问维基百科以了解有关摊销分析的更多信息。

我在这里给出一个直观的解释，而不是证明：

考虑树中的每条边。对于每条边，在整个遍历过程中会使用两次，一次进入，一次离开。

边数为O(n)。在_M_increment中，我们最关心的部分是循环。幸运的是，这些循环消耗边访问，这意味着对于整个遍历，循环体将总共执行 O(n) 次。所以每个增量的摊销复杂度是 O(1)。

STL RBTree 是有序迭代 O(N ln N) 吗？

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

c++

algorithm

stl

red-black-tree