Изменения

[[Файл:konspkonspv2.jpg‎|350px|thumb|Ослабленное красно-чёрное дерево.]]

Определим ослабленное красно-чёрное дерево как красно-чёрное дерево, корень которого может быть как чёрным, так и красным. Останется ли оно после этого Докажем, что при таком условии не будут выполняться и некоторые другие свойства красно-черным? черных деревьев. При добавлении вершины около корня могут возникнуть повороты, и корневая вершина перейдет в какое-то поддерево. Из-за этого может возникнуть ситуация, в которой подряд будут идти две красные вершины. То же самое может произойти из-за перекрашиваний возле корня. Если мы продолжим вставлять элементы подобным образом, свойства дерева перестанут выполняться, и оно перестанет быть сбалансированным. Таким образом, время выполнения некоторых операций ухудшится.

Перед тем, как перейдем к примеру, договоримся, что мы разрешим в ослабленном красно-чёрном дереве при первом добавлении вершин (обеих, правой и левой) к красному корню делать их черными (немного модифицированный алгоритм вставки). Предыдущее условие можно заменить на другое, позволяющее корню иметь красных детей. Рассмотрим пример справа. Получим такое дерево добавляя ключи в следующем порядке: <tex>10, 6, 45, 4, 8</tex>. На примере можно видеть, что после добавления вершины с ключом <tex>F0</tex> и соответствующих перекрашиваний вершина с ключом <tex>B6</tex> становится красной с красным родителем. Дальше добавим вершину <tex>G5</tex>. Так как мы добавляем ее к черной вершине, все свойства дерева сохраняются без перекрашиваний. Но добавим после этого вершину <tex>H-3</tex>. Тогда вершина с ключом <tex>D4</tex> станет красной (<tex>F0</tex> и <tex>G5</tex> {{---}} черными) и у нас образуются три красные вершины подряд. Продолжая добавлять вершины таким образом , мы можем сделать сильно разбалансированное дерево.

|statement= В красно-черном дереве с черной высотой <tex>hb</tex> количество внутренних вершин не менее <tex>2^{hb+1}-1</tex>.

По индукции докажем, что поддерево любого узла <tex>x</tex> с черной высотой <tex>hb(x)</tex> содержит не менее <tex>2^{hb(x)} - 1</tex> внутренних узлов. '''База индукции:''' Если рассмотреть высота узла <tex>x</tex> равна <tex>0,</tex> то <tex>x</tex> {{---}} это лист , <tex>hb(фиктивную вершинуx)= 0, то </tex> <tex>2^{0} - 1 = 0.</tex> '''Индукционный переход:''' Пусть наше предположение верно для нее лемма вернавысот до <tex>h'. Рассмотрим </tex> Теперь рассмотрим внутреннюю вершину <tex>x</tex>. Пусть с двумя потомками, для которой <tex>hb(x)=h'</tex>. Тогда если ее потомок <tex>p</tex> {{---}} черный, то его высота <tex>hb(p)=h'-1</tex>, а если красный, то <tex>hb(p) = h'</tex>. Таким образомНо поскольку высота потомка меньше, по предположению индукциичем высота узла <tex>x</tex>, для него выполняется индукционное предположение. В таком случае в поддеревьях содержится не менее поддереве узла <tex>2^{h'}-1x</tex> вершин, а во всём дереве, соответственно, содержится не менее чем <tex>2^{h'-1}-1 + 2^{h'-1}-1 + 1=2^{h'+1}-1</tex>. Следовательно, утверждение верно и для всего дерева.

Так как только черные узлы могут иметь красных детейПо доказанной лемме, то для количества внутренних вершин в самом длинном пути от корня до листа красных вершин будет точно не больше половины, поэтому если обычная высота дерева равна <tex>h</tex>, то черная высота дерева будет не меньше дереве <tex>h/2-1N</tex> и, по лемме, количество внутренних вершин в деревевыполняется неравенство:

