\Section{Двоичное дерево поиска}{9 февраля}{Андрей Гусев}

\begin{Def}{Двоичное дерево поиска, binary search tree (BST)} --
  бинарное дерево, у которого оба поддерева вершины являются BST, причём значения всех вершин левого поддерева
  меньше значения вершины, а значения всех вершин правого поддерева больше значения вершины.
\end{Def}

В зависимости от реализации каждая вершина может иметь не более двух или ровно двух (с помощью добавления фиктивных вершин) детей.

\begin{Def}{Глубина вершины} -- расстояние до корня \end{Def}
\begin{Def}{Глубина дерева} -- максимальная глубина по всем вершинам \end{Def}

\Subsection{Хранение}

Двоичные деревья поиска можно хранить:
\begin{MyList}
  \item{\bf Как бинарные деревья:}
    \begin{code}
    struct Node {
      Node *l, *r, *parent;
      int x;
    }
    \end{code}
    Хранить ссылку на отца не обязательно.
  \item{\bf Способом для произвольных деревьев:}
    \begin{code}
    struct Node {
      Node *child, *next;
      int x;
    }
    \end{code}
    Дети каждой вершины хранятся списком. child указывает на первого из детей, next -- на следующего брата.
  \item{\bf Через отцов:}
    \begin{code}
    struct Node {
      Node *parent;
      int x;
    }
    \end{code}
    Такой способ хорош тем, что позволяет легко генерировать случайные деревья. Сделаем корнем вершину с номером 0, 
    каждую следующую будем подвешивать к случайной уже добавленной. $p_0 = 0$ -- корень, $0 \le p_i < i$ -- все остальные.
\end{MyList}

\pagebreak
\Subsection{Добавление}

\begin{MyList}
  \item{\bf Способ первый, простой:}
    \begin{code}
    Node *add(Node *v, int x) {
      if (v == 0)
        return new Node(0, 0, x);
      if (x > v->x)
        v->r = add(v->r, x);
      else
        v->l = add(v->l, x);
      return v;
    }
    \end{code}
  \item{\bf Способ второй, персистентный:}
    \begin{code}
    Node *add(Node *v, int x) {
      if (v == 0)
        return new Node(0, 0, x);
      if (x > v->x)
        return new Node(v->l, add(v->r, x), x);
      else
        return new Node(add(v->r, x), v->r, x);
    }
    \end{code}
    Достоинство этого способа -- персистентность. Он не изменяет переданное дерево, а создаёт новое, отличающееся от старого лишь добавленным значением.
  \item{\bf Способ третий, короткий:}
    \begin{code}
    void add(Node *&v, int x) {
      if (v == 0)
        v = new Node(0, 0, x);
      else if (x > v->x)
        add(v->r, x);
      else
        add(v->l, x);
    }
    \end{code}
\end{MyList}

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

\begin{MyList}
  \item{\bf Find}

    Поиск элемента в дереве. Спускаемся, пока не окажемся в вершине с искомым значением.
    На каждом шаге переходим к левому или правому сыну в зависимости от того, больше или меньше искомого текущее значение.
  \item{\bf Leftest, Rightest}

    Поиск наименьшего и наибольшего элемента в дереве. Переходим в левого или правого сына соответственно до тех пор, пока это возможно.
  \item{\bf Next, Previous}

    Поиск предыдущего и следующего элемента. Поскольку операции аналогичны, рассмотрим только поиск следующего. Возможно два случая.
  
    Пусть у данной вершины есть правый сын. Тогда любой предок текущей вершины либо больше правого поддерева 
    (если рассматриваемая вершина находится в его левом поддереве), либо меньше самой рассматриваемой вершины (если она в его правом поддереве).
    Любая вершина, не являющаяся предком или потомком рассматриваемой, лежит в другом поддереве, поэтому она либо меньше данной,
    либо больше её правого поддерева. Осталось взять наименьшую вершину в правом поддереве.
  
    Если правого поддерева нет, будем переходить к отцу до тех пор, пока исходная вершина не окажется в его левом поддереве.
    Первый предок, для которого данная вершина находится в левом поддереве -- это минимальный из предков этой вершины, превосходящий её.
    Вершины из правых поддеревьев этого и других предков, для которых наша вершина находится в левом, больше этих предков.
    Вершины из левых поддеревьев других предков меньше исходной, и поэтому они тоже не подходят.
    Таким образом, ответ -- это первый предок, для которого данная вершина лежит в левом поддереве.
  
  \begin{Lm}
    Цикл, обходящий дерево в порядке возрастания с помощью операции next
    \begin{code}
      for (v = leftest; v != 0; v = next(v))
    \end{code}
    Работает за линейное время.
  \end{Lm}
  
  Доказательство первое, простое.
  
  Маршрут $v$ в дереве почти совпадает с эйлеровым обходом. Каждое ребро, кроме рёбер на пути из корня в наибольший элемент будет пройдено два раза. 
  Рёбра же на пути из корня в самую правую вершину будут пройдены один раз.
  
  Доказательство второе, строгое.
  
  Индукция.
  
  База: листья обрабатываются за $\O(1)$. Это укладывается в $\O(n)$.
  
  Переход: Проход по дереву состоит из проходов по поддеревьям его корня. Оба поддерева обрабатываются за линейное от их размера время. 
  В сумме получается линейное от размера дерева время.
  \end{MyList}
