Изменения

Красно-черные деревья эквивалентны B-деревьям 4 порядка. Реализация B-деревьев трудна на практике, поэтому для них был придуман аналог, называемый симметричным бинарным B-деревом. Особенностью симметричных бинарных B-деревьев является наличие горизонтальных и вертикальных связей. Вертикальные связи отделяют друг от друга разные узлы, а горизонтальные соединяют узлы, являющиеся одним узлом B-дерева. Для различения вертикальных и горизонтальных связей вводится новый атрибут узла {{---}} цвет. Только один из элементов узла в B-дереве имеет красится в черный цвет. Горизонтальные связи ведут из черного узла в красный узел, а вертикальные могут вести из любого узла в черный.

Во-первых, у {{Утверждение|statement=У красного узла родитель не может быть красного цвета, так как в .|proof=В узле 2-4 дереве в одном узле дерева содержится не более трех элементов и , один из элементов которых обязательно красится в черныйпри переходе к симметричному бинарному B-дереву. Значит можно подвесить Тогда оставшиеся красные элементы так, чтобы их родитель был чернымесли они есть, подвешиваются к черному. ВоИз этих элементов могут идти ребра в следующий узел 2-вторых4 дерева. В этом узле обязательно есть черная вершина, в нее и направляется ребро. Оставшиеся элементы узла, если они есть, подвешиваются к черной вершине аналогично первому узлу. Таким образом, число ребро из красной вершины никогда не попадает в красную, значит у красного элемента родитель не может быть красным.}}{{Утверждение|statement=Число черных узлов на любом пути от листа до вершины одинаково, так как в .|proof=В B-дереве это свойство выполнено, а из глубина всех листьев одинакова. Из каждого узла B-дерева выбирается только один элемент красится для окраски в черный цвет, и путь в симметричным бинарным B-дереве состоит только из элементов, лежащих на одном пути в B-дереве. Наконец, корень Значит количество черных элементов на любом пути от листа до вершины одинаково.}}{{Утверждение|statement=Корень дерева {{---}} черный, так как вершина .|proof=Вершина B-дерева состоит из узла, в котором один элемент {{---}} черный. Он и выбирается в качестве корня симметричного бинарного B-дерева.}}Все операции, совершаемые в B-дереве, сопоставляются операциям в красно-черном дереве. Для этого достаточно доказать, что изменение узла в B-дереве соответствует повороту в красно-черном дереве.{{Утверждение|statement=Изменение узла в B-дереве соответствует повороту в красно-черном дереве.|proof=В 2-4 дереве изменение узла необходимо при добавлении к нему элемента. Если в узле содержался 1 элемент, то происходит добавление второго элемента, соответствующее добавлению красного элемента в красно-черное дерево. Если в узле содержалось 2 элемента, то происходит добавление третьего элемента, что соответствует повороту и перекрашиванию вершин в красно-черном дереве. Если в узле содержалось 3 элемента, то один из элементов узла становится самостоятельным узлом, к которому подвешиваются узел из пары элементов и узел из одного элемента. Эта операция соответствует перекрашиванию яруса красно-черного дерева из красного в черный цвет.}}[[Файл:Rbtree2.png‎|1000px|]] Так как все операции в 2-4 дереве происходят за счет изменения узлов, то они эквивалентны соответствующим операциям в красно-черном дереве.