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

Question

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

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

Answer 1

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

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

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

Answer 2

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

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

Answer 3

Деревья 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 в зависимости от соотношения.

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

Answer 4

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

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

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

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

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

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

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

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

Александр Степанов (создатель 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 может быть самым быстрым выбором.

Answer 5

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

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

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

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

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

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

Answer 6

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