Изменения

Перед тем, как перейдем к примеру, договоримся, что мы разрешим в ослабленном красно-чёрном дереве при первом добавлении вершин (обеих, правой и левой) к красному корню делать их черными (немного модифицированный алгоритм вставки). Предыдущее условие можно заменить на другое, позволяющее корю корню иметь красных детей.

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

То, что только черная вершина может иметь красных детей, совместно с <tex>4</tex>-тым ым свойством говорит о том, что корень дерева должен быть черным, а значит определения можно считать эквивалентными.

|definition=Будем называть '''чёрной высотой''' (англ. ''black-height'') вершины <tex>x</tex> число чёрных вершин на пути из <tex>x</tex> в лист, не учитывая саму вершину <tex>x</tex>.

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

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

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

<tex>\log(N+1) \geqslant \dfrac{h/}{2}</tex>

Каждый элемент вставляется вместо листа, поэтому для выбора места вставки идём от корня до тех пор, пока указатель на следующего сына не станет <tex>nil</tex> (то есть этот сын {{---}} лист). Вставляем вместо него новый элемент с <tex>nil</tex>-нулевыми потомками и красным цветом. Теперь проверяем балансировку. Если отец нового элемента черный, то никакое из свойств дерева не нарушено. Если же он красный, то нарушается свойство <tex>3</tex>, для исправления достаточно рассмотреть два случая:# "Дядя" этого узла тоже красный. Тогда, чтобы сохранить свойства <tex>3</tex> и <tex>4</tex>, просто перекрашиваем "отца" и "дядю" в чёрный цвет, а "деда" {{---}} в красный. В таком случае черная высота в этом поддереве одинакова для всех листьев и у всех красных вершин "отцы" черные. Проверяем, не нарушена ли балансировка. Если в результате этих перекрашиваний мы дойдём до корня, то в нём в любом случае ставим чёрный цвет, чтобы дерево удовлетворяло свойству <tex>2</tex>. [[Файл:Untitled-1.png|200px]]# "Дядя" чёрный. Если выполнить только перекрашивание, то может нарушиться постоянство чёрной высоты дерева по всем ветвям. Поэтому выполняем поворот. Если добавляемый узел был правым потомком, то необходимо сначала выполнить левое вращение, которое сделает его левым потомком. Таким образом, свойство <tex>3</tex> и постоянство черной высоты сохраняются.

1. "Дядя" этого узла тоже красный. Тогда, чтобы сохранить свойства <tex>3</tex> и <tex>4</tex>, просто перекрашиваем "отца" и "дядю" в чёрный цвет, а "деда" {{-[[Файл:Untitled--}} в красный. В таком случае черная высота в этом поддереве одинакова для всех листьев и у всех красных вершин "отцы" черные. Проверяем, не нарушена ли балансировка. Если в результате этих перекрашиваний мы дойдём до корня, то в нём в любом случае ставим чёрный цвет, чтобы дерево удовлетворяло свойству <tex>2</tex>. png|250px|]]