Описанные операции работают за $\O(height)$, однако их можно ускорить до $\O(1)$.

\Subsection{Ускорение операций}

\begin{MyList}
  \item{\bf Find}
  
  Добавляем HashMap $x \rightarrow v$.
  \item{\bf Leftetst, Rightest}
  
  Храним значения крайних левого и правого элементов.
  \item{\bf Next, Previous}
  
  Поддерживаем двусвязный список вершин. Такая модификация называется прошивкой дерева. 
  Каждая вершина содержит указатели на следующую и предыдущую в порядке возрастания значения ключа.
  \begin{code}
  struct Node {
    Node *l, *r, *prev, *next;
    int x;
  }
  \end{code}
  В качестве примера использования прошивки дерева можно привести обход set.
  \begin{code}
    for (auto it = s.begin(); it != s.end(); it++) 
  \end{code}
  Этот код делает ровно то же самое, что и 
  \begin{code}
    for (auto &x : s) 
  \end{code}
\end{MyList}

\Subsection{Удаление}

Если вершина, которую мы хотим удалить, является листом, просто уберём её из дерева.

Если у вершины есть один сын, поставим его на её место.

Если же у вершины есть два поддерева, выберем минимальную (самую левую) вершину в правом поддереве и перенесём её на место удаляемой. 
Поскольку новая вершина меньше всех остальных вершин правого поддерева и больше всех вершин левого поддерева, условие двоичного дерева поиска сохранится.

\Subsection{Обходы дерева}

\begin{MyList}
  \item{\bf Симметричный обход}
    Выводит все вершины дерева в виде упорядоченного массива.
    \begin{code}
    void out(v) {
      if (!v) {
        return;
      }
      out(v->l);
      cout << v->x;
      out(v->r);
    }
    \end{code}

  \item{\bf Прямой обход}
    \begin{code}
    void out(v) {
      if (!v) {
        return;
      }
      cout << v->x;
      out(v->l);
      out(v->r);
    }
    \end{code}
    \begin{Lm}
      Вывод прямого обхода позволяет однозначно восстановить дерево.
    \end{Lm}
    Действительно, мы знаем, что первая вершина -- это корень дерева. После неё идёт набор чисел меньше неё. Это левое поддерево. 
    Затем идёт набор чисел больше неё. Это правое поддерево. Таким образом, мы умеем выделять корень и поддеревья. 
    Переходя от дерева к поддеревьям, мы будем спускаться от корня к листьям.
\end{MyList}

\pagebreak
\Subsection{Способы вывода дерева}

\begin{MyList}
  \item{\bf В строку}

    Каждое поддерево берётся в скобки. На выходе имеем одну строку.
    \begin{code}
      void Out( Node* v ) {
        if (!v) return;
        printf("(");
        Out(v->l);
        printf("%d", v->x);
        Out(v->r);
        printf(")");
      }
    \end{code}

  \item{\bf С отступом}

    Каждая вершина выводится на своей строке, с отступом от начала строки, пропорциональным её глубине. 
    Вывести на экран значение вершины $v$ с отступом $d$ можно с помощью строки:
    \begin{code}
      printf("%*s%d\n", 2 * d, "", v->x);
    \end{code}
    Пишется дольше, но вывод читается лучше.
\end{MyList}

\Subsection{Set, Multiset и Map}

На двоичных деревьях поиска возможно реализовать такие структуры, как множество, мультимножество и словарь.
Множество представляется просто BST, в которое значения добавляются как ключи вершин.
Словарь получается из множества добавлением к каждой вершине значения при сравнении только по ключу. 
Мультимножество получается, если добавлять к входным значениям дополнительную часть ключа.
