Как карта STRING (целочисленная или что-то еще) хранится внутри? Как они упорядочены / сбалансированы?

Question

Я знаю, что контейнер Map в STL является внутри себя красно-черным деревом, которое является самобалансирующимся деревом.

В Map самый низкий элемент находится в верхней части дерева.Таким образом, для целочисленной карты «что-нибудь» самое низкое целое будет сверху и так далее.Это всегда уравновешивает себя.Вот почему мы получаем log n сложности при поиске целого числа и связанного с ним значения.

Но в случае отображения строки в «что-нибудь», как она уравновешивает и упорядочивает себя, если делает?Какая строка будет в верхней части дерева?Соответствует ли оно значениям ASCII или что-то в этом роде?

Это может быть неубедительно, но мне нужно знать это, поскольку я должен убедиться, что я придерживаюсь сложности log n в моем коде.

Answer 1

В Map самый низкий элемент находится на вершине дерева.

Нет, наименьший элемент находится в крайнем левом узле, тот, к которому вы переходите, следуя по левому дочернему указателю, пока он не станет нулевым. В случае строк наименьший элемент - это тот, который всегда сравнивал «меньше, чем» все остальные строки, которые вы вставили в карту. Сравнение по умолчанию лексикографическое.

Балансировка продолжается , как обычно , с помощью нескольких обменов указателей. Путь от корня до любого листа гарантированно будет иметь длину Θ (lg n), несмотря ни на что.

(Это предполагает исходную реализацию STL map, которая все еще распространена, хотя соответствующая библиотека C ++ может использовать другую структуру.)