Изменения

=== Изоморфизм деревьев === Красно-черные деревья эквивалентны изоморфны [[B-дерево | B-деревьям ]] 4 порядка. Реализация B-деревьев трудна на практике, поэтому для них был придуман аналог, называемый симметричным бинарным B-деревом<ref>[http://rflinux.blogspot.ru/2011/10/red-black-trees.html Абстрактные типы данных {{---}} Красно-чёрные деревья (Red black trees)]</ref>. Особенностью симметричных бинарных B-деревьев является наличие горизонтальных и вертикальных связей. Вертикальные связи отделяют друг от друга разные узлы, а горизонтальные соединяют узлыэлементы, являющиеся одним узлом хранящиеся в одном узле B-дерева. Для различения вертикальных и горизонтальных связей вводится новый атрибут узла {{---}} цвет. Только один из элементов узла в B-дереве красится в черный цвет. Горизонтальные связи ведут из черного узла в красный узел, а вертикальные могут вести из любого узла в черный.

В 2-4 дереве изменение узла необходимо при добавлении к нему элемента. Рассмотрим, как будет меняться структура B-дерева и, соответственно, красно-черного дерева при добавлении элемента: * Если в узле содержался один элемент, то происходит добавление второго элемента, соответствующее добавлению красного элемента в красно-черное дерево. * Если в узле содержалось два элемента, то происходит добавление третьего элемента, что соответствует повороту и перекрашиванию вершин в красно-черном дереве. * Если в узле содержалось три элемента, то один из элементов узла становится самостоятельным узлом, к которому подвешиваются узел из пары элементов и узел из одного элемента. Эта операция соответствует перекрашиванию яруса красно-черного дерева из красного в черный цвет.

Если в узле содержался 1 элемент, то происходит добавление второго элемента, соответствующее добавлению красного элемента в красно-черное дерево[[Файл:Rbtree2.png‎|1000px|]]

Если При удалении элемента из узла B-дерева совершаются аналогичные процессы поворота и окраски вершин в красно-черном дереве, только в обратном направлении. Так как все операции в узле содержалось 2 элемента-4 дереве происходят за счет изменения узлов, то происходит добавление третьего элемента, что соответствует повороту и перекрашиванию вершин они эквивалентны соответствующим операциям в красно-черном дереве.}}

Если в узле содержалось 3 элемента, то один из элементов узла становится самостоятельным узлом, к которому подвешиваются узел из пары элементов {{Теорема|statement=Приведенное выше сопоставление B-деревьев и узел из одного элемента. Эта операция соответствует перекрашиванию яруса красно-черного дерева черных деревьев является изоморфизмом.|proof=Доказательство следует непосредственно из красного в черный цветприведенных выше утверждений.