Каждый элемент вставляется вместо листа, поэтому для выбора места вставки идём от корня до тех пор, пока указатель на следующего сына не станет <tex>nil</tex>(то есть этот сын {{---}} лист). Вставляем вместо него новый элемент с <tex>nil</tex>-потомками и красным цветом. Теперь проверяем балансировку. Если отец нового элемента черный, то никакое из свойств дерева не нарушено. Если же он красный, то нарушается свойство <tex>3</tex>, для исправления достаточно рассмотреть два случая:

1. Если брат этого ребёнка красный, то делаем вращение вокруг ребра между отцом и братом, тогда брат становится родителем отца. Красим его в чёрный, а отца {{- --}} в красный цвет, сохраняя таким образом черную высоту дерева. Хотя все пути по-прежнему содержат одинаковое количество чёрных узлов, сейчас <tex>x</tex> имеет чёрного брата и красного отца. Таким образом, мы можем перейти к следующему шагу.

* Оба ребёнка у брата чёрные. Красим брата в красный цвет и рассматриваем далее отца вершины. Делаем его черным, это не повлияет на количество чёрных узлов на путях, проходящих через <tex>b</tex>, но добавит один к числу чёрных узлов на путях, проходящих через <tex>x</tex>, восстанавливая тем самым влиянние удаленного чёрного узла. Таким образом, после удаления вершины черная глубина от отца этой вершины до всех листьев в этом поддереве будет одинаковой.

Объединение двух красно-чёрных деревьев <tex>T_{1}</tex> и <tex>T_{2}</tex> по элементу <tex>x</tex> выполняется, когда <tex>key[T_{1}] \leqslant x</tex> и <tex>x \leqslant key[T_{2}]</tex>, где <tex>key[T]</tex> {{---}} максимальные ключи дерева <tex>T</tex>.

