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

195

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

Существует несколько сбалансированных бинарных поисковых деревьев (BST). Каковы были дизайнерские компромиссы при выборе красно-черного дерева?

c++ dictionary data-structures stl binary-search-tree Денис Городецкий
источник
26
Хотя все реализации, которые я видел, используют RB-дерево, обратите внимание, что оно все еще зависит от реализации.
Томас
3
@Томас. Это зависит от реализации, так почему же все реализации используют RB-деревья?
Денис Городецкий
1
Мне бы очень хотелось узнать, задумывался ли кто-нибудь из разработчиков STL об использовании списка пропуска.
Матье М.
2
Карта и набор в C ++ - это упорядоченная карта и упорядоченный набор. Они не реализованы с использованием хеш-функций. Каждый запрос будет принимать O(logn)и нет O(1), но значения всегда будут отсортированы. Начиная с C ++ 11 (я думаю), есть unordered_mapи unordered_set, которые реализованы с использованием хеш-функций, и, хотя они не отсортированы, большинство запросов и операций возможно O(1)(в среднем)
SomethingSomething
@ Томас, это правда, но не так интересно на практике. Стандарт дает гарантии сложности с учетом конкретного алгоритма или набора алгоритмов.
Джастин Майнерс

Ответы:

126

Вероятно, два наиболее распространенных алгоритма самобалансирующегося дерева - это красно-черные деревья и деревья AVL . Чтобы сбалансировать дерево после вставки / обновления, оба алгоритма используют понятие поворотов, где узлы дерева вращаются для выполнения повторной балансировки.

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

Красно-черные деревья используются в большинстве библиотек коллекций, включая предложения Java и Microsoft .NET Framework.

Крис Тейлор
источник
54
Вы говорите так, будто красно-черные деревья могут изменять дерево за O (1), что не соответствует действительности. модификациями дерева являются O (log n) как для красно-черных, так и для деревьев AVL. это делает его спорным, является ли балансирующая часть модификации дерева O (1) или O (log n), потому что основная операция уже O (log n). даже после небольшой дополнительной работы, выполняемой деревьями AVL, получается более плотно сбалансированное дерево, что приводит к немного более быстрому поиску. таким образом, это совершенно приемлемый компромисс и не делает деревья AVL хуже красно-черных деревьев.
некромант
35
Чтобы увидеть разницу, нужно посмотреть не только на сложность, но и на фактическое время выполнения. У деревьев AVL общее время выполнения меньше, когда операций поиска намного больше, чем операций вставки / удаления. Деревья RB имеют меньшее общее время выполнения, когда есть еще много вставок / удалений. Точная пропорция, в которой происходит разрыв, зависит, конечно, от многих деталей реализации, аппаратного обеспечения и точного использования, но поскольку авторам библиотек приходится поддерживать широкий спектр шаблонов использования, им приходится делать обоснованные предположения. AVL также немного сложнее в реализации, поэтому вы можете захотеть использовать проверенную выгоду.
Стив Джессоп
6
Дерево RB не является "реализацией по умолчанию". Каждый реализатор выбирает реализацию. Насколько нам известно, все они выбрали деревья RB, поэтому, вероятно, это либо для производительности, либо для простоты внедрения / обслуживания. Как я уже сказал, точка останова для производительности может не означать, что они думают, что вставок / удалений больше, чем поисков, просто что соотношение между ними выше уровня, на котором, по их мнению, RB, вероятно, превосходит AVL.
Стив Джессоп
9
@Denis: к сожалению, единственный способ получить числа - составить список std::mapреализаций, отследить разработчиков и спросить их, какие критерии они использовали для принятия решения, так что это остается спекуляцией.
Стив Джессоп
4
Из всего этого не хватает затрат на хранение дополнительной информации, необходимой для принятия решений о балансе. Красно-черным деревьям требуется 1 бит для представления цвета. Деревьям AVL требуется как минимум 2 бита (для представления -1, 0 или 1).
SJHowe
47

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

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

webbertiger
источник
1
Вы уверены, что??? Лично я считаю, что красно-черное дерево является или более сложным, и никогда не бывает проще. Единственное, есть в Rd-Black tree, ребалансировка происходит реже, чем в AVL.
Эрик
1
@Eric Теоретически, и дерево R / B, и дерево AVL имеют сложность O (log n)) для вставки и удаления. Но одна большая часть эксплуатационных затрат - это ротация, которая отличается между этими двумя деревьями. Пожалуйста, обратитесь к Discus.fogcreek.com/joelonsoftware/… Цитата: «балансировка дерева AVL может потребовать O (log n) поворотов, в то время как красное черное дерево потребует не более двух поворотов, чтобы привести его в равновесие (хотя это может потребоваться исследуйте O (log n) узлов, чтобы решить, где вращения необходимы). " Отредактировал мои комментарии соответственно.
webbertiger
27

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

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

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

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

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

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

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

user847376
источник
2
Хороший ответ. Но если AVL являются лучшими, почему стандартная библиотека реализует std :: map как дерево RB?
Денис Городецкий
14
Я не согласен с тем, что деревья AVL, несомненно, являются лучшими. Несмотря на то, что они имеют низкую высоту, им требуется (в целом) больше работы для перебалансировки, чем для красных / черных деревьев (O (log n), работа по перебалансировке по сравнению с O (1) амортизированной перебалансировкой). Густые деревья могут быть намного лучше, и ваше утверждение о том, что люди их боятся, необоснованно. Не существует единой универсальной «лучшей» схемы балансировки деревьев.
templatetypedef
Почти идеальный ответ. Почему вы сказали, что AVL лучший. Это просто неправильно, и поэтому в большинстве общих реализаций используется красно-черное дерево. Вы должны иметь довольно высокий коэффициент манипулирования чтением, чтобы выбрать AVL. Кроме того, AVL занимает немного меньше памяти, чем RB.
Эрик
Я согласен, что AVL имеет тенденцию быть лучше в большинстве случаев, потому что обычно деревья ищутся чаще, чем они вставляются. Почему дерево RB так широко считается лучшим, когда оно имеет небольшое преимущество в случае большей части записи и, что более важно, небольшой недостаток в случае большей части чтения? Действительно ли верили, что вы вставите больше, чем найдете?
doug65536
25

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

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

Тип требует, чтобы <оператор (сравнение) использовался как ключ в дереве. Однако для хеш-таблиц требуется, чтобы для каждого типа ключа была определена hashфункция. Соблюдение минимальных требований к типам очень важно для общего программирования, поэтому вы можете использовать его с самыми разными типами и алгоритмами.

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

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

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

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

Красные Черные деревья предлагают быстрый поиск и являются самобалансирующимися, в отличие от BST. Другой пользователь указал на свои преимущества перед самобалансирующимся деревом AVL.

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

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

Должны ли карты всегда использовать деревья?

Другой возможной реализацией карт будет сортированный вектор (сортировка вставкой) и бинарный поиск. Это будет хорошо работать для контейнеров, которые не часто изменяются, но часто запрашиваются. Я часто делаю это в C, как qsortи bsearchвстроены.

Мне даже нужно использовать карту?

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

Конечно, выбор читаемого контейнера обычно важнее производительности.

Джастин Майнерс
источник
3

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

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

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

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

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

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

Эрик Оуэлл
источник
2

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

некромант
источник