chapter03.tex

\chapter{Некоторые известные структуры данных в функциональном
  окружении}
\label{ch:3}

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

\section{Левоориентированные кучи}
\label{sc:3.1}

Как правило, множества и конечные отображения поддерживают эффективный
доступ к произвольным элементам. Однако иногда требуется эффективный
доступ только к \emph{минимальному} элементу.  Структура данных,
поддерживающая такой режим доступа, называется \term{очередь с
  приоритетами}{priority queue} или \term{куча}{heap}.  Чтобы избежать
путаницы с очередями FIFO, мы будем использовать второй из этих
терминов. На Рис.~\ref{fig:3.1} приведена простая сигнатура для кучи.

\begin{figure}
\begin{lstlisting}
signature HEAD = sig
  structure Elem: ORDERED
  type Heap

  val empty     : Heap
  val isEmpty   : Heap $\rightarrow$ bool
  val insert    : Elem.T $\times$ Heap $\rightarrow$ Heap
  val merge     : Heap $\times$ Heap $\rightarrow$ Heap

  val findMin   : Heap $\rightarrow$ Elem.T /*$\mbox{ возбуждает EMPTY при пустой куче }$*/
  val deleteMin : Heap $\rightarrow$ Elem.T /*$\mbox{ возбуждает EMPTY при пустой куче }$*/
end
\end{lstlisting}
% TODO: understand what is wrong with comments
\caption{Сигнатура для кучи (очереди с приоритетами).} \label{fig:3.1}
\end{figure}

\begin{remark}
  Сравнивая сигнатуру кучи с сигнатурой множества
  (Рис.~\ref{fig:2.7}), мы видим, что для кучи отношение порядка на
  элементах включено в сигнатуру, а для множества нет.  Это различие
  вытекает из того, что отношение порядка играет важную роль в
  семантике кучи, а в семантике множества не играет.  С другой
  стороны, можно утверждать, что в семантике множества большую роль
  играет отношение \emph{равенства}, и оно должно быть включено в
  сигнатуру.
\end{remark}

Часто кучи реализуются через деревья \term{с порядком
  кучи}{heap-ordered}, т.~е., в которых элемент при каждой вершине не
больше элементов в поддеревьях. При таком упорядочении минимальный
элемент дерева всегда находится в корне.

Левоориентированные кучи \cite{Crane1972, Knuth1973a} представляют
собой двоичные деревья с порядком кучи, обладающие свойством
\term{левоориентированности}{leftist property}: ранг любого левого поддерева
не меньше ранга его сестринской правой вершины.  Ранг узла
определяется как длина его \term{правой периферии}{right spine}
(т.~е., самого правого пути от данного узла до пустого).  Простым
следствием свойства левоориентированности является то, что правая
периферия любого узла~--- кратчайший путь от него к пустому узлу.

\begin{exercise}\label{ex:3.1}
  Докажите, что правая периферия левоориентированной кучи размера $n$
  всегда содержит не более $\lfloor \log(n+1) \rfloor$ элементов. (В
  этой книге все логарифмы, если не указано обратного, берутся по
  основанию 2.)
\end{exercise}

Если у нас есть некоторая структура упорядоченных элементов
\lstinline!Elem!, мы можем представить левоориентированные кучи как
двоичные деревья, снабженные информацией о ранге.
\begin{lstlisting}
  datatype Heap = E | T of int $\times$ Elem.T $\times$ Heap $\times$ Heap
\end{lstlisting}
Заметим, что элементы правой периферии левоориентированной кучи (да и
любого дерева с порядком кучи) расположены в порядке возрастания.
Главная идея левоориентированной кучи заключается в том, что для
слияния двух куч достаточно слить их правые периферии как
упорядоченные списки, а затем вдоль полученного пути обменивать
местами поддеревья при вершинах, чтобы восстановить свойство
левоориентированности.  Это можно реализовать следующим образом:
\begin{lstlisting}
  fun merge (h, E) = h
    | merge (E, h) = h
    | merge (h$_1$ as T(_, x, a$_1$, b$_1$), h$_2$ as T(_, y, a$_2$, b$_2$)) =
       if Elem.leq (x, y) then makeT (x, a$_1$, merge (b$_1$, h$_2$))
       else makeT (y, a$_2$, merge (h$_1$, b$_2$))
