\Section{Red-Black, AA, 2-3, 2-3-4, B+ Trees}{19 февраля}{Горохов Никита}

Все описываемые деревья являются сбалансированными деревьями поиска. Далее будет о том, что они из себя представляют и как связаны друг с другом.

\Subsection{2-3 Tree}

В дереве существуют вершины двух видов: 2-вершины и 3-вершины. 2-вершины такие же, как и обычном дереве поиска, но обязательно имеют два ребёнка. 3-вершины содержат в себе сразу два ключа и имеют трёх детей. Таким образом любая вершина либо лист, либо имеет двух детей, либо трёх. Вершин с одним ребёнком в дереве нет.

\down

\textit{Пример дерева:}

\begin{center}
\includegraphics[scale=0.5]{gorokhov/2-3_example.png}
\end{center}

\textit{Пример двойной вершины:}

\begin{center}
\includegraphics[scale=0.5]{gorokhov/2-3_3_example.png}
\end{center}

Для ключей выполнено неравенство дерева поиска:

$L < x < M < y < R$ (в предположении, что все ключи различны)

\down

{\bf Инвариант:} все листья дерева находятся на одинаковой глубине.

Из этого, в свою очередь, следует, что $\log_3n \le h \le \log_2n$, где $h$ -- высота дерева.

\pagebreak

\THE{Добавление в дерево}


Найдём стандартной процедурой лист, в который должен быть помещён новый ключ. Добавим его в эту вершину. В результате чего в этой вершине могло стать три ключа. Это плохо, нужно исправлять. Возьмём средний ключ из трёх и "вытолкнем" его наверх, в предка. Теперь осталась вершина с двумя ключами и четырьмя детьми, разделим её на две, отдав первой меньший ключ и два левых сына, а правой второй ключ и оставшихся двух детей. Теперь на этом уровне всё стало в порядке, однако проблема могла появиться в предке. Поднимемся и сделаем для него аналогичные действия. Поднимаясь ближе к корню, либо в какой-то момент мы остановимся в вершине, в которой стало два ключа, либо, если на пути от корня до листа изначально все вершины имели по два ключа, из корня вытолкнется вверх один ключ, создав новый корень и увеличив высоту дерева на 1.

\down

\textit{Пример добавления:}

Изначально есть дерево с ключами 2, 5, 6, 9. 

Последовательно добавляются три ключа: 4, 10, 11.

\down

\begin{center}
\includegraphics[scale=0.8]{gorokhov/2-3_insertion.png}
\end{center}

\pagebreak

\THE{Удаление из дерева}

Найдём нужный ключ в дереве. Как и в обычном BST найдём следующий по значению ключ, он будет в листе. И обменяем местами ключи в этом листе и удаляемой вершине. Теперь этот ключ нужно удалить уже из листа.

Самый простой случай, когда в этом листе содержится два ключа. Тогда просто удалим нужный ключ, в вершине останется один ключ и структура дерева не нарушится.

 Так как некоторые случаи проталкивают "проблему" наверх, то и рассматривать случаи будем в общем случае. Для удобства введём понятие "пустая вершина". Это вершина с нулём ключей и одним сыном. Для пустой вершины-листа, очевидно, сын будет пустым. Заменим вершину, которую нам нужно удалить, на пустую. 

\begin{center}
\includegraphics[scale=1]{gorokhov/2-3_empty.jpg}
\end{center}

Теперь образовался один из случаев:

\begin{MyList}

\item У пустой вершины есть брат с двумя ключами. Заберём у него один ключ. А точнее переместим его в отца, а ключ отца заберём себе.

\begin{center}
\includegraphics[scale=1]{gorokhov/2-3_1_case.jpg}
\end{center}

\item У пустой вершины два брата, то есть у отца два ключа. Заберём один ключ себе, а из двух братьев сделаем одного.

\begin{center}
\includegraphics[scale=1]{gorokhov/2-3_2_case.jpg}
\end{center}

\pagebreak

\item У пустой вершины один брат с одним ключом и отец, соответственно, с одним ключом. Ни у кого ничего не заберёшь. Тогда склеим отца и брата, получим вершину с двумя ключами. Поместим пустую вершину на место отца, а новую вершину подвесим за неё. Сына пустой вершины подвесим за эту новую вершину. Теперь на данном уровне всё в порядке, но на уровень выше -- нет. Поднимемся и решим задачу уже там.

\begin{center}
\includegraphics[scale=1]{gorokhov/2-3_3_case.jpg}
\end{center}

\item И простой случай, который может образоваться только один раз, когда мы дошли до корня. А именно: пустая вершина оказалась на месте корня. В таком случае мы просто удаляем её, а её сын становится новым корнем.
\end{MyList}

\Subsection{AA tree}
\textit{Названы в честь придумавшего их Арне Андерссона.}

