Изменения

|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)</tex> содержит не менее <tex>2^{hb(x)-1} - 1</tex> внутренних узлов.Здесь $h(x)$ {{---}} кратчайшее расстояние от вершины $x$ до какого-то из листьев.

Если высота узла <tex>x</tex> равна <tex>0,1</tex> , то <tex>x</tex> {{---}} это лист, <tex>hb(x) = 0, 1</tex> , <tex>2^{01-1} - 1 = 0.</tex>.

'''Индукционный переходПереход:'''

Пусть наше Так как любая внутренняя вершина (вершина, у которой высота положительна) имеет двух потомков, то применим предположение верно для высот до <tex>h'индукции к ним {{---}} их высоты на единицу меньше высоты $x$.</tex> Теперь рассмотрим внутреннюю вершину <tex>Тогда черные высоты детей могут быть $hb(x</tex> с двумя потомками, для которой <tex>)$ или $hb(x)=h'</tex>. Тогда если ее потомок <tex>p</tex> -1$ {{---}} если потомок красный или черный, то его высота <tex>соответственно. Тогда по предположению индукции в каждом из поддеревьев не менее $2^{hb(px)=h'-2}- 1</tex>, а если красный, то <tex>hb(p) = h'</tex>$ вершин. Но поскольку высота потомка меньше, чем высота узла <tex>x</tex>, для него выполняется индукционное предположение. В таком случае Тогда всего в поддереве узла <tex>x</tex> содержится не менее чем <tex>$2*(2^{h'hb(x)-12} - 1 )+ 1 = 2^{h'hb(x)-1} - 1 $ вершин ($+ 1 = $ {{---}} мы учли еще саму вершину $x$). Переход доказан.Теперь, если мы рассмотрим корень всего дерева в качестве $x$, то получится, что всего вершин в дереве не менее $2^{h'hb-1} - 1</tex>$.

Рассмотрим красно-чёрное дерево с высотой <tex>h.</tex> . Так как у красной вершины чёрные дети <tex>(</tex>по свойству <tex>$3$),</tex> количество красных вершин не больше <tex>$h / 2$. </tex> Тогда чёрных вершин не меньше, чем <tex>h / 2 - 1.</tex>.

Объединение двух красно-чёрных деревьев <tex>T_{1}</tex> и <tex>T_{2}</tex> по элементу ключу <tex>xk</tex> выполняетсявозвращает дерево с элементами из $T_2$, когда <tex>key[T_{1}] \leqslant x</tex> $T_1$ и <tex>x \leqslant key[T_{2}]</tex>, где <tex>key[T]</tex> $k$. Требование: ключ $k$ {{---}} максимальные ключи дерева <tex>T</tex>разделяющий.Найдём чёрные высоты деревьев. Предположим такжеТо есть $\forall k_1\in T_1, что <tex>hb[T_{1}] k_2 \in T_2: k_1\leqslant k\geqslant hb[T_{2}]</tex>. Тогда в дереве <tex>T_{1}</tex> ищем среди чёрных вершин, имеющих чёрную высоту <tex>hb[T_{2}]</tex>, вершину <tex>y</tex> с наибольшим ключом. Пусть <tex>T_{y}</tex> — поддерево с корнем <tex>y</tex>. Объединяем это дерево с <tex>T_{2}</tex> в одно с красным корнем <tex>x</tex>. Теперь родителем вершины <tex>x</tex> становится бывший отец вершины <tex>y</tex>. Осталось восстановить свойства красно-черного дерева, чтобы у красной вершины не было красных детей. Делается аналогично алгоритму добавления вершиныleqslant k_2$.

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