\chapter{Red Black Tree}

実装を行う Red Black Tree の説明を行う。
Red Black Tree は 木構造の基本操作である Insert(挿入)、Delete(削除)、Search(検索)の
いずれに置いても最悪実行時間が $O(log \: n)$であり、データ構造のうちで最善のものの一つである。
そのため、実用的なデータ構造として知られている。

\section{Tree}
Tree (木構造)とは、非常に有用なデータ構造である。
\figref{tree}の○の部分を node (節) と呼び、top node を root(根) と呼ぶ。
特に、根を持つ木構造のことを強調して、Rooted Tree (根付き木) と呼ぶ事がある。

\section{Binary Tree}
各 node からすぐ下に辺で結ばれている node を
その node の child またはson (子あるいは子供)と呼ぶ。
child 側から上の辺を parent (親) と呼ぶ。
\figref{bt}のように、各 node が持つ child が高々2つである Tree を Binary Tree (2分木)と呼ぶ。

\begin{figure}[htbp]
  \begin{minipage}{0.5\hsize}
    \begin{center}
      \includegraphics[height=4.5cm]{pic/rbt/tree.pdf}
    \end{center}
  \caption{Tree の例}
  \label{tree}
  \end{minipage}
  \begin{minipage}{0.5\hsize}
    \begin{center}
      \includegraphics[height=4.5cm]{pic/rbt/bt.pdf}
    \end{center}
    \caption{Binary Tree の例}
    \label{bt}
  \end{minipage}
\end{figure}

\section{Binary Search Tree}
Rooted Binary Tree に対して、 以下の制約を持つものを、Binary Search Tree と呼ぶ。

$左側の子孫にある要素 < 親 < 右側の子孫にある要素$

例を以下\figref{bst}に示す

\begin{figure}[H]
  \begin{center}
    \includegraphics[height=7.5cm]{pic/rbt/bst.pdf}
  \end{center}
  \caption{Binary Search Tree の一例}
  \label{bst}
\end{figure}

\section{RedBlackTree}
RedBlackTree (または赤黒木)とは平衡2分探索木の一つである。
2分探索木の点にランクという概念を追加し、そのランクの違いを赤と黒の色で分け、
以下の定義に基づくように
木を構成した物である。図では省略しているが、値を持っている点の下に黒色の空の葉があり、
それが外点となる。

\begin{enumerate}
  \item 各点は赤か黒の色である。
  \item 点が赤である場合の親となる点の色は黒である。
  \item 外点(葉。つまり一番下の点)は黒である。
  \item 任意の点から外点までの黒色の点はいずれも同数となる。
\end{enumerate}
参考となる\figref{rbt}を以下に示す。上記の定義を満たしていることが分かる。

\begin{figure}[H]
  \begin{center}
    \includegraphics[height=6.5cm]{pic/rbt/rbt.pdf}
  \end{center}
  \caption{Red Black Tree の一例}
  \label{rbt}
\end{figure}

\section{Left Learning Red Black Tree}
Left Learing Red Black Tree とは Red Black Tree の変形である。
Red Black Tree の 仕様を満たしながら、実装が容易である。

\figref{rbt}に入っていた値を Left Learning Red Black Tree に適応した場合を
\figref{llrbt}に示す。
Left Learning Red Black Tree では赤色の node は parent から見て
左の node にしか 現れない Red Black Tree となる。
これにより、パターンマッチの分岐を減らす事ができ、実装が容易になる。

本来の Red Black Tree の実装は困難であるため、
本論では Red Black Tree の仕様を満たしている
Left Learning Red Black Tree を検証する。

\begin{figure}[H]
  \begin{center}
    \includegraphics[height=7.5cm]{pic/rbt/llrbt.pdf}
  \end{center}
  \caption{Left Learning Red Black Tree の一例}
  \label{llrbt}
\end{figure}