Является ли 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 (пер 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 пер Н) вместо O (N).

Я ошибался или сделал какое-то странное предположение?

---

Кстати, я думал о итераторе на основе стека, укладывая путь. Я думаю, что он может достичь сложности времени O (1), но это будет стоить сложности O (ln N), так же как и рекурсивное обходное обходное обслуживание.

Однако проблема с подходом к стеклу связана с тем, что разные потоки изменяют структуру дерева и перепутали стек стека с помощью поворотов. (Но чаще всего, когда мы думаем о многопоточном программировании с этим типом ADT, мы обычно будем блокировать все дерево, так что путаница не такая уж большая проблема ... не так ли?) Даже этот тип O (ln N) в любом случае не является потокобезопасным.

Заранее спасибо.

Answer 1

_M_increment is O (lg n) в худшем случае, да, но амортизирован O (1). Вы можете посетить Википедию, чтобы узнать больше об Амортизированном анализе.

Я давая интуитивное объяснить здесь, а не доказательство:

Рассмотрим каждое ребро в дереве. Для каждого ребра он будет использоваться дважды через весь обход, один для ввода и один для ухода.

Число ребер - O (n). В _M_increment части, которые нам больше всего интересны, - это петли. К счастью, эти петли потребляют края, что означает, что для всего обхода тело цикла будет выполнено O (n) раз в общей сложности. поэтому амортизированная сложность для каждого приращения равна O (1).