577
правок
Изменения
→Преимущества красно-чёрных деревьев
== Преимущества красно-чёрных деревьев ==
#Самое главное преимущество красно-черных деревьев в том, что при вставке выполняется не более <tex>O(1)</tex> вращений. Это важно, например, в алгоритме построения [[Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление)|динамической выпуклой оболочки]]. Ещё важно, что примерно половина вставок и удалений произойдут задаром, например, при вставке красного узла мы иногда вообще ничего не делаем. Разница высот в два раза в поддереве {{---}} это не так важно по сравнению с этим.#Алгоритм вставки и удаления может быть написан в один проход сверху вниз, вместо алгоритма, который использует рекурсивный проход вниз, родительские указатели или явный стек для обеспечения возможности пройти назад вверх, чтобы провести перебалансировку. Например, в АВЛ-деревьях требуется сначала пройти вниз, произвести операцию, а потом сделать балансирующий проход обратно вверх
#Процедуру балансировки практически всегда можно выполнять параллельно с процедурами поиска, так как алгоритм поиска не зависит от атрибута цвета узлов.
#Сбалансированность этих деревьев хуже, чем у АВЛ, но работа по поддержанию сбалансированности в красно-чёрных деревьях обычно эффективнее. Для балансировки красно-чёрного дерева производится минимальная работа по сравнению с АВЛ-деревьями.
#Использует всего 1 бит дополнительной памяти для хранения цвета вершины. Но на самом деле в современных вычислительных системах память выделяется кратно байтам, поэтому это не является преимуществом относительно, например, АВЛ-дерева, которое хранит 2 бита. Однако есть реализации красно-чёрного дерева, которые хранят значение цвета в бите. Пример {{---}} Boost Multiindex. В этой реализации уменьшается потребление памяти красно-чёрным деревом, так как бит цвета хранится не в отдельной переменной, а в одном из указателей узла дерева.
Красно-чёрные деревья являются наиболее активно используемыми на практике самобалансирующимися деревьями поиска. В частности, ассоциативные контейнеры библиотеки STL(map, set, multiset, multimap) основаны на красно-чёрных деревьях. Они имеют различные применения TreeMap в ядре Linux (для организации очередей запросов, в ext3, например)Java тоже реализован на основе красно-чёрных деревьев.
==См. также==
