\Section{Splay Tree}{19 февраля}{Черепанов Валерий}

Splay-дерево "--- это самобалансирующееся бинарное дерево без каких-либо дополнительных условий.

\Subsection{Операции}

Все основные операции работают так же, как и в обычном BST, но для того, 
чтобы дерево сохраняло логарифмическую высоту после каждой ``обычной'' операции выполняется операция splay,
которая поднимает данную вершину в корень с помощью вращений, балансируя дерево.

\Subsubsection{Zig-zig вращение}

\begin{center}
\includegraphics{cherepanov/zig-zig.png}
\end{center}

\Subsubsection{Zig-zag вращение}

\begin{center}
\includegraphics{cherepanov/zig-zag1.png}
\end{center}

Если дедушки нет, то делаем такое вращение:

\begin{center}
\includegraphics{cherepanov/zig-zag2.png}
\end{center}

Нетрудно заметить, что zig-zag "--- это одно из вращений AVL-дерева.

\begin{Lm}
    \begin{gather*}
        \t{Пусть } (a + b) = 1; a, b > 0 \\
        \log a + \log b \rightarrow \max \\
        \Rightarrow a = b = \mfrac{1}{2}; \log a + \log b = -2
    \end{gather*}
\end{Lm}
\begin{proof}
    Можно продифференцировать или использовать неравенство о средних.
\end{proof}

\begin{Thm}
    \[\sum \text{depth}_i \le 4 n \log n\]
\end{Thm}

\begin{Thm}
    \begin{gather*}
        \t{Пусть } R_v = \log(\text{size}_v) \\
        a_i \le 3(R_u-R_v) \\
        a_i = t_i + \Delta \phi \\
        \phi \le \sum R_v \le n \log n
    \end{gather*}
\end{Thm}
\begin{proof}{Для zig-zig}
    \begin{gather*}
        \text{size}_z = \text{size}_x + \text{size}_{z'} + 1 \\
        \log(size_x) - \log(size_z) + \log(size_z) + \\
        \log(size_z') - \log(size_z) + \log(size_z) \le 2 \log (size_z) - 2 \\
        \Rightarrow R_{z'} \ le 2 R_z - R_x - 2 \\
        \Delta \phi = R_{x'} + R_{y'} + r_{z'} - R_x - R_y - R_z = \\
        R_{y'} + R_{z'} - R_x - R_y \le \\
        (R_{y'} - R_x - R_y) + (2R_z - R_x-2) \le 3(R_z-R_x)-2 \\
        t_i = 2
    \end{gather*}
\end{proof}

Для zig-zag доказывается так же.

\begin{Thm}
\item Хотим найти $i$ $k_i$ раз. Тогда
    \[\sum a_i \le \sum k_i \log (n/k_i)\]
\end{Thm}

\Subsubsection{Бор}
    В каждой вершине храним \t{map<char, int> next[N]}.
    Если map "--- это splay-дерево, то $t_i = |s| + \log{|\Sigma|}\cdot 2(k+\log n)$,где $\Sigma$ "--- алфавит.
    Идея в том, что каждое splay-дерево будет давать разность логарифмов и в итоге все сократится.

$\log(size_x) - \log(size_z) + \log(size_z) +
\log(size_z') - \log(size_z) + \log(size_z) \le 2 \log (size_z) - 2
\Rightarrow R_{z'} \ le 2 R_z - R_x - 2$

\begin{verbatim}
  y d
 x c
a b 

to (zig-zig)

 x'
a y'
 b z'
  c d
\end{verbatim}
  
Для zig-zag доказывается также.

\pagebreak
\Subsection{Другие деревья}
    \Subsubsection{2-3-Tree}

    \[L < x_1 < M < x_2 < R\]
    Вершина состоит из двух на 2-уровне.
    \[\log_3 n \le n \le log_2 n\]
    Add "--- спустится вниз и добавить новый ключ, перебалансировка (например, на 2-уровне вершина состоит из трех или на 3 уровне из двух).

    Правки oOo - o-O-o

    Удаление - обратная операция к удалению, а значит ключ мы тупо опускаем. Что получится?
    1. Нет жирных вершине
    2. Есть жирные

    \Subsubsection{АА-дерево ~ 2-3 Tree}
    Тоже самое, что 2-3 вершины на 2-уровне разделяются на две и называются черными. Остальные называются белыми.

    \Subsubsection{RB-дерево ~ 2-3-4 Tree}
    Черная глубина ``листьев'' -- вершин которые можно добавить в свободные места = const, но у чёрной вершины могут быть 2 сына. Единственная плохая ситуация, когда 2 красных соединены ребром. У красной как минимум 2 сына.

    \Subsubsection{B+ Tree}
    2-3 дерево -- частный случай B+ для случая k=2. [k 2k-1]. Когда становится 2k вершин, то можно разделить на 2 по k + поднять одну ??