\end{lstlisting}
где \lstinline!makeT!~--- вспомогательная функция, вычисляющая ранг
вершины \lstinline!T! и, если необходимо, меняющая местами ее
поддеревья.
\begin{lstlisting}
  fun rank (E) = 0
    | rank (T (r, _, _, _)) = r
  fun makeT (x, a, b) = if rank a $\ge$ rank b then T (rank b + 1, x, a, b)
                                           else T (rank a + 1, x, b, a)
\end{lstlisting}
Поскольку длина правой периферии любой вершины в худшем случае
логарифмическая, \lstinline!merge! выполняется за время $O(\log n)$.

Теперь, когда у нас есть эффективная функция \lstinline!merge!,
оставшиеся функции не представляют труда: \lstinline!insert! создает
одноэлементную кучу и сливает ее с существующей, \lstinline!findMin!
возвращает корневой элемент, а \lstinline!deleteMin! отбрасывает
корневой элемент и сливает его поддеревья.
\begin{lstlisting}
  fun insert (x, h) = merge (T (1, x, E, E), h)
  fun findMin (T (_, x, a, b)) = x
  fun deleteMin (T (_, x, a, b)) = merge (a, b)
\end{lstlisting}
Поскольку \lstinline!merge! выполняется за время $O(\log n)$, столько
же занимают и \lstinline!insert! с \lstinline!deleteMin!. Очевидно,
что \lstinline!findMin! выполняется за $O(1)$. Полная реализация
левоориентированных куч приведена на Рис.~\ref{fig:3.2} в виде
функтора, принимающего в качестве параметра структуру упорядоченных
элементов.

\begin{remark}
  Чтобы не перегружать примеры мелкими деталями, мы обычно в
  фрагментах кода пропускаем варианты, ведущие к ошибкам. Например,
  приведенные выше фрагменты не показывают поведение
  \lstinline!findMin! и \lstinline!deleteMin! на пустых кучах.  Когда
  дело доходит до полной реализации, как на Рис.~\ref{fig:3.2}, мы
  всегда включаем в нее разбор ошибок.
\end{remark}