При #Самое главное преимущество красно-черных деревьев в том, что при вставке выполняется не более <tex>O(1)</tex> вращений. Это важно, например, в алгоритме построения [[Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление)|динамической выпуклой оболочки]]. Ещё важно, что примерно половина вставок и удалений произойдут задаром. #Процедуру балансировки практически всегда можно выполнять параллельно с процедурами поиска, так как алгоритм поиска не зависит от атрибута цвета узлов.#Сбалансированность этих деревьев хуже, чем у АВЛ, но работа по поддержанию сбалансированности в красно-чёрных деревьях обычно эффективнее. Для балансировки красно-чёрного дерева производится минимальная работа по сравнению с АВЛ-деревьями.#Использует всего 1 бит дополнительной памяти для хранения цвета вершины. Но на самом деле в современных вычислительных системах память выделяется кратно байтам, поэтому это не является преимуществом относительно, например, АВЛ-дерева, которое хранит 2 бита. Однако есть реализации красно-чёрного дерева, которые хранят значение цвета в бите. Пример {{---}} Boost Multiindex. В этой реализации уменьшается потребление памяти красно-чёрным деревом, так как бит цвета хранится не в отдельной переменной, а в одном из указателей узла дерева. Красно-чёрные деревья являются наиболее активно используемыми на практике самобалансирующимися деревьями поиска. В частности, ассоциативные контейнеры библиотеки STL(map, set, multiset, multimap) основаны на красно-чёрных деревьях. TreeMap в Java тоже реализован на основе красно-чёрных деревьев. == Связь с 2-3 и 2-4 деревьями == === Изоморфизм деревьев === Красно-черные деревья изоморфны [[B-дерево | B-деревьям]] 4 порядка. Реализация B-деревьев трудна на практике, поэтому для них был придуман аналог, называемый симметричным бинарным B-деревом<ref>[http://rflinux.blogspot.ru/2011/10/red-black-trees.html Абстрактные типы данных {{---}} Красно-чёрные деревья (Red black trees)]</ref>. Особенностью симметричных бинарных B-деревьев является наличие горизонтальных и вертикальных связей. Вертикальные связи отделяют друг от друга разные узлы, а горизонтальные соединяют элементы, хранящиеся в одном узле B-дерева. Для различения вертикальных и горизонтальных связей вводится новый атрибут узла {{---}} цвет. Только один из элементов узла в B-дереве красится в черный цвет. Горизонтальные связи ведут из черного узла в красный узел, а вертикальные могут вести из любого узла в черный. [[Файл:Rbtree.png‎|750px|]] === Корректность сопоставления деревьев === Сопоставив таким образом цвета узлам дерева, можно проверить, что полученное дерево удовлетворяет всем свойствам красно-черного дерева.{{Утверждение|statement=У красного узла родитель не может быть красного цвета.|proof=В узле 2-4 дерева содержится не более трех элементов, один из которых обязательно красится в черный при переходе к симметричному бинарному B-дереву. Тогда оставшиеся красные элементы, если они есть, подвешиваются к черному. Из этих элементов могут идти ребра в следующий узел 2-4 дерева. В этом узле обязательно есть черная вершина, в нее и направляется ребро. Оставшиеся элементы узла, если они есть, подвешиваются к черной вершине аналогично первому узлу. Таким образом, ребро из красной вершины никогда не попадает в красную, значит у красного элемента родитель не может быть красным.}}{{Утверждение|statement=Число черных узлов на любом пути от листа до вершины одинаково.|proof=В B-дереве глубина всех листьев одинакова, следовательно, одинаково и количество внутренних узлов на каждом пути. Мы сопоставляем чёрный цвет одному элементу внутреннего узла B-дерева. Значит, количество чёрных элементов на любом пути от листа до вершины одинаково.}}{{Утверждение|statement=Корень дерева {{---}} черный.|proof=Если в корне один элемент, то он {{---}} чёрный. Если же в корне несколько элементов, то заметим, что один элемент окрашен в чёрный цвет, остальные {{---}} в красный. Горизонтальные связи, соединяющие элементы внутри одного узнала, ведут из чёрного элемента в красный, следовательно, красные элементы будут подвешены к чёрному. Он и выбирается в качестве корня симметричного бинарного B-дерева.}} === Сопоставление операций в деревьях === Все операции, совершаемые в B-дереве, сопоставляются операциям в красно-черном дереве. Для этого достаточно доказать, что изменение узла в B-дереве соответствует повороту в красно-черном дереве.{{Утверждение|statement=Изменение узла в B-дереве соответствует повороту в красно-черном дереве.|proof=В 2-4 дереве изменение узла необходимо при добавлении к нему элемента. Рассмотрим, как будет меняться структура B-дерева и, соответственно, красно-черного дерева при добавлении элемента: * Если в узле содержался один элемент, то происходит добавление второго элемента, соответствующее добавлению красного элемента в красно-черное дерево.

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

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

Сбалансированность этих деревьев хуже, чем у АВЛ, но работа по поддержанию сбалансированности в красно-чёрных деревьях обычно эффективнее. Для балансировки красно-чёрного дерева производится минимальная работа по сравнению с АВЛ-деревьями[[Файл:Rbtree2.png‎|1000px|]]

Использует всего 1 бит дополнительной памяти для хранения цвета вершины. Но на самом деле в современных вычислительных системах память выделяется кратно байтам, поэтому это не является преимуществом относительно, например, АВЛПри удалении элемента из узла B-дерева, которое хранит 2 бита. Однако есть реализации совершаются аналогичные процессы поворота и окраски вершин в красно-чёрного деревачерном дереве, которые хранят значение цвета только в бите. Пример {{---}} Boost Multiindexобратном направлении. В этой реализации уменьшается потребление памяти красно-чёрным деревом, так Так как бит цвета хранится не все операции в отдельной переменной2-4 дереве происходят за счет изменения узлов, а то они эквивалентны соответствующим операциям в одном из указателей узла деревакрасно-черном дереве.}}

Красно{{Теорема|statement=Приведенное выше сопоставление B-чёрные деревья являются наиболее активно используемыми на практике самобалансирующимися деревьями поиска. В частности, ассоциативные контейнеры библиотеки STL(map, set, multiset, multimap) основаны на деревьев и красно-чёрных деревьяхчерных деревьев является изоморфизмом.|proof=Доказательство следует непосредственно из приведенных выше утверждений.}}