Почему std::map реализован как красно-черное дерево?
Существует несколько сбалансированных двоичных деревьев поиска (BST). Какие компромиссы были при выборе красно-черного дерева?
Почему std :: map реализован в виде красно-черного дерева?
Ответы (6)
Вероятно, двумя наиболее распространенными алгоритмами самобалансирующегося дерева являются красно-черные деревья и деревья AVL. Чтобы сбалансировать дерево после вставки / обновления, оба алгоритма используют понятие вращения, при котором узлы дерева поворачиваются для выполнения повторной балансировки.
В то время как в обоих алгоритмах операции вставки / удаления выполняются O (log n), в случае перебалансировки красного и черного дерева вращение выполняется как O (1) операция, в то время как с AVL это O (log n), что делает Красно-Черное дерево более эффективным в этом аспекте этапа перебалансировки и является одной из возможных причин его более широкого использования.
Красно-черные деревья используются в большинстве библиотек коллекций, включая предложения от Java и Microsoft .NET Framework.
person
Chris Taylor
schedule
13.03.2011
вы говорите так, будто красно-черные деревья могут изменять дерево за O (1) раз, что неверно. модификации дерева равны O (log n) как для красно-черного, так и для AVL-деревьев. это делает спорным, является ли балансирующая часть модификации дерева O (1) или O (log n), потому что основная операция уже O (log n). даже после всей небольшой дополнительной работы, которую выполняют деревья AVL, получается более строго сбалансированное дерево, что приводит к немного более быстрому поиску. так что это вполне допустимый компромисс, который не делает деревья AVL хуже красно-черных деревьев.
- person necromancer; 13.03.2011
@agks mehx, я имею в виду ротационную часть алгоритма. Я обновлю это, чтобы было понятнее.
- person Chris Taylor; 13.03.2011
Чтобы увидеть разницу, вы должны посмотреть не только на сложность, но и на фактическую среду выполнения - деревья AVL обычно имеют меньшее общее время выполнения, когда выполняется гораздо больше операций поиска, чем вставок / удалений. Деревья RB имеют меньшее общее время выполнения, когда имеется намного больше вставок / удалений. Точная пропорция, в которой происходит сбой, конечно, зависит от многих деталей реализации, оборудования и точного использования, но, поскольку авторы библиотеки должны поддерживать широкий спектр шаблонов использования, они должны делать обоснованное предположение. AVL также немного сложнее реализовать, поэтому вам может понадобиться доказанное преимущество для его использования.
- person Steve Jessop; 13.03.2011
@Steve Итак, почему было принято решение сделать дерево RB имплементацией по умолчанию? Вы имеете в виду, что вставок / удалений больше, чем поисков в целом?
- person Denis Gorodetskiy; 13.03.2011
Дерево RB не является реализацией по умолчанию. Каждый разработчик выбирает реализацию. Насколько нам известно, все они выбрали деревья RB, так что предположительно это либо для производительности, либо для простоты реализации / обслуживания. Как я уже сказал, точка останова для производительности может не означать, что они думают, что вставок / удалений больше, чем поисков, просто соотношение между ними выше уровня, на котором, по их мнению, RB, вероятно, превосходит AVL.
- person Steve Jessop; 13.03.2011
@Стив. Я хочу отметить ваш комментарий как ответ, если он будет поддержан цифрами
- person Denis Gorodetskiy; 14.03.2011
@Denis: к сожалению, единственный способ получить числа - это составить список
std::map реализаций, выследить разработчиков и спросить их, по каким критериям они приняли решение, так что это остается предположением.
- person Steve Jessop; 14.03.2011
@ChrisTaylor Разве деревья AVL и RB-деревья не принимают O (1) для перебалансировки амортизированной пост-вставки?
- person dhruvbird; 16.06.2013
@dhruvbird - Здесь не так много места, чтобы вдаваться в подробности. Возможно, следующая ссылка поможет pages.cs .wisc.edu / ~ ealexand / cs367 / NOTES / AVL-Trees /
- person Chris Taylor; 16.06.2013
@ChrisTaylor Я думаю, что эта ссылка может вводить в заблуждение. В среднем реструктуризация деревьев AVL также стоит O (1). См. en.wikipedia.org/wiki/AVL_tree#Comparison_to_other_structures Интуиция такова, что RB- Деревья - это, по сути, 2-3-деревья, и, попросту говоря, изменения высоты AVL-дерева не распространяются до тех пор, пока не будут изменены узлы Ω (n).
- person dhruvbird; 16.06.2013
Хотя я был бы склонен написать код для проверки всего этого, потребуется некоторое время, чтобы написать код для обоих и доказать их правильность. Я нашел следующий практический анализ, который выглядит достаточно разумно nathanbelue. blogspot.com/2013/01/
- person Chris Taylor; 16.06.2013
@ChrisTaylor После того, как положение узла определено, деревьям AVL требуется до двух оборотов, чтобы зафиксировать высоту. Это связано с тем, что вставка может увеличить высоту поддерева не более чем на 1. Это увеличение может быть [1] в меньшем дереве (вращение не требуется) или [2] в большом дереве (возможно, без увеличения высоты поста). -rotation) или [3], если оба дерева имеют одинаковую высоту, то вставка может эффективно УВЕЛИЧИТЬ общую высоту дерева на 1. Это увеличение компенсируется поворотом на узле более высокого уровня. то есть случай [3] приводит к случаю [1] или [2], которые фиксируются одним поворотом.
- person dhruvbird; 17.06.2013
@ChrisTaylor Этот блог - отличный ресурс о практических характеристиках, которых можно было ожидать - спасибо! :)
- person dhruvbird; 17.06.2013
@ChrisTaylor Для вставки в дерево AVL выполняется максимум 2 поворота, а не log n поворотов. см. проблему 3d здесь ocw.mit.edu/courses/electrical-engineering-and-computer-science/
- person Nikunj Banka; 24.04.2014
@NikunjBanka, это максимальное количество оборотов, однако с точки зрения затрат это операция O (log (n)). Чтобы быть более точным, это амортизированная стоимость, в то время как RB-деревья имеют постоянную амортизированную стоимость, т.е. O (1) для вращения вставки штифта.
- person Chris Taylor; 27.04.2014
@ChrisTaylor Это очень крутое наблюдение! Действительно, в красно-черном дереве можно выполнить максимум 3 операции, в то время как в дереве AVL можно выполнить максимум O (logN) операций, когда мы изменим коэффициенты баланса узлов logN в дереве.
- person Nikunj Banka; 27.04.2014
Пожалуйста, прочтите комментарий и не могли бы вы исправить свой ответ ?. Вы совершенно неправы, и ваш ответ просто приводит людей к ложным утверждениям. В большинстве реализаций используется черно-красное дерево, потому что в общем случае, когда у вас больше манипуляций, чем консультации (чтение), красно-черное дерево немного быстрее, потому что требуется реже балансировать. Но когда консультация (чтение) происходит чаще, чем манипуляции, АВЛ протекает быстрее, потому что она лучше сбалансирована. Обе перебалансировки выполняются в одном и том же порядке для обоих, который равен не O (1), а O (log n).
- person Eric Ouellet; 30.05.2017
@EricOuellet - Я думаю, что вы неправильно прочитали, я не говорю, что ребалансировка - O (1), это шаг вращения, который равен O (1) для R-B Tree (требуется не более двойного левого или правого вращения),
- person Chris Taylor; 31.05.2017
Любое вращение всегда выполняется за O (1) в любом действии по ребалансировке дерева, об этом нет смысла упоминать, это ничего не приносит в обсуждение. Любая перебалансировка требует рекурсии между O (1) и O (log (n)), чтобы гарантировать, что правила дерева действительны. Вы можете прочитать отличный пример: cs.auckland.ac.nz/software /AlgAnim/red_black_op.html, чтобы понять, о чем я говорю. Как и в дереве AVL, вам иногда приходится возвращаться к вершине и переупорядочивать ветви, чтобы правила RB оставались в силе. Разница в окраске, перебалансировка происходит примерно в 2 раза меньше, чем в AVL.
- person Eric Ouellet; 31.05.2017
Во всем этом отсутствует стоимость на узел для хранения вспомогательной информации, необходимой для принятия решений по балансу. Красно-черным деревьям требуется 1 бит для представления цвета. Деревьям AVL требуется как минимум 2 бита (для представления -1, 0 или 1).
- person SJHowe; 12.09.2017
@EricOuellet: Неверно, что повторная балансировка будет происходить в 2 раза меньше, чем в дереве AVL. Для дерева RB вставки стоят максимум 2 оборота и максимум 3 * (log (n) / 2) перекрашивания. Вставки дерева AVL могут стоить журнала (n) оборотов вплоть до корня. Для дерева RB удаление стоит максимум 3 ротации и до log (n) перекрашиваний,. Удаление дерева AVL - это то же самое, что и Вставка, как и стоимость. Повороты в деревьях RB равны O (1), потому что они ограничены из-за перекрашивания log (n), тогда как повороты в деревьях AVL равны O (log (n)), поэтому перекрашивание не происходит.
- person SJHowe; 29.07.2020
Это действительно зависит от использования. Дерево AVL обычно имеет больше вращений для ребалансировки. Так что, если ваше приложение не имеет слишком большого количества операций вставки и удаления, но сильно нагружает поиск, то дерево AVL, вероятно, будет хорошим выбором.
std::map использует красно-черное дерево, поскольку оно обеспечивает разумный компромисс между скоростью вставки / удаления узла и поиском.
person
webbertiger
schedule
26.05.2012
Вы уверены, что??? Я лично считаю, что красно-черное дерево либо сложнее, либо проще. Единственное, в дереве Rd-Black ребалансировка происходит реже, чем в AVL.
- person Eric Ouellet; 30.05.2017
@Eric Теоретически и R / B-дерево, и AVL-дерево имеют сложность O (log n)) для вставки и удаления. Но одна большая часть стоимости операции - это вращение, которое у этих двух деревьев различается. См. Discussion.fogcreek.com/joelonsoftware/ Цитата : балансировка дерева AVL может потребовать O (log n) вращений, в то время как красно-черное дерево потребует не более двух вращений, чтобы привести его в равновесие (хотя ему, возможно, придется проверить O (log n) узлов, чтобы решить, где необходимы вращения ). Соответственно отредактировал свои комментарии.
- person webbertiger; 14.06.2017
Большое спасибо за то, что обратил мое внимание на максимальное вращение 2 для вставки в дерево RB. Ты прав. Я этого не понимал. Как вы сказали, перекрашивание происходит в Log (n), но это вращение стоит намного меньше. Думаю, ваш ответ отличный, не помню, какой был предыдущий ;-). Спасибо!!!
- person Eric Ouellet; 31.07.2020
Деревья AVL имеют максимальную высоту 1,44 логна, в то время как деревья RB имеют максимальную высоту 2логна. Вставка элемента в AVL может означать перебалансировку в одной точке дерева. Перебалансировка завершает вставку. После вставки нового листа обновление предков этого листа должно выполняться до корня или до точки, в которой два поддерева имеют одинаковую глубину. Вероятность обновления k узлов составляет 1/3 ^ k. Ребалансировка - O (1). Удаление элемента может потребовать более одной перебалансировки (до половины глубины дерева).
RB-деревья - это B-деревья 4-го порядка, представленные как деревья двоичного поиска. Четыре узла в B-дереве приводят к двум уровням эквивалентного BST. В худшем случае все узлы дерева являются 2-узлами, и только одна цепочка из 3-узлов вниз до листа. Этот лист будет на расстоянии 2логн от корня.
Спускаясь от корня к точке вставки, нужно преобразовать 4 узла в 2 узла, чтобы убедиться, что любая вставка не приведет к насыщению листа. Вернувшись после вставки, все эти узлы необходимо проанализировать, чтобы убедиться, что они правильно представляют 4-узлы. Это также можно сделать, спустившись по дереву. Глобальная стоимость будет такой же. Бесплатных обедов нет! Удаление элемента из дерева происходит в том же порядке.
Все эти деревья требуют, чтобы узлы несли информацию о росте, весе, цвете и т. Д. Только деревья Splay не содержат такой дополнительной информации. Но большинство людей боятся Splay-деревьев из-за неуклюжести их структуры!
Наконец, деревья могут также нести информацию о весе в узлах, что позволяет балансировать вес. Могут применяться различные схемы. Следует перебалансировать, когда поддерево содержит более чем в 3 раза больше элементов, чем другое поддерево. Повторная балансировка снова выполняется посредством одинарного или двойного вращения. Это означает наихудший случай 2,4логн. Можно обойтись 2 раза вместо 3, это гораздо лучшее соотношение, но это может означать, что здесь и там будет разбалансировано чуть меньше 1% поддеревьев. Сложный!
Какой тип дерева лучше? AVL точно. Их проще всего кодировать, а их худшая высота ближе всего к входу в систему. Для дерева из 1000000 элементов AVL будет иметь максимальную высоту 29, RB 40 и сбалансированный вес 36 или 50 в зависимости от соотношения.
Есть много других переменных: случайность, соотношение добавлений, удалений, поисков и т. Д.
person
user847376
schedule
16.07.2011
Хороший ответ. Но если AVL являются лучшими, почему стандартная библиотека реализует std :: map как дерево RB?
- person Denis Gorodetskiy; 07.10.2011
Я не согласен с тем, что деревья AVL, несомненно, лучшие. Несмотря на то, что они имеют небольшую высоту, они требуют (в целом) больше работы для восстановления баланса, чем красные / черные деревья (O (log n) работы по ребалансировке против O (1) амортизированной работы по ребалансировке). Скользящие деревья могли бы быть намного лучше, и ваше утверждение о том, что люди их боятся, необоснованно. Не существует универсальной лучшей схемы балансировки деревьев.
- person templatetypedef; 04.01.2013
Почти идеальный ответ. Почему вы сказали, что AVL - лучший. Это просто неправильно, и поэтому в большинстве общих реализаций используется красно-черное дерево. Чтобы выбрать AVL, вам нужно иметь более высокое соотношение чтения по сравнению с манипуляциями. Кроме того, у AVL немного меньше памяти, чем у RB.
- person Eric Ouellet; 30.05.2017
Я согласен с тем, что в большинстве случаев AVL лучше, потому что обычно деревья ищут чаще, чем вставляют. Почему дерево RB так широко считается лучшим, если оно имеет небольшое преимущество в случае, когда в основном используется запись, и, что более важно, имеет небольшой недостаток в случае чтения в основном? Неужели вы думаете, что вы вставите больше, чем найдете?
- person doug65536; 16.11.2019
Предыдущие ответы касались только альтернатив дерева, а красный черный, вероятно, остался только по историческим причинам.
Почему не хеш-таблица?
Тип требует только использования оператора < (сравнения) в качестве ключа в дереве. Однако хеш-таблицы требуют, чтобы для каждого типа ключа была определена hash функция. Сведение к минимуму требований к типу очень важно для универсального программирования, поэтому вы можете использовать его с широким спектром типов и алгоритмов.
Создание хорошей хеш-таблицы требует глубокого знания контекста, в котором она будет использоваться. Следует ли использовать открытую адресацию или связанную цепочку? Какие уровни нагрузки он должен принять перед изменением размера? Должен ли он использовать дорогой хэш, избегающий коллизий, или грубый и быстрый?
Поскольку STL не может предвидеть, какой вариант лучше всего подходит для вашего приложения, значение по умолчанию должно быть более гибким. Деревья «просто работают» и хорошо масштабируются.
(В C ++ 11 были добавлены хеш-таблицы с unordered_map. Вы можете видеть из документации для настройки многих из этих параметров требуется настройка политик.)
А как насчет других деревьев?
Красно-черные деревья предлагают быстрый поиск и самобалансируются, в отличие от BST. Другой пользователь указал на его преимущества перед самобалансирующимся деревом AVL.
Александр Степанов (создатель STL) сказал, что он будет использовать B * Tree вместо красно-черного дерева, если он снова напишет std::map, потому что это более дружелюбно для современных кешей памяти.
С тех пор одним из самых больших изменений стал рост кешей. Промахи кеша обходятся очень дорого, поэтому теперь гораздо важнее местоположение ссылки. Структуры данных на основе узлов, которые имеют низкую локальность ссылок, имеют гораздо меньший смысл. Если бы я проектировал STL сегодня, у меня был бы другой набор контейнеров. Например, B * -дерево в памяти - гораздо лучший выбор, чем красно-черное дерево для реализации ассоциативного контейнера. - Александр Степанов
Должны ли карты всегда использовать деревья?
Другая возможная реализация карт - это сортированный вектор (сортировка вставкой) и двоичный поиск. Это будет хорошо работать для контейнеров, которые не часто модифицируются, но часто запрашиваются. Я часто делаю это в C, поскольку qsort и bsearch встроены.
Мне вообще нужно использовать карту?
Соображения о кешировании означают, что редко имеет смысл использовать std::list или std::deque вместо std:vector даже в тех ситуациях, которым нас учили в школе (например, удаление элемента из середины списка). Применяя те же рассуждения, использование цикла for для линейного поиска по списку часто более эффективно и чище, чем построение карты для нескольких поисков.
Конечно, выбор читаемого контейнера обычно важнее производительности.
person
Justin Meiners
schedule
22.12.2017
Обновление 2017-06-14: webbertiger редактирует свой ответ после того, как я прокомментировал. Я должен отметить, что его ответ теперь намного лучше для моих глаз. Но я сохранил свой ответ как дополнительную информацию ...
Из-за того, что я думаю, что первый ответ неверен (исправление: больше не оба), а третий имеет неправильное утверждение. Я чувствую, что мне нужно кое-что прояснить ...
Два самых популярных дерева - это AVL и Red Black (RB). Основное отличие заключается в использовании:
- АВЛ: Лучше, если соотношение консультации (чтения) больше, чем манипуляции (модификации). Отпечаток памяти немного меньше RB (из-за бит, необходимого для раскраски).
- РБ: Лучше в общих случаях, когда есть баланс между консультацией (читать) и манипуляцией (модификацией) или большим количеством изменений вместо консультации. Немного больший объем памяти из-за хранения красно-черного флага.
Основное отличие заключается в расцветке. У вас меньше действий по перебалансировке в дереве RB, чем у AVL, потому что окраска позволяет вам иногда пропускать или сокращать действия по перебалансировке, которые имеют относительную высокую стоимость. Из-за раскраски дерево RB также имеет более высокий уровень узлов, потому что оно может принимать красные узлы между черными (имея возможности ~ в 2 раза больше уровней), что делает поиск (чтение) немного менее эффективным ... но потому что это constant (2x), он остается в O (log n).
Если вы рассматриваете снижение производительности для модификации дерева (значимое) VS снижение производительности при просмотре дерева (почти незначительное), становится естественным предпочесть RB над AVL для общего случая.
person
Eric Ouellet
schedule
30.05.2017
Это просто выбор вашей реализации - они могут быть реализованы как любое сбалансированное дерево. Различные варианты сопоставимы с небольшими различиями. Следовательно, любой ничем не хуже любого другого.
person
necromancer
schedule
13.03.2011
O(logn), а неO(1), но значения всегда будут отсортированы. Начиная с C ++ 11 (я думаю), естьunordered_mapиunordered_set, которые реализованы с использованием хэш-функций, и хотя они не отсортированы, большинство запросов и операций возможно вO(1)(в среднем) - person SomethingSomething schedule 15.03.2017std::mapитераторы, указывающие на другие элементы, не становятся недействительными. Это делает очень трудным, если не полностью невозможным, хранение более одного элемента на динамически выделяемый узел, при этом выполняя обычные гарантии временной сложности. (Запросы и обновленияstd::mapдолжны занимать в худшем случае логарифмическое время.) Итак, на практике реализацииstd::mapдолжны быть своего рода самобалансирующимися двоичными деревьями. - person pyon schedule 04.08.2020