\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}