\Section{AVL-дерево}{9 февраля}{Зуев Михаил}
  \Subsection{Опеределение и основные свойства}
\begin{Def}
  Высота поддерева -- наибольшее из расстояний от корня до листьев этого поддерева. Высота вершины -- высота поддерева этой вершины.
\end{Def}
\begin{Def}
  AVL-дерево -- сбалансированное двоичное дерево поиска, в котором для каждой вершины выполняется инвариант: разница между высотами левого и правого поддеревьев не больше 1.
\end{Def} 
\begin{Lm}
  AVL-дерево имеет высоту $O(\log n)$.
\begin{proof}
Оценим размер каждого поддерева. Сверху мы ограниченны размером полного бинарного дерева (т.к. это максамальное по размеру бинарное дерево с фиксированной высотой). Соотвественно для минимального размера наши сыновья должны быть также минимального размера и иметь разные высоты (это св-во рекурсивно распространяется вниз по дереву). Т.е. $SIZE_{h} \geq SIZE_{h - 1} + SIZE_{h - 2}$. Заметим, что эта формула соответствует числам Фибоначчи, а значит $SIZE_{h} \geq FIB_{h} \geq 1.6^{h}$ (оценка на значение h-го числа Фибоначчи). Получили, что $1.6^{h} \leq SIZE_{h} \leq 2^h.$\\
С помощью оценкци размера поддерева можно получить оценку глубины (прологорифмировав левое и правое неравенство поотдельноести):\\
$\log_2 size \leq h \leq log_{1.6} size$\\
\end{proof}
\end{Lm}

\vspace*{-2em}
\Subsection{Добавление}
  
При добавлении находим место в дереве, куда мы будем добавлять новый элемент $x$. Для этого спускаемся вниз по дерево как при поиске, пока не придем в пустую/фиктивную вершину. Вставляем в это место новую вершину. После добавления у нас могли измениться глубины, а значит в некоторых вершинах мог сломаться инвариант. Будем рассматривать вершины на пути от добавленной до корня (это можно сделать или циклом поднимаясь по предкам, или разворачия рекурсию, если операция добавления реализована рекурсивно). Пусть мы стоим в некоторой вершине $v$. Сначала проверяем, выполняется ли инвариант в текущем поддереве. Если да, то пересчитываем высоту вершины. Если она не изменилась, то заканчиваем исправление (т.к. высоты вершин выше тоже не могли измениться, а значит там ничего не сломано). Иначе продолжаем исправление и переходим к вершине выше.\\

Теперь рассмотрим ситуацию, когда для текущей вершины инвариант не выполняется. Т.е. один из сыновей вершины имеет высоту на 2 больше, чем второй. Для удобства будем считать, что это левый сын (для случая правого сына все операции аналогичны). Обозначим его высоту за $(h + 2_)$, тогда у правого высота $h$. У левого сына один из его сыновей имеет высоту $(h + 1)$. Заметим, что это всегда только 1 из сыновей (после текущего добавления мы могли увеличить высоту только одного из них, а тогда текущаяя вершина стала высоты $(h + 2)$ еще раньше). Рассмотрим 2 случая: если это левый сын сына (нужно больше сыновей), и если это правый.\\

В первом случаи нам на помощь придет правое (аналогично ему есть левое) малое вращение (в англ. вики его называют просто вращением). Название его соответсвтует тому, что оно делает: мы поворачиваем часть поддерева и переподвешиваем вершины, тем самым изменяя высоты.\\
\vspace*{-1em}
\begin{center}
  \includegraphics[scale=3]{Zuev/rot1.jpg}
\end{center}
\vspace*{-1em}
На рисунке показано, как происходит правое вращение. Левое вращание выполняется аналогично и является обратным к правому (из правого поддерева мы получим левое). Вследствии неравенства после поворота наше дерево останется корректным двоичным деревом поиска ($A \leq X$ обозначает, что все ключи в поддереве не больше $X$). После выполнения поворота на не нужно увеличивать высоту текущей вершины (на рисунке видно, что она не изменилась), а значит мы закончили исправления.\\

Во втором случаи на поможет большое правое вращение. На самом деле оно будет просто состоять из двух малых. Мы ставим на место корня текущего поддерева ,,плохого\textquoteleft\textquoteleft внука. Для этого мы поднимаем его сначала малым левым, а потом малым правым вращениями.
\vspace*{-1em}
\begin{center}
  \includegraphics[scale=2.95]{Zuev/rot2.jpg}
\end{center}
\vspace*{-1em}
Корни поддеревьев $B$ и $C$ до поворота могли иметь только высоты $h$ или $(h - 1)$. Поэтому они не будут ломать инвариант в своих поддереьях (их ,,братья\textquoteleft\textquoteleft имеют высоту $h$). Аналогично 1-му случаю нам не нужно увеличвать высоту корня поддерева, а значит мы закончили исправление дерева. Благодарю неравенству наше дерево осталось корректным деревом поиска.