AA дерево -- бинарное дерево, вершины которого бывают чёрными и красными. Так как только что было описано устройство 2-3 дерева, то описать АА дерево будет проще всего, сказав, что оно получается из 2-3 дерева заменой обычных вершин на чёрные, а двойные вершины на цепочку из чёрной вершины и подвешенной к ней красной.

\begin{center}
\includegraphics[scale=1]{gorokhov/2-3_to_aa.png}
\end{center}

Из такого определения сразу следует несколько свойств АА дерева:

\begin{MyList}
\item Назовём \textit{чёрной глубиной вершины} количество чёрных вершин на пути от вершины до корня. В АА дереве чёрная глубина всех листьев одинакова.
\item Не бывает рёбер между красными вершинами.
\item Корень всегда чёрный.
\item Красная вершина всегда является левым сыном своего отца.
\end{MyList}

\Subsection{2-3-4 Tree}

2-3-4 дерево -- это то же 2-3 дерево, только с добавлением вершин с тремя ключами и четырьмя детьми. Как и у 2-3 дерева, глубина всех листьев равна. Операции добавления и удаления также аналогичны 2-3 дереву, только надо рассмотреть побольше случаев. Какой интерес для нас представляет это дерево, если оно почти ничем не отличается от 2-3 дерева? Сейчас узнаем.

\Subsection{Red-Black Tree}

Не случайно в этой главе дано столько деревьев и все они вместе. Мы уже встречались с аналогиями и этот случай не будет исключением. 

Как можно понять из названия, красно-чёрное дерево содержит красные и чёрные вершины, оно бинарное. Очень похоже на АА дерево, а если точнее, то это АА дерево без ограничения на то, что красные вершины могут быть только левыми сыновьями. И раз уж АА дерево можно получить из 2-3 дерева, RB дерево можно получить из 2-3-4 дерева. Для этого нужно применить следующие замены:

\begin{center}
\includegraphics[scale=1]{gorokhov/2-3-4_to_rb.png}
\end{center}

\pagebreak

Таким образом, мы представили 2-3-4 дерево в удобном бинарном формате. Работают эти деревья аналогично, но как раз благодаря тому, что RB дерево бинарное, его намного проще реализовывать и на практике используют именно его. Стоит упомянуть, что в целях упрощения реализации принято считать (а в последствии и программировать), что все листья дерева -- пустые чёрные вершины. А именно, во всех местах дерева, где у какой-то вершины мог бы быть сын, но его нет, создаётся фиктивная пустая чёрная вершина. На практике обычно создаётся ровно одна такая фиктивная вершина, на которую и ссылаются все "пустые дети".

\begin{center}
\includegraphics[scale=0.15]{gorokhov/rb_nil_example.png}
\end{center}

\Subsection{B+ Tree}

Обобщение 2-3 и 2-3-4 деревьев -- B деревья. Сейчас мы рассмотрим один из вариантов B деревьев -- B+ дерево.

B+ дерево порядка $t$ (со степенью ветвления $t$) -- дерево поиска со следующими свойствами:

\begin{MyList}
\item Корень дерева содержит от $1$ до $2t - 1$ ключей ($0$ или от $2$ до $2t$ детей). 

Все остальные узлы содержат от $t - 1$ до $2t - 1$ ключей (от $t$ до $2t$ детей).
\item Пусть $v$ -- какая-то вершина, не лист, $k_1, k_2, ... , k_n$ -- ключи в $v$, $T_1, T_2, ..., T_{n + 1}$ -- дети $v$. 

Тогда $\forall x \in T_1: x < k_1. \forall \ 2 \le i \le n : \forall x \in T_i : x \in (k_{i - 1}, k_i). \forall x \in T_{n+1} : x > k_n$.

Или проще -- как и в 2-3, и в 2-3-4, выполнен порядок на ключах и на ключах в поддеревьях детей.
\item Глубина всех листьев одинакова.
\item Все данные хранятся в листьях, в промежуточных же вершинах содержаться только ключи.
\item В каждом листе есть ссылка на соседний лист.
\end{MyList}

\begin{center}
\includegraphics[scale=0.8]{gorokhov/b+_example.png}
\end{center}

Если первые три пункта понятны, но непонятно, зачем они нужны, то последние два -- совсем непонятны.

А дело в том, что структура была придумана и используется для хранения данных во внешней памяти. Выигрыш перед остальными структурами данных заключается в том, что обращение к памяти, как правило, идёт не к паре байт, а сразу к нескольким сотням байт, и операция эта очень дорогая. Поэтому, грубо говоря, чем меньше обращений к памяти делает структура, тем быстрее она работает. И можно по свойствам B+  заметить, что если $t$ довольно большое, то обращений будет действительно мало. А именно, если $t$ взять, к примеру, равным $1001$ и хранить в дереве $10^9$ каких-то объектов, то поиск нужного потребует всего лишь $3$ обращения к памяти. На практике $t$ выбирается так, чтобы одна вершина дерева помещалась в один блок памяти и при этом содержала как можно больше ключей.
