\Section{Удаление из AVL и Неявный Ключ}{12 февраля}{Олег Свидченко}

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

\begin{MyList}
    \item Делаем так же, как и при обычном удалении из $BST$.
    \item На обратном ходе рекурсии делаем ребаланс.
          Заметим, что высота у ребенка уменьшилась не больше чем на $1$ $\SO$ достаточно сделать один из поворотов.
\end{MyList}
\begin{Lm}
    $Time(\t{AVL::add}) = \Omega(\log n)$.
    \begin{proof}
        От противного:
        \begin{MyList}
            \item Добавим $n$ неупорядоченных элементов в дерево.($o(n \cdot \log n)$).
            \item Обойдем дерево. ($\O(n)$).
        \end{MyList}
        Получили сортировку за время $o(n \cdot \log n)$. Противоречие.
    \end{proof}
\end{Lm}

\Subsection{Implicit Key}

\THE{$k$-ый элемент за $\O(\log n)$}

Для каждой вершины теперь дополнительно храним $size$ --- размер поддрева.
\begin{code}
struct Node
    Node* left, right;
    size_t size;
Node* Node::null = new Node();
    
inline size_t getKey(Node* v)
    return v->left->size; // `Элементы нумеруются с нуля`
    
inline void refreshSize(Node* v)
    v->size = v->left->size + v->right->size + 1;

Node* find(Node* v, size_t key)
    if (v == Node::null) return Node::null;
    if (getKey(v) == key) return v;
    if (getKey(v) < key) return find(v->right(), key - (v->left->size + 1);
    if (getkey(v) > key) return find(v->left(), key);
\end{code}

\THE{Массив при помощи AVL.}

Хотим уметь делать следующие операции:
\begin{MyList}
    \item\t{get($i$)} -- получить элемент на $i$-той позиции.
    \item\t{set($i,x$)} -- присвоить элементу на $i$-ой позиции значение $x$.
    \item\t{add($i,x$)} -- добавить элемент со значением $x$ после $i$-того.
\end{MyList}
Заметим, что в AVL ключ нам нужен только при спуске вниз и никак не влияет на ребаланс. Значит, можно использовать неявный ключ ничего не сломав. Тогда:
\begin{MyList}
    \item\t{get($i$)} := AVL.find($i$)->data;
    \item\t{set($i,x$)} := AVL.find($i$)->data = x;
    \item\t{add($i,x$)} := AVL.add($i$)->data = x; 
\end{MyList}
Здесь AVL.find($key$) -- поиск по неявному ключу, описанный выше, а AVL.add($key$) -- добавление как в обычном AVL, но с поправкой на неявный ключ, 
то есть, со спуском, как в AVL.find($key$). Очевидно, что время работы каждой операции $\O(\log n)$.

\Subsection{Случайное BST-дерево}

Рассмотрим несбалансированное BST. Очевидно, что случайная перестановка задает случайное дерево.

\begin{Lm}
    {\bf Вспомогательная лемма}
    $\sum\limits_{v} size_{v} = \sum\limits_{v} depth_{v}$
    \begin{proof}
        Зафиксируем $v$.
        \begin{MyList}
            \item $v$ лежит в поддереве любой вершины, находящейся на пути от корня до $v$.
            \item Нет других вершин, у которых $v$ лежит в поддереве.
        \end{MyList}
    \end{proof}
\end{Lm}
\begin{Lm}
    Матожидание средней глубины вершины равно $2 \cdot \ln n$.
    \begin{proof}
        В доказателстве \t{QuickSort} мы использовали формулу подсчета времени $T(n) = T(x) + T(n-x) + n$.
        Эта же формула справедлива для подсчета суммы количества вершин в поддеревьях, поэтому сошлёмся на док-во \t{QuickSort}.
    \end{proof}
\end{Lm}
\begin{Lm}
    Матожидание максимальной глубины вершины не больше $4 \cdot \ln n$;
    \begin{proof}
        Эта лемма была без доказательства.
    \end{proof}
\end{Lm}
