Изменения
Нет описания правки
Красно-чёрным называется бинарное поисковое дерево, у которого каждому узлу сопоставлен дополнительный аттрибут – цвет и для которого выполняются следующие свойства:
# Каждый узел промаркирован красным или чёрным цветом
# Корень и конечные узлы (листья) дерева – чёрные
# У красного узла родительский узел – чёрный
# Все простые пути из любого узла x до листьев содержат одинаковое количество чёрных узлов
|statement= В красно-черном дереве с черной высотой <tex>hb</tex> количество внутренних вершин не менее <tex>2^{hb+1}-1</tex>.
|proof=
Если рассмотреть лист (фиктивную вершину), то для нее лемма верна. Рассмотрим внутреннюю вершину <tex>x</tex>. Пусть <tex>hb(x)=h'</tex>. Тогда если ее потомок <tex>p</tex> - черный, то высота <tex>hb(p)=h'-1</tex>, а если – красный, то <tex>hb(p)=h'</tex>. Таким образом, по предположению индукции, в поддеревьях содержится не менее <tex>2^{h'}-1</tex> вершин, а во всём дереве, соответственно, не менее <tex>2^{h'}-1 + 2^{h'}-1 + 1=2^{h'+1}-1</tex>.
}}
[[Файл:Merge2.jpg|400px|]]
Далее проверяем: не нарушили ли мы свойства красно-чёрного дерева. Так как присутствует нарушение (у красной вершины есть красный сын), то перекрасим вершины и сделаем поворот:
[[Файл:Merge3.jpg|400px|]]
Одно из основных преимуществ красно-чёрных деревьев заключается в том, что оно использует всего 1 бит дополнительной памяти для хранения цвета вершины. Также при вставке выполняется не более <tex>O(1)</tex> вращений.
Красно-чёрные деревья являются наиболее активно используемыми на практике самобалансирующимися деревьями поиска. В частности, ассоциативные контейнеры библиотеки STL (map, set, multiset, multimap) основаны на красно-чёрных деревьях.
==Ссылки==
