Почему у map::erase ( range version ) линейная сложность?

Ведь там внутри бинарное дерево поиска ... насколько я помню все реализации хранят в каждом узле ссылку на родителя — т.е. удаление всех элементов в диапазоне (first,last] сводится к нахождению общего предка ( что есть логарифмическая сложность).

Вот что говорит документация —

Complexity:
For the last version (erase(first,last)), linear in the distance between first and last.

http://www.cplusplus.com/reference/map/map/erase/