577
правок
Изменения
Нет описания правки
Для экономии памяти фиктивные листья можно сделать одним общим фиктивным листом.
== Свойства ==
Красно-чёрным называется бинарное поисковое дерево, у которого каждому узлу сопоставлен дополнительный атрибут {{---}} цвет и для которого выполняются следующие свойства (англ. ''red-black properties''):
# Каждый узел промаркирован красным или чёрным цветом
# Корень и конечные узлы(листья) дерева {{---}} чёрные
# У красного узла родительский узел {{---}} чёрный
# Все простые пути из любого узла x до листьев содержат одинаковое количество чёрных узлов
# Чёрный узел может иметь чёрного родителя
В книге Кормена "Алгоритмы: построение и анализ" дается немного иное определение красно-черного дерева, а именно: '''красно-чёрное дерево''' {{---}} это двоичное дерево поиска, вершины которого разделены на красные и черные. Таким образом, каждая вершина хранит один дополнительный бит {{---}} её цвет. При этом должны выполняться определенные требования, которые гарантируют, что глубины любых двух листьев отличаются не более, чем в два раза, поэтому дерево можно назвать сбалансированным (англ. ''balanced'').
По Кормену двоичное дерево поиска является красно-чёрным, если обладает следующими свойствами:
# Каждая вершина {{---}} либо красная, либо черная
# Каждый лист {{---}} черный
# Если вершина красная, оба ее ребенка черные
# Все пути, идущие от корня к листьям, содержат одинаковое количество черных вершин
Из свойств красно-черного дерева понятно, почему "глубины любых двух листьев отличаются не более, чем в два раза", поэтому определения можно считать эквивалентными.
Определим ослабленное красно-чёрное дерево как красно-чёрное дерево, корень которого может быть как чёрным, так и красным. Тогда корень всегда может быть изменен с красного на чёрный с сохранением всех свойств. Но вот при изменении цвета корня с чёрного на красный дерево может перестать удовлетворять свойствам <tex>3</tex> и <tex>4</tex>. Тогда даже если мы перекрасим все вершины так, чтобы у красного узла не было красных потомков, свойство <tex>4</tex> все равно может не выполняться.
== Высота красно-черного дерева ==
{{Определение
|definition=Будем называть '''чёрной высотой''' (англ. ''black-height'') вершины <tex>x</tex> число чёрных вершин на пути из <tex>x</tex> в лист, не учитывая саму вершину <tex>x</tex>.
}}
{{Лемма
Если рассмотреть лист (фиктивную вершину), то для нее лемма верна. Рассмотрим внутреннюю вершину <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>.
}}
{{Теорема
|statement=Красно-чёрное дерево с <tex>N</tex> ключами имеет высоту <tex>h = O(\log N)</tex>.
|proof=
Если обычная высота дерева равна <tex>h</tex>, то черная высота дерева будет не меньше <tex>h/2-1</tex> и, по лемме, количество внутренних вершин в дереве
Красно-чёрные деревья являются наиболее активно используемыми на практике самобалансирующимися деревьями поиска. В частности, ассоциативные контейнеры библиотеки STL(map, set, multiset, multimap) основаны на красно-чёрных деревьях.
==См. также==
* [[Дерево поиска, наивная реализация|Дерево поиска, наивная реализация]]
* [[АВЛ-дерево|АВЛ-дерево]]
* [[2-3 дерево|2-3 дерево]]
==Источники информации==
* [http://rain.ifmo.ru/cat/view.php/vis/trees/red-black-2002 Визуализатор]
* [http://ru.wikipedia.org/wiki/%CA%F0%E0%F1%ED%EE-%F7%B8%F0%ED%EE%E5_%E4%E5%F0%E5%E2%EE Википедия {{---}} Красно-чёрное дерево]
* [http://algolist.manual.ru/ds/rbtree.php AlgoList {{---}} Красно-черные деревья]
* [http://nord.org.ua/static/course/algo_2009/lecture10.pdf Курс kiev-clrs {{---}} Лекция 10. Красно-чёрные деревья]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Деревья поиска]]
