Почему std:: map реализован в виде красно-черного дерева?

Это действительно зависит от использования. Дерево AVL обычно имеет больше вращений перебалансировки. Поэтому, если ваше приложение не имеет слишком много операций вставки и удаления, но сильно весит при поиске, то дерево AVL, вероятно, является хорошим выбором.

std::map использует красно-черное дерево, поскольку оно получает разумный компромисс между скоростью вставки/удаления узла и поиском.

деревья AVL имеют максимальную высоту 1.44 logn, в то время как деревья RB имеют максимум 2logn. Вставка элемента в AVL может означать перебалансировку в одной точке дерева. Перебалансировка завершает вставку. После вставки нового листа, обновление предков этого листа должно быть сделано до корня, или до точки, где два поддерева имеют одинаковую глубину. Вероятность обновления K узлов равна 1/3^k. перебалансировка равна O (1). Удаление элемента может означать более одного перебалансировка (до половины глубины дерева).

RB-деревья-это B-деревья порядка 4, представленные в виде бинарных деревьев поиска. 4-узел в B-дереве приводит к двум уровням в эквивалентном BST. В худшем случае все узлы дерева являются 2-узлами, причем только одна цепочка из 3-узлов спускается к листу. Этот лист будет находиться на расстоянии 2logn от корня.

спускаясь от корня до точки вставки, нужно изменить 4-узлы на 2-узлы, чтобы убедиться, что любая вставка не насытит лист. Возвращаясь из вставки, все эти узлы должны быть проанализированы, чтобы убедиться, что они правильно представляют 4-узлы. Это также можно сделать, спустившись в дерево. Глобальная стоимость будет такой же. Здесь нет бесплатного обеда! Удаление элемента из дерева происходит в том же порядке.

все эти деревья требуют, чтобы узлы несли информацию о высоте, весе, цвете и т. д. Только раскидистые деревья свободны от такой дополнительной информации. Но большинство людей боятся раскидистых деревьев, из-за разветвленности их структуры!

наконец, деревья также могут нести информацию о весе в узлах, что позволяет балансировать вес. Могут применяться различные схемы. Следует перебалансировать, когда поддерево содержит более чем в 3 раза больше элементов другого поддерева. Перебалансировка снова выполняется либо через один, либо двойной поворот. Это означает, что в худшем случае 2.4 дошла. Можно уйти с 2 раза вместо 3, гораздо лучшее соотношение, но это может означать, оставив немного менее 1% поддеревьев разбалансированы здесь и там. Сложно!

какой тип дерева является лучшим? Авл точно. Они являются самыми простыми в коде и имеют худшую высоту, ближайшую к logn. Для дерева из 1000000 элементов AVL будет иметь максимальную высоту 29, RB 40 и вес сбалансированный 36 или 50 в зависимости от соотношения.

есть много других переменных: произвольности, соотношение добавление, удаление, поиск и т. д.

предыдущие ответы касаются только альтернатив дерева, а красный черный, вероятно, остается только по историческим причинам.

почему не хэш-таблицу?

в дереве тип требует только частичного упорядочения (

проектирование хорошим хэш-таблица требует глубокого знания контекста, в котором она будет использоваться. Следует ли использовать открытую адресацию или связанную цепочку? Какие уровни нагрузки он должен принять перед изменением размера? Должен ли он использовать дорогой хэш, который избегает столкновений, или тот, который является грубым и быстрым?

(C++11 добавил хэш-таблицы с unordered_map. Вы можете видеть из документация для настройки многих из этих параметров требуется настройка политик.)

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

как насчет других деревьев?

предложение красного черного дерева быстрый поиск и самобалансировка, в отличие от BSTs. Другой пользователь отметил ее преимущества по сравнению с self-балансировка Авл деревьев.

Александр Степанов (создатель STL) сказал, что он будет использовать дерево B* вместо красно-черного дерева, если он напишет std::map опять же, что более удобно для современных кэшей памяти.

одним из самых больших изменений с тех пор стал рост схрон. Промахи кэша очень дороги, поэтому локальность ссылки намного больше важный сейчас. Узловые структуры данных, которые имеют низкую локальность ссылка, имеет гораздо меньше смысла. Если бы я проектировал STL сегодня, я будет иметь другой набор контейнеров. Например, в памяти B*-дерева, является гораздо лучшим выбором, чем красно-черное дерево для реализации ассоциативный контейнер. - Александр Степанов

вы можете подробнее здесь

красное черное дерево или B* всегда лучше?

в других случаях Алекс заявил, что std::vector почти всегда является лучшим контейнером списка по аналогичным причинам. Это редко имеет смысл использовать std::list или std::deque даже для тех ситуаций, которые мы учили в школе (например, удаление элемента из середины список.) std::vector настолько быстро, что он бьет эти структуры для всего, кроме большого n.

применяя то же самое рассуждение, если у вас есть только небольшое количество элементов (сотни?) с помощью std::vector и линейный поиск может быть более эффективным, чем реализация дерева std::map. В зависимости от частоты вставки, сортируется std::vector в сочетании с std::binary_search может быть самый быстрый выбор.

Это просто выбор ваш осуществлению - они могут быть реализованы как любое сбалансированное дерево. Различные варианты все сопоставимы с незначительными различиями. Поэтому любой так же хорош, как и любой.

обновление 2017-06-14: webbertiger редактировать свой ответ после того, как я прокомментировал. Я должен отметить, что его ответ теперь намного лучше для моих глаз. Но я сохранил свой ответ только в качестве дополнительной информации...

из-за того, что я думаю, что первый ответ неверен (поправочка: не как больше), а третий имеет неправильное утверждение. Я чувствую, что должен был прояснить ситуацию...

2 самых популярных дерева-AVL и Red Black (RB). Главное отличие заключается в следующем использование:

• AVL: лучше, если коэффициент консультации (чтения) больше, чем манипуляции (модификации). Память отпечатка ноги немного меньше, чем RB (из-за бита, необходимого для окраски).
• RB: лучше в общих случаях, когда существует баланс между консультацией (читай) и манипуляцией (модификацией) или более модификацией по сравнению с консультацией. Немного больший объем памяти из-за хранения красно-черного флага.

главная разница заключается в окраске. У вас есть меньше действий повторного баланса в дереве RB, чем AVL, потому что окраска позволяет иногда пропускать или сокращать действия повторного баланса, которые имеют относительную стоимость hi. Из-за окраски дерево RB также имеет более высокий уровень узлов, потому что оно может принимать красные узлы между черными (имея возможности ~2x больше уровней), что делает поиск (чтение) немного менее эффективным... но поскольку это константа (2x), она остается в O(log n).

Если вы рассмотрим хит производительности для модификации дерева (сигнификативный) VS хит производительности консультации дерева (почти незначительный), становится естественным предпочесть RB над AVL для общего случая.