[[Файл'''Псевдокод:Untitled''' '''func''' insert(key) Node t = Node(key, red, ''nil'', ''nil'') <font color=green>// конструктор, в который передаем ключ, цвет, левого и правого ребенка </font> '''if''' дерево пустое root = t t.parent = ''nil'' '''else''' Node p = root Node q = ''nil'' '''while''' p != ''nil'' <font color=green>// спускаемся вниз, пока не дойдем до подходящего листа </font> q = p '''if''' p.key < t.key p = p.right '''else''' p = p.left t.parent = q <font color=green>// добавляем новый элемент красного цвета </font> '''if''' q.key < t.key q.right = t '''else''' q.left = t fixInsertion(t) <font color=green>// проверяем, не нарушены ли свойства красно-1.png|200px]]черного дерева </font>

2. '''func''' fixInsertion(t: '''Node''') '''if''' t {{---}} корень t = black '''return''' <font color=green>// далее все предки упоминаются относительно t </font> '''while''' "Дядяотец" чёрный. Если выполнить только перекрашивание, то может нарушиться постоянство чёрной высоты дерева по всем ветвям. Поэтому выполняем поворот. Если добавляемый узел был правым потомком, то необходимо сначала выполнить левое вращение, которое сделает его левым потомком. Таким образом, красный <font color=green>// нарушается свойство <tex>3</tex> и постоянство черной высоты сохраняются.</font> '''if''' "отец" {{---}} левый ребенок '''if''' есть "дядя" '''if''' "дядя" красный parent = black uncle = black grandfather = red t = grandfather '''else''' <font color=green>// случай, когда нет "дяди" </font> '''if''' t {{---}} правый сын t = parent leftRotate(t) parent = black grandfather = red rightRotate(grandfather) '''else''' <font color=green>// "отец" {{---}} правый ребенок </font> '''if''' есть "дядя" '''if''' "дядя" красный parent = black uncle = black grandfather = red t = grandfather[[Файл:Untitled '''else''' <font color=green>// нет "дяди" </font> '''if''' t {{---2}} левый ребенок t = t.png|250px|]]parent rightRotate(t) parent = black grandfather = red leftRotate(grandfather) root = black <font color=green>// восстанавливаем свойство корня </font>

# * Если у вершины нет детей, то изменяем указатель на неё у родителя на <tex>nil</tex>.# * Если у неё только один ребёнок, то делаем у родителя ссылку на него вместо этой вершины.# * Если же имеются оба ребёнка, то находим вершину со следующим значением ключа. У такой вершины нет левого ребёнка (так как такая вершина находится в правом поддереве исходной вершины и она самая левая в нем, иначе бы мы взяли ее левого ребенка. Иными словами сначала мы переходим в правое поддерево, а после спускаемся вниз в левое до тех пор, пока у вершины есть левый ребенок). Удаляем уже эту вершину описанным во втором пункте способом, скопировав её ключ в изначальную вершину.

1. * Если брат этого ребёнка красный, то делаем вращение вокруг ребра между отцом и братом, тогда брат становится родителем отца. Красим его в чёрный, а отца {{---}} в красный цвет, сохраняя таким образом черную высоту дерева. Хотя все пути по-прежнему содержат одинаковое количество чёрных узлов, сейчас <tex>x</tex> имеет чёрного брата и красного отца. Таким образом, мы можем перейти к следующему шагу. *:*:[[Файл:Untitled-3.png|400px|]]*:* Если брат текущей вершины был чёрным, то получаем три случая:** Оба ребёнка у брата чёрные. Красим брата в красный цвет и рассматриваем далее отца вершины. Делаем его черным, это не повлияет на количество чёрных узлов на путях, проходящих через <tex>b</tex>, но добавит один к числу чёрных узлов на путях, проходящих через <tex>x</tex>, восстанавливая тем самым влиянние удаленного чёрного узла. Таким образом, после удаления вершины черная глубина от отца этой вершины до всех листьев в этом поддереве будет одинаковой.**:**:[[Файл:Untitled-4.png|400px|]]**:** Если у брата правый ребёнок чёрный, а левый красный, то перекрашиваем брата и его левого сына и делаем вращение. Все пути по-прежнему содержат одинаковое количество чёрных узлов, но теперь у <tex>x</tex> есть чёрный брат с красным правым потомком, и мы переходим к следующему случаю. Ни <tex>x</tex>, ни его отец не влияют на эту трансформацию.**:**:[[Файл:Untitled-5.png|400px|]]**:** Если у брата правый ребёнок красный, то перекрашиваем брата в цвет отца, его ребёнка и отца {{---}} в чёрный, делаем вращение. Поддерево по-прежнему имеет тот же цвет корня, поэтому свойство <tex>3</tex> и <tex>4</tex> не нарушаются. Но у <tex>x</tex> теперь появился дополнительный чёрный предок: либо <tex>a</tex> стал чёрным, или он и был чёрным и <tex>b</tex> был добавлен в качестве чёрного дедушки. Таким образом, проходящие через <tex>x</tex> пути проходят через один дополнительный чёрный узел. Выходим из алгоритма.**:**: [[Файл:Untitled-6.png|400px|]]

[[Файл:Untitled-3Продолжаем тот же алгоритм, пока текущая вершина чёрная и мы не дошли до корня дерева.Из рассмотренных случаев ясно, что при удалении выполняется не более трёх вращений.png|400px|]]

2'''Псевдокод:''' '''func''' delete(key) Node p = root <font color=green>// находим узел с ключом key</font> '''while''' p.key != key '''if''' p.key < key p = p.right '''else''' p = p. Если брат текущей вершины был чёрным, то получаем три случая:left '''if''' у p нет детей '''if''' p {{---}} корень root = ''nil'' '''else'''* Оба ребёнка ссылку на p у брата чёрные. Красим брата в красный цвет и рассматриваем далее "отца вершины. Делаем его черным, это не повлияет " меняем на ''nil'' '''return''' Node y = ''nil'' Node q = ''nil'' '''if''' один ребенок ссылку на количество чёрных узлов у от "отца" меняем на путях, проходящих через ребенка y '''else''' <texfont color=green>b// два ребенка</texfont> y = вершина, но добавит один к числу чёрных узлов на путях, проходящих через со следующим значением ключа <texfont color=green>x// у нее нет левого ребенка </texfont>, восстанавливая тем самым влиянние удаленного чёрного узла '''if''' y имеет правого ребенка y.right.parent = y.parent '''if''' y {{---}} корень root = y.right '''else''' у родителя ссылку на y меняем на ссылку на первого ребенка y '''if''' y != p p.colour = y.colour p.key = y.key '''if''' y. Таким образом, после удаления colour == black <font color=green>// при удалении черной вершины черная глубина от отца этой вершины до всех листьев в этом поддереве будет одинаковой.могла быть нарушена балансировка</font> fixDeleting(q)

[[Файл '''func''' fixDeleting(p:Untitled'''Node''') <font color=green>// далее родственные связи относительно p</font> '''while''' p {{-4--}} черный узел и не корень '''if''' p {{---}} левый ребенок '''if''' "брат" красный brother = black parent = red leftRotate(parent) '''if''' у "брата" черные дети <font color=green>// случай <tex>1:</tex> "брат" красный с черными детьми</font> brother = red '''else''' '''if''' правый ребенок "брата" черный <font color=green>// случай, рассматриваемый во втором подпункте:</font> brother.left = black <font color=green>// "брат" красный с черными правым ребенком</font> brother = red rightRotate(brother) brother.colour = parent.colour <font color=green>// случай, рассматриваемый в последнем подпункте</font> parent = black brother.right = black leftRotate(parent) p = root '''else''' <font color=green>// p {{---}} правый ребенок</font> <font color=green>// все случаи аналогичны тому, что рассмотрено выше</font> '''if''' "брат" красный brother = black parent = red rightRotate(p.parent) '''if''' у "брата" черные дети brother = red '''else''' '''if''' левый ребенок "брата" черный brother.right = black brother = red leftRotate(brother); brother = parent parent = black brother.left = black rightRotate(p.png|400px|]]parent) p = root p = black root = black

* Если у брата правый ребёнок чёрный, а левый красный, то перекрашиваем брата и его левого сына и делаем вращение. Все пути по=== Объединение красно-чёрных деревьев ===Объединение двух красно-прежнему содержат одинаковое количество чёрных узлов, но теперь у деревьев <tex>xT_{1}</tex> есть чёрный брат с красным правым потомком, и мы переходим к следующему случаю. Ни <tex>xT_{2}</tex>, ни его отец не влияют на эту трансформацию. [[Файл:Untitled-5.png|400px|]] * Если у брата правый ребёнок красный, то перекрашиваем брата в цвет отца, его ребёнка и отца - в чёрный, делаем вращение. Поддерево по-прежнему имеет тот же цвет корня, поэтому свойство ключу <tex>3k</tex> возвращает дерево с элементами из $T_2$, $T_1$ и <tex>4</tex> не нарушаются$k$. Но у <tex>x</tex> теперь появился дополнительный чёрный предокТребование: либо <tex>a</tex> стал чёрным, или он и был чёрным и <tex>b</tex> был добавлен в качестве чёрного дедушкиключ $k$ {{---}} разделяющий. Таким образомТо есть $\forall k_1\in T_1, проходящие через <tex>x</tex> пути проходят через один дополнительный чёрный узел. Выходим из алгоритмаk_2 \in T_2: k_1\leqslant k\leqslant k_2$.

[[Файл:Untitled-6Если оба дерева имеют одинаковую черную высоту, то результатом будет дерево с черным корнем $k$, левым и правым поддеревьями $k_1$ и $k_2$ соответствено.png|400px|]]

Продолжаем тот же алгоритм, пока текущая вершина чёрная и мы не дошли до корня дерева.Из рассмотренных случаев ясно, что при удалении выполняется не более трёх вращенийТеперь пусть у $T_1$ черная высота больше (иначе аналогично).

=== Объединение красно-чёрных деревьев ===* Находим в дереве $T_1$ вершину $y$ на черной высоте, как у дерева $T_2$ вершину с максимальным ключом. Это делается несложно (особенно если мы знаем черную высоту дерева): спускаемся вниз, поддерживая текущую черную высоту.*:Идем вправо. Когда высота станет равной высоте $T_2$, остановимся.Объединение двух красно-чёрных деревьев <tex>T_{*:Заметим, что черная высота $T_2\geqslant 2$. Поэтому в дереве $T_1$ мы не будем ниже, чем $2$. Пусть мы не можем повернуть направо (сын нулевой), тогда наша высота $2$ (если мы в черной вершине) или $1}</tex> и <tex>T_{$ (если в красной). Второго случая быть не может, ибо высота $T_2\geqslant 2}</tex> по элементу <tex>x</tex> выполняется$, а в первом случае мы должны были завершить алгоритм, когда <tex>key[T_{1}] \leqslant пришли в эту вершину.*:Очевидно, мы окажемся в черной вершине (ибо следующий шаг даст высоту меньше). Очевидно, мы оказались на нужной высоте.*:Теперь пусть мы попали не туда. То есть существует путь от корня до другой вершины. Посмотрим на то место, где мы не туда пошли. Если мы пошли вправо, а надо бы влево, то $x</tex> $ имеет больший ключ (по свойству дерева поиска). А если пошли влево, а не вправо, значит правого сына и <tex>x \leqslant key[T_{2}]</tex>нет (точнее, есть, но он нулевой), значит в правом поддереве вообще нет вершин.*:Более того, все вершины с высотами меньше $y$, которые имеют ключ больше $y$, будут находиться в поддереве $y$. Действительно, где <tex>key[T]</tex> мы всегда идем вправо. Инвариант алгоритма на каждом шаге {{---}} максимальные ключи дерева <tex>T</tex>в поддереве текущей вершины содержатся все вершины, ключ которых больше текущего. Проверяется очевидно.Найдём чёрные высоты деревьев. Предположим также*:Еще поймем, что <tex>hb[T_{1}] \geqslant hb[T_{2}]</tex>как будем хранить черную высоту дерева. Тогда Изначально она нулевая (в пустом дереве <tex>T_{1}</tex> ищем среди чёрных вершин). Далее просто поддерживаем ее при операциях вставки и удаления.* Объединим поддерево. $k$ будет корнем, имеющих чёрную высоту <tex>hb[T_{2}]</tex>левым и правым сыновьями будут $T_y$ и $T_2$ соответственно.*:Покажем, вершину <tex>y</tex> с наибольшим ключомчто свойства дерева поиска не нарушены. Пусть <tex>T_{*:Так как все ключи поддерева $y}</tex> — поддерево $ не более $k$ и все ключи $T_2$ не менее $k$, то в новом поддереве с корнем <tex>y</tex>$k$ свойства выполняются.*:Так как $k$ больше любого ключа из $T_1$, то выполняется и для всего дерева. Объединяем это дерево с <tex>T_{2}</tex> * Красим $k$ в одно с красным корнем <tex>x</tex>красный цвет. Тогда свойство $4$ будет выполнено. Теперь родителем вершины <tex>x</tex> становится бывший отец вершины <tex>y</tex>Далее поднимаемся вверх, как во вставке операциях, поворотами исправляя нарушение правила $3$. Осталось восстановить свойства красно-черного дерева* В конце корень красим в черный, если до этого был красный (это всегда можно сделать, чтобы у красной вершины ничего не было красных детей. Делается аналогично алгоритму добавления вершинынарушив).

Если <tex>hb[T_{1}] \leqslant hb[T_{2}]</tex>'''Псевдокод:''' '''func''' join(T_1, то слияние происходит аналогичноT_2, только теперь мы ищем в дереве <tex>T_{2}</tex> среди чёрных вершинk) '''if''' черные высоты равны return Node(k, имеющих чёрную высоту <tex>hb[T_{1}]</tex>black, вершину <tex>y</tex> с наименьшим ключомT_1, T_2) '''if''' высота T_1 больше T' = joinToRight(T_1, T_2, k) T'.color = black return T' '''else''' T' = joinToLeft(T_1, T_2, k) T'.color = black return T' '''func''' joinToRight(T_1, T_2, k) Y = find(T_1, bh(T_2)) T' = Node(k, red, Y, T_2) '''while''' нарушение действуем как во вставке return T' '''func''' find(T, h) curBH = bh(T) curV = T '''while''' curBH != h curV = curV.right '''if''' curV. color == black --curBH return curV

Так как общее время выполнения каждой из операций порядка высоты дерева ,то все они выполняются за <tex>Сложность: $\mathcal{O}(T_1.h-T_2.h)=\mathcal{O}(\log{(n})</tex>.)$

Рассмотрим пример объединения двух === Разрезание красно-чёрных деревьев и вершины<tex>(35)</tex>:чёрного дерева ===Разрезание дерева по ключу $k$ вернет два дерева, ключи первого меньше $k$, а второго {{---}} не меньше.

[[Файл:UntitledПройдем вниз как во время поиска. Все левые поддеревья вершин пути, корень которых не в пути, будут в первом поддереве. Аналогично правые {{-7--}} в правом.Теперь поднимаемся и последовательно сливаем деревья справа и слева с ответами.png‎|550px|]]

Узнаём чёрную высоту левого За счет того, что функция '''$join$''' работает за разницу высот, и правого дерева. Чёрная высота левого и правого деревьев равна <tex>2</tex> и <tex>1</tex> соответственно.Так как чёрная высота левого дерева большемы объединяем снизу, то ищем в левом дереве чёрную вершину, имеющую чёрную высоту правого дереваблагодаря телескопическому эффекту на работу времени будут влиять только крайние слагаемые, с наибольшим ключом.Чёрная высота вершины<tex>(8)</tex> левого которые порядка глубины дерева равна высоте правого дерева и ключ является наибольшим. Поэтому вершина<tex>(8)</tex> становится левым сыном вершины<tex>(35)</tex>, а правое дерево будет правым сыном. Вершина<tex>(35)</tex> станет правым сыном вершины<tex>(0)</tex>:

[[Файл:Untitled-8'''Псевдокод''' '''func''' split(T, k) '''if''' T = nil return $\langle$nil, nil$\rangle$ '''if''' k < T.png‎|400px|]]key $\langle$L',R'$\rangle$ = split(L,k) return $\langle$L',join(R',T.key,R)$\rangle$ '''else''' $\langle$L',R'$\rangle$ = split(R,k) return $\langle$join(L,T.key,L'),R)$\rangle$

Далее проверяемСложность: не нарушили ли мы свойства красно-чёрного дерева. Так как присутствует нарушение$\mathcal{O}(у красной вершины есть красный сын\log(n), то перекрасим вершины и сделаем поворот:)$

[[Файл:UntitledТочно такой же алгоритм в разрезании AVL деревьев. Оно и понятно {{---9}} нам нужна лишь корректная функция '''$join$''', работающая за разницу высот.png‎|400px|]]

#Сбалансированность этих деревьев хуже, чем у [[АВЛ-дерево | АВЛ]], но работа по поддержанию сбалансированности в красно-чёрных деревьях обычно эффективнее. Для балансировки красно-чёрного дерева производится минимальная работа по сравнению с АВЛ-деревьями.#Использует всего $1 $ бит дополнительной памяти для хранения цвета вершины. Но на самом деле в современных вычислительных системах память выделяется кратно байтам, поэтому это не является преимуществом относительно, например, АВЛ-дерева, которое хранит $2 $ бита. Однако есть реализации красно-чёрного дерева, которые хранят значение цвета в бите. Пример {{---}} Boost Multiindex. В этой реализации уменьшается потребление памяти красно-чёрным деревом, так как бит цвета хранится не в отдельной переменной, а в одном из указателей узла дерева.

== Связь с [[2-3_дерево | 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-дереве имеет красится в черный цвет. Горизонтальные связи ведут из черного узла в красный узел, а вертикальные могут вести из любого узла в черный.

Во-первых, у {{Утверждение|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|]] При удалении элемента из узлаB-дерева совершаются аналогичные процессы поворота и окраски вершин в красно-черном дереве, только в обратном направлении. Так как все операции в 2-4 дереве происходят за счет изменения узлов, то они эквивалентны соответствующим операциям в котором один элемент красно-черном дереве.}} {{Теорема|statement=Приведенное выше сопоставление B-деревьев и красно--черных деревьев является изоморфизмом.|proof=Доказательство следует непосредственно из приведенных выше утверждений.}} черный.