\begin{figure}
\begin{lstlisting}
functor LeftistHeap(Element: ORDERED) : Heap = struct
  structure Elem = Element

  datatype Heap = E | T of int $\times$ Elem.T $\times$ Heap $\times$ Heap

  fun rank E = 0
    | rank (T(r,_,_,_)) = r
  fun makeT (x,a,b) = if rank a $\geq$ rank b then T(rank b+1, x,a,b)
                       else T(rank a + 1, x,b,a)

  val empty = E
  fun isEmpty E = true
    | isEmpty _ = false

  fun merge (h,E) = h
    | merge (E,h) = h
    | merge ($h_1$ as T(_,x,$a_1$,$b_1$), h_2 as T(_,y,$a_2$,$b_2$)) =
       if Elem.leq (x,y) then makeT(x,$a_1$, merge($b_1$,$h_2$)
       else makeT(y,$a_2$,merge($h_1$,$b_2$))

  fun insert (x,h) = merge (T(1,x,E,E),h)
  fun findMin E = raise EMPTY
    | findMin (T(_,x,a,b)) = x
  fun deleteMin E = raise EMPTY
    | deleteMin (T(_,x,a,b)) = merge(a,b)
end
\end{lstlisting}

  \caption{Левоориентированные кучи.}
  \label{fig:3.2}
\end{figure}

\begin{exercise}\label{ex:3.2}
  Определите \lstinline!insert! напрямую, а не через обращение к \lstinline!merge!.
\end{exercise}

\begin{exercise}\label{ex:3.3}
  Реализуйте функцию \lstinline!fromList! типа \lstinline!Elem.T list $\to$ Heap!,
  порождающую левоориентированную кучу из неупорядоченного списка
  элементов путем преобразования каждого элемента в одноэлементную
  кучу, а затем слияния получившихся куч, пока не останется
  одна. Вместо того, чтобы сливать кучи проходом слева направо или
  справа налево при помощи \lstinline!foldr! или \lstinline!foldl!,
  слейте кучи за $\lceil \log n \rceil$ проходов, где на каждом
  проходе сливаются пары соседних куч. Покажите, что
  \lstinline!fromList! требует всего $O(n)$ времени.
\end{exercise}

\begin{exercise}\label{ex:3.4}
  \textbf{(Чо и Сахни \cite{ChoSahni1996})} Левоориентированные кучи
  со сдвинутым весом~--- альтернатива левоориентированным кучам, где
  вместо свойства левоориентированности используется свойство
  \term{левоориентированности, сдвинутой по весу}{weight-biased leftist
    property}: размер любого левого поддерева всегда не меньше размера
  соответствующего правого поддерева.
  \begin{enumerate}
  \item Докажите, что правая периферия левоориентированной кучи со
    сдвинутым весом содержит не более $\lfloor \log(n+1) \rfloor$ элементов.
  \item Измените реализацию на Рис.~\ref{fig:3.2}, чтобы получились
    левоориентированные кучи со сдвинутым весом.
  \item Функция \lstinline!merge! сейчас выполняется в два прохода:
    сверху вниз, с вызовами \lstinline!merge!, и снизу вверх, с
    вызовами вспомогательной функции \lstinline!makeT!. Измените
    \lstinline!merge! для левоориентированных куч со сдвинутым весом
    так, чтобы она работала за один проход сверху вниз.
  \item Каковы преимущества однопроходной версии \lstinline!merge! в
    условиях ленивого вычисления? В условиях параллельного вычисления?
  \end{enumerate}
\end{exercise}

\section{Биномиальные кучи}
\label{sc:3.2}

Биномиальные очереди \cite{Vuillemin1978, Brown1978}, которые мы,
чтобы избежать путаницы с очередями FIFO, будем называть \term{ биномиальными
кучами}{binomial heaps}~--- ещё одна распространенная реализация
куч. Биномиальные кучи устроены сложнее, чем левоориентированные, и, на
первый взгляд, не возмещают эту сложность никакими
преимуществами. Однако в последующих главах мы увидим, как в различных
вариантах биномиальных куч можно заставить \lstinline!insert! и
\lstinline!merge! выполняться за время $O(1)$.

Биномиальные кучи строятся из более простых объектов, называемых
биномиальными деревьями. Биномиальные деревья индуктивно определяются
так:
\begin{itemize}
\item Биномиальное дерево ранга 1 представляет собой одиночный узел.
\item Биномиальное дерево ранга $r+1$ получается путем
  \term{связывания}{linking} двух биномиальных деревьев ранга $r$, так
  что одно из них становится самым левым потомком второго.
\end{itemize}
Из этого определения видно, что биномиальное дерево ранга $r$ содержит
ровно $2^r$ элементов.  Существует второе, эквивалентное первому,
определение биномиальных деревьев, которым иногда удобнее
пользоваться: биномиальное дерево ранга $r$ представляет собой узел
с $r$ потомками $t_1\ldots t_r$, где каждое $t_i$ является
биномиальным деревом ранга $r-i$.  На Рис.~\ref{fig:3.3} показаны
биномиальные деревья рангов от 0 до 3.

\begin{figure}[h]
  \centering
  \input{figures/fig.3.3.tex}
  \caption{Биномиальные деревья рангов 0--3.}
  \label{fig:3.3}
\end{figure}

Мы представляем вершину биномиального дерева в виде элемента и списка
его потомков. Для удобства мы также помечаем каждый узел его рангом.
\begin{lstlisting}
  datatype Tree = Node of int $\times$ Elem.T $\times$ Tree list
\end{lstlisting}
Каждый список потомков хранится в убывающем порядке рангов, а элементы
хранятся с порядком кучи.  Чтобы сохранять этот порядок, мы всегда
привязываем дерево с большим корнем к дереву с меньшим корнем.
\begin{lstlisting}
  fun link (t$_1$ as Node (r, x$_1$, c$_1$), t$_2$ as Node (_, x$_2$, c$_2$)) =
        if Elem.leq (x$_1$, x$_2$) then Node (r+1, x$_1$, t$_2$ :: c$_1$)
        else Node (r+1, x$_2$, t$_1$ :: c$_2$
\end{lstlisting}
Связываем мы всегда деревья одного ранга.

Теперь определяем биномиальную кучу как коллекцию биномиальных
деревьев, каждое из которых имеет порядок кучи, и никакие два дерева
не совпадают по рангу. Мы представляем эту коллекцию в виде списка
деревьев в возрастающем порядке ранга.
\begin{lstlisting}
  Type Heap = Tree list
\end{lstlisting}
Поскольку каждое биномиальное дерево содержит $2^r$ элементов, и
никакие два дерева по рангу не совпадают, деревья размера $n$ в
точности соответствуют единицам в двоичном представлении
$n$. Например, число 21 в двоичном виде выглядит как 10101, и поэтому
биномиальная куча размера 21 содержит одно дерево ранга 0, одно ранга
2, и одно ранга 4 (размерами, соответственно, 1, 4 и 16). Заметим, что
так же, как двоичное представление $n$ содержит не более $\lfloor log
(n+1)\rfloor$ единиц, биномиальная куча размера $n$ содержит не более
$\lfloor log(n+1) \rfloor$ деревьев.

Теперь мы готовы описать функции, действующие на биномиальных
деревьях. Начинаем мы с \lstinline!insert! и \lstinline!merge!,
которые определяются примерно аналогично сложению двоичных чисел. (Мы
укрепим эту аналогию в Главе~\ref{ch:9}.) Чтобы внести элемент в кучу,
мы сначала создаем одноэлементное дерево (т.~е., биномиальное дерево
ранга 0), затем поднимаемся по списку существующих деревьев в порядке
возрастания рангов, связывая при этом одноранговые деревья. Каждое
связывание соответствует переносу в двоичной арифметике.
\begin{lstlisting}
  fun rank (Node (r, x, c)) = r
  fun insTree (t,[]) = [t]
    | insTree (t, ts as t' :: ts') =
       if rank t < rank t' then t :: ts else insTree (link (t, t'), ts')
  fun insert (x, ts) = insTree (Node (0, x, []), ts)
\end{lstlisting}
В худшем случае, при вставке в кучу размера $n = 2^k -1$, требуется
$k$ связываний и $O(k) = O(\log n)$ времени.

При слиянии двух куч мы проходим через оба списка деревьев в порядке
возрастания ранга и связываем по пути деревья равного ранга. Как и
прежде, каждое связывание соответствует переносу в двоичной
арифметике.
\begin{lstlisting}
  fun merge (ts$_1$, []) = ts$_1$
    | merge ([], ts$_2$) = ts$_2$
    | merge (ts$_1$ as t$_1$ :: ts'$_1$, ts$_2$ as t$_2$ :: ts'$_2$) =
       if rank t$_1$ < rank t$_2$ then t$_1$ :: merge (ts'$_1$, ts$_2$)
       else if rank t$_2$ < rank t$_1$ then merge (ts$_1$, ts'$_2$)
       else insTree (link (t$_1$, t$_2$), merge (ts'$_1$, ts'$_2$))
\end{lstlisting}

Функции \lstinline!findMin! и \lstinline!deleteMin! вызывают
вспомогательную функцию \lstinline!removeMinTree!, которая находит
дерево с минимальным корнем, исключает его из списка и возвращает как
это дерево, так и список оставшихся деревьев.
\begin{lstlisting}
  fun removeMinTree [t] = (t, [])
    | removeMinTree (t :: ts) =
        let val (t', ts') = removeMinTree ts
        in if Elem.leq (root t, root t') then (t, ts) else (t', t :: ts') end
\end{lstlisting}
Функция \lstinline!findMin! просто возвращает корень найденного дерева
\begin{lstlisting}
  fun findMin ts = let val (t, _) = removeMinTree ts in root t end
\end{lstlisting}
Функция \lstinline!deleteMin! устроена немного похитрее. Отбросив
корень найденного дерева, мы ещё должны вернуть его потомков в список
остальных деревьев. Заметим, что список потомков \emph{почти} уже
соответствует определению биномиальной кучи. Это коллекция
биномиальных деревьев с неповторяющимися рангами, но только
отсортирована она не по возрастанию, а по убыванию ранга. Таким
образом, обратив список потомков, мы преобразуем его в биномиальную
кучу, а затем сливаем с оставшимися деревьями.
\begin{lstlisting}
  fun deleteMin ts = let val (Node (_, x, ts$_1$), ts$_2$) = removeMinTree ts
                     in merge (rev ts$_1$, ts$_2$) end
\end{lstlisting}
Полная реализация биномиальных куч приведена на
Рис.~\ref{fig:3.4}. Все четыре основные операции в худшем случае
требуют $O(\log n)$ времени.

\begin{figure}
\begin{lstlisting}
functor BinomialHeap(Element: ORDERED) : Heap = struct
  structure Elem = Element
  datatype Tree = Node of int $\times$ Elem.T $\times$ Tree list
  datatype Heap = Tree list

  val empty = []
  val isEmpty ts = null ts

  fun rank (Node(r,x,c)) = r
  fun root (Node(r,x,c)) = x

  fun link ($t_1$ as Node ($r_1$,$x_1$,$c_1$), $t_2$ as Node ($r_2$,$x_2$,$c_2$)) =
    if Elem.leq ($x_1$,$x_2$) then Node(r+1, $x_1$, $t_2$::$c_1$)
    else Node(r+1, $x_2$, $t_1$::$c_2$)

  fun insTree (t,[]) = [t]
    | insTree (t, ts as t'::ts') =
       if rank t < rank t' then t::ts else insTree(link(t,t'), ts')

  fun insert (x,ts) = insTree(Node(0,x,[]), ts)

  fun merge ($ts_1$, []) $=$  $ts_1$
    | merge ([], $ts_2$) $=$  $ts_2$
    | merge ($ts_1$ as $t_1$::$ts_1'$, $ts_2$ as $t_2$::$ts_2'$) =
       if rank $t_1$ < rank $t_2$ then $t_1$ :: merge($ts_1$,$ts_2'$)
       else if rank $t_2$ < rank $t_1$ then $t_2$ :: merge($ts_2$, $ts_1'$)
       else insTree(link($t_1$,$t_2$), merge($ts_1'$,$ts_2'$)

  fun removeMinTree [] = raise EMPTY
    | removeMinTree [t] = (t,[])
    | removeMinTree (t::ts) =
      let val ($t'$, $ts'$) $=$ removeMinTree ts
      in if Elem.leq (root t, root t') then (t,ts) else (t', t::ts') end

  fun findMin ts = let val (t,_) = removeMinTree ts in root t end

  fun deleteMin ts =
    let val (Node(_, x,$ts_1$), $ts_2$) $=$ removeMinTree ts
    in merge (rev $ts_1$,$ts_2$) end
end
\end{lstlisting}
\centering

  \caption{Биномиальные кучи.}
  \label{fig:3.4}
\end{figure}

\begin{exercise}\label{ex:3.5}
  Определите \lstinline!findMin! напрямую, без обращения к \lstinline!removeMinTree!.
\end{exercise}

\begin{exercise}\label{ex:3.6}
  Большая часть аннотаций ранга в нашем представлении биномиальных куч
  излишня, потому что мы и так знаем, что дети узла ранга $r$ имеют
  ранги $r-1, \ldots, 0$. Таким образом, можно исключить
  поле-аннотацию ранга из узлов, а вместо этого помечать ранг корня
  каждого дерева, т.~е.,
  \begin{lstlisting}
    datatype Tree = Node of Elem $\times$ Tree list
    type Heap = (int $\times$ Tree) list
  \end{lstlisting}
  Реализуйте биномиальные кучи в таком представлении.
\end{exercise}

\begin{exercise}\label{ex:3.7}
  Одно из основных преимуществ левоориентированных куч над
  биномиальными заключается в том, что \lstinline!findMin! занимает в
  них $O(1)$ времени, а не $O(\log n)$. Следующая заготовка функтора
  улучшает время \lstinline!findMin! до $O(1)$, сохраняя минимальный
  элемент отдельно от остальной кучи.
  \begin{lstlisting}
    functor ExplicitMin (H : Heap) : Heap =
    struct
          structure Elem = H.Elem
          datatype Heap = E | NE of Elem.t $\times$ H.Heap
          ...
    end
  \end{lstlisting}
  Заметим, что этот функтор не ограничен биномиальными кучами, а
  принимает любую реализацию куч в качестве параметра. Закончите этот
  функтор так, чтобы \lstinline!findMin! требовал время $O(1)$, а
  функции \lstinline!insert!, \lstinline!merge! и
  \lstinline!deleteMin! каждая по $O(\log n)$. Предполагается, что
  нижележащая реализация \lstinline!H! для всех операций занимает
  $O(\log n)$.
\end{exercise}

\section{Красно-чёрные деревья}
\label{sc:3.3}

В разделе~\ref{sc:2.2} мы описали двоичные деревья поиска. Такие
деревья хорошо ведут себя на случайных или неупорядоченных данных,
однако на упорядоченных данных их производительность резко падает, и
каждая операция может занимать до $O(n)$  времени.  Решение этой
проблемы состоит в том, чтобы каждое дерево поддерживать в
приблизительно сбалансированном состоянии. Тогда каждая операция
выполняется не хуже, чем за время $O(\log n)$.  Одним из наиболее
популярных семейств сбалансированных двоичных деревьев поиска являются
красно-чёрные \cite{GuibasSedgewick1978}.

Красно-чёрное дерево представляет собой двоичное дерево поиска, в
котором каждый узел окрашен либо красным, либо чёрным. Мы добавляем
поле цвета в тип двоичных деревьев поиска из раздела~\ref{sc:2.2}.
\begin{lstlisting}
  datatype Color = R | B
  datatype Tree = E | T of Color $\times$ Tree $\times$ Elem $\times$ Tree
\end{lstlisting}
Все пустые узлы считаются чёрными, поэтому пустой конструктор
\lstinline!E! в поле цвета не нуждается.

Мы требуем, чтобы всякое красно-чёрное дерево соблюдало два
инварианта:
\begin{itemize}
\item \textbf{Инвариант 1.} У красного узла не может быть красного ребёнка.
\item \textbf{Инвариант 2.} Каждый путь от корня дерева до пустого
  узла содержит одинаковое количество чёрных узлов.
\end{itemize}
Вместе эти два инварианта гарантируют, что самый длинный возможный
путь по красно-чёрному дереву, где красные и чёрные узлы чередуются,
не более чем вдвое длиннее самого короткого, состоящего только из
чёрных узлов.

\begin{exercise}\label{ex:3.8}
  Докажите, что максимальная глубина узла в красно-чёрном дереве
  размера $n$ не превышает $2 \lfloor \log (n+1) \rfloor$.
\end{exercise}

Функция \lstinline!member! для красно-чёрных деревьев не обращает
внимания на цвета. За исключением заглушки в варианте для конструктора
\lstinline!T!, она не отличается от функции \lstinline!member! для
несбалансированных деревьев.
\begin{lstlisting}
  fun member (x, E) = false
    | member (x, T (_, a, y, b) =
       if x < y then member (x, a)
       else if x > y then member (x, b)
       else true
\end{lstlisting}
Функция \lstinline!insert! более интересна, поскольку она должна
поддерживать два инварианта баланса.
\begin{lstlisting}
  fun insert (x, s) =
        let fun ins E = T (R, E, x, E)
              | ins (s as T (color, a, y, b)) =
                  if x < y then balance (color, ins a, y, b)
                  else if x > y then balance (color, a, y, ins b)
                  else s
            val T (_, a, y, b) = ins s  (* $\mbox{гарантированно непустое}$ *)
        in T (B, a, y, b)
\end{lstlisting}
Эта функция содержит три существенных изменения по сравнению с \lstinline!insert! для
несбалансированных деревьев поиска. Во-первых, когда мы создаем новый
узел в ветке \lstinline!ins E!, мы сначала окрашиваем его в красный
цвет. Во-вторых, независимо от цвета, возвращаемого \lstinline!ins!,
в окончательном результате мы корень окрашиваем чёрным. Наконец, в
ветках \lstinline!x < y! и \lstinline!x > y! мы вызовы конструктора
\lstinline!T! заменяем на обращения к функции
\lstinline!balance!. Функция \lstinline!balance! действует подобно
конструктору \lstinline!T!, но только она переупорядочивает свои
аргументы, чтобы обеспечить выполнение инвариантов баланса.

Если новый узел окрашен красным, мы сохраняем Инвариант 2, но в
случае, если отец нового узла тоже красный, нарушается Инвариант 1. Мы
временно позволяем существовать одному такому нарушению, и переносим
его снизу вверх по мере перебалансирования. Функция
\lstinline!balance! обнаруживает и исправляет красно-красные нарушения,
когда обрабатывает чёрного родителя красного узла с красным
ребёнком. Такая чёрно-красно-красная цепочка может возникнуть в
четырёх различных конфигурациях, в зависимости от того, левым или
правым ребёнком является каждая из красных вершин. Однако в каждом из
этих случаев решение одно и то же: нужно преобразовать
чёрно-красно-красный путь в красную вершину с двумя чёрными детьми,
как показано на Рис.~\ref{fig:3.5}.  Это преобразование можно записать
так:
\begin{lstlisting}
  fun balance (B,T (R,T (R,a,x,b),y,c),z,d) = T (R, T (B,a,x,b),T (B,c,z,d))
    | balance (B,T (R,a,x,T (R,b,y,c)),z,d) = T (R, T (B,a,x,b),T (B,c,z,d))
    | balance (B,a,x,T (R,T (R,b,y,c),z,d)) = T (R, T (B,a,x,b),T (B,c,z,d))
    | balance (B,a,x,T (R,b,y,T (R,c,z,d))) = T (R, T (B,a,x,b),T (B,c,z,d))
    | balance body = T body
\end{lstlisting}
Нетрудно проверить, что в получающемся поддереве будут соблюдены оба
инварианта красно-чёрного баланса.

\begin{figure}[h]
  \centering
  \input{figures/fig.3.5.tex}
  \caption{Избавление от красных узлов с красными родителями.}
  \label{fig:3.5}
\end{figure}

\begin{remark}
  Заметим, что в первых четырех строках \lstinline!balance! правые
  части одинаковы. В некоторых реализациях Стандартного ML, в
  частности, в Нью-Джерсийском Стандартном ML (Standard ML of New
  Jersey), поддерживается расширение, называемое
  \term{или-образцы}{or-patterns}, позволяющее слить несколько
  вариантов с одинаковыми правыми сторонами в один
  \cite{FahndrichBoyland1997}. С использованием или-образцов можно
  переписать функцию \lstinline!balance! так:
  \begin{lstlisting}
    fun balance ( (B,T (R,T (R,a,x,b),y,c),z,d)
                | (B,T (R,a,x,T (R,b,y,c)),z,d)
                | (B,a,x,T (R,T (R,b,y,c),z,d))
                | (B,a,x,T (R,b,y,T (R,c,z,d))) ) = T (R, T (B,a,x,b),T (B,c,z,d))
      | balance body = T body
  \end{lstlisting}
\end{remark}

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

Реализация красно-чёрных деревьев полностью приведена на Рис.~\ref{fig:3.6}.

\begin{figure}
\begin{lstlisting}
functor RedBlackSet(Element: ORDERED) : SET =
  type Elem = Element.T
  datatype Color = R | B
  datatype Tree = E | T of Color $\times$ Tree $\times$ Elem $\times$ Tree
  type Set = Tree

  val empty = E
  fun member (x, E) = false
    | member (x, T (_, a, y, b) =
       if Element.lt (x,y) then member (x, a)
       else if Element.lt (y,x) then member (x, b)
       else true

  fun balance (B,T (R,T (R,a,x,b),y,c),z,d) = T (R, T (B,a,x,b),T (B,c,z,d))
    | balance (B,T (R,a,x,T (R,b,y,c)),z,d) = T (R, T (B,a,x,b),T (B,c,z,d))
    | balance (B,a,x,T (R,T (R,b,y,c),z,d)) = T (R, T (B,a,x,b),T (B,c,z,d))
    | balance (B,a,x,T (R,b,y,T (R,c,z,d))) = T (R, T (B,a,x,b),T (B,c,z,d))
    | balance body = T body

  fun insert (x, s) =
        let fun ins E = T (R, E, x, E)
              | ins (s as T (color, a, y, b)) =
                  if Element.lt (x,y) then balance (color, ins a, y, b)
                  else if Element.lt (y,x) then balance (color, a, y, ins b)
                  else s
            val T (_, a, y, b) = ins s  /* $\mbox{гарантированно непустое}$ */
        in T (B, a, y, b)
end
\end{lstlisting}
% TODO: опять курсив там где комменты

  \caption{Красно-чёрные деревья.}
  \label{fig:3.6}
\end{figure}

\begin{hint}
  Даже без дополнительных оптимизаций наша реализация сбалансированных
  двоичных деревьев поиска~--- одна из самых быстрых среди
  имеющихся. С оптимизациями вроде описанных в
  Упражнениях~\ref{ex:2.2} и \ref{ex:3.10} она просто летает!
\end{hint}

\begin{remark}
  Одна из причин, почему наша реализация выглядит настолько проще, чем
  типичное описание красно-чёрных деревьев (напр., Глава~14 в
  книге~\cite{CormenLeisersonRivest1990}), состоит в том, что мы
  используем несколько другие преобразования перебалансировки. В
  императивных реализациях обычно наши четыре проблематичных случая
  разбиваются на восемь, в зависимости от цвета узла, соседствующего с
  красной вершиной с красным ребёнком.  Знание цвета этого узла в
  некоторых случаях позволяет совершить меньше присваиваний, а в
  некоторых других завершить балансировку раньше. Однако в
  функциональной среде мы в любом случае копируем все эти вершины, и
  таким образом, не можем ни сократить число присваиваний, ни
  прекратить копирование раньше времени, так что для использования
  более сложных преобразований нет причины.
\end{remark}

\begin{exercise}\label{ex:3.9}
  Напишите функцию \lstinline!fromOrdList! типа \lstinline!Elem list $\to$ Tree!,
  преобразующую отсортированный список без повторений в красно-чёрное
  дерево. Функция должна выполняться за время $O(n)$.
\end{exercise}

\begin{exercise}\label{ex:3.10}
  Приведенная нами функция \lstinline!balance! производит несколько
  ненужных проверок. Например, когда функция \lstinline!ins!
  рекурсивно вызывается для левого ребёнка, не требуется проверять
  красно-красные нарушения на правом ребёнке.
  \begin{enumerate}
  \item Разбейте \lstinline!balance! на две функции
    \lstinline!lbalance! и \lstinline!rbalance!, которые проверяют,
    соответственно, нарушения инварианта в левом и правом
    ребёнке. Замените обращения к \lstinline!balance! внутри
    \lstinline!ins! на вызовы \lstinline!lbalance! либо \lstinline!rbalance!.
  \item Ту же самую логику можно распространить ещё на шаг и убрать
    одну из проверок для внуков. Перепишите \lstinline!ins! так, чтобы
    она никогда не проверяла цвет узлов, не находящихся на пути поиска.
  \end{enumerate}
\end{exercise}

\section{Примечания}
\label{sc:3.4}

Нуньес, Палао и Пенья \cite{NunezPalaoPena1995} и Кинг \cite{King1994}
описывают подобные нашим реализации, соответственно,
левоориентированных куч и биномиальных куч на Haskell.  Красно-чёрные
деревья до сих пор не были описаны в литературе по функциональному
программированию, в отличие от некоторых других вариантов
сбалансированных деревьев поиска, таких как AVL-деревья
\cite{Myers1982, Myers1984, BirdWadler1988, NunezPalaoPena1995},
2-3-деревья \cite{Reade1992} и деревья, сбалансированные по весу
\cite{Adams1993}.

Левоориентированные кучи были изобретены Кнутом \cite{Knuth1973a} как
упрощение структуры данных, введенной Крейном
\cite{Crane1972}. Виллемин \cite{Vuillemin1978} изобрел биномиальные
кучи; Браун \cite{Brown1978} исследовал многие свойства этой изящной
структуры данных. Гибас и Седжвик \cite{GuibasSedgewick1978}
предложили красно-чёрные деревья в качестве обобщающего описания для
многих других разновидностей сбалансированных деревьев.

%%% Local Variables:
%%% mode: latex
%%% TeX-master: "pfds"
%%% End: