За счёт каких факторов достигается амортизированная константная сложность в контейнере map?

В std::map (который является сбалансированным двоичным деревом поиска, например, красно-черным деревом) большинство операций (вставка, удаление, поиск) имеют логарифмическую временную сложность $O(\log N)$, где $N$ — количество элементов в контейнере.

Амортизированная константная сложность, о которой иногда говорят в контексте ассоциативных контейнеров, чаще относится к std::unordered_map (хеш-таблице, см. ниже). В std::map такой амортизированной константной сложности для основных операций нет.

Возможно, вопрос касается амортизированной константной сложности при операциях, которые не являются основными поисковыми или модифицирующими, например, при перемещении итератора. Итераторы в std::map позволяют перемещаться по элементам в отсортированном порядке за амортизированное $O(1)$ время, поскольку структура дерева позволяет находить следующий/предыдущий элемент достаточно эффективно в среднем.

Также стоит упомянуть std::unordered_map – это хеш-таблица. В ней вставка, удаление и поиск имеют среднюю амортизированную сложность $O(1)$ при хорошей хеш-функции и отсутствии большого количества коллизий. Худший случай при большом количестве коллизий или плохой хеш-функции может достигать $O(N)$.

В контексте std::map говорить об амортизированной константной сложности для ключевых операций неверно.