\chapter{非破壊 TreeMap の実装}
JungleのIndexは、Functional Javaの非破壊 TreeMap を用いて実装を行っている。
しかし、Functional Java の TreeMap は、木の変更の手間が大きい、並列実行時処理速度が落ちるなど、実用的な性能を持っていなかった。
そのため、Jungle の性能も、TreeMap部分がネックとなっていた。

その問題を解決するため、Jungleで使用する非破壊 TreeMap を作成した。
TreeMapは、Red Black Treeのアルゴリズム用いる。

\section{Red Black Tree}
Red Black Treeは二分探索木の一つで、以下の条件を満たした木のことである。

\begin{enumerate}
\item ノードは赤か黒の色を持つ。
\item ルートノードの色は黒。
\item 全ての葉は黒である。
\item 赤いノードの子は黒色である。
\item 全ての葉からルートまでのパスには、同じ個数の黒いノードがある。
\end{enumerate}

Red Black Treeは、データの挿入、削除時に、上記の条件を崩さないように木のバランスを取る。
この条件により、Red Black Treeはデータの検索、削除、探索をO(log n)で行える。

\section{非破壊 TreeMap の定義}
非破壊 TreeMapは、Javaのジェネリクスを用いて、{\tt TreeMap<K,V>Key}と定義される。
TreeMapを作る際に、K,Vに任意の型を記述することで、
KeyとValueで使用する型を設定できる。
ソースコード\ref{src:TreeMapExample}に、 Key を String 型・ Value を ByteBuffer 型で定義するサンプルコードを記述する。

\begin{lstlisting}[frame=lrbt,numbers=left,label=src:TreeMapExample,caption=TreeMapの定義サンプル]
TreeMap<String, ByteBuffer> map = new TreeMap<>();
\end{lstlisting}

\newpage

\section{非破壊 TreeMap のAPI}

非破壊 TreeMap は、値の挿入・削除を行うために、表\ref{RedBlackTreeAPI}に記述してあるAPIを提供している。
\begin{table}[htb]
\begin{center}
\caption{非破壊 TreeMap に実装されているAPI}
\begin{tabular}{|p{15em}|p{24em}|}        \hline
{\tt Node getRoot()} & TreeMap のルートノードを返す。 \\ \hline
{\tt boolean isEmpty()} & TreeMap が値を保持していないなら{\tt true}を返す。  \\ \hline
{\tt TreeMap<K,V> put(K key, V value)} & TreeMap に{\tt key:value} の組で値を挿入し、新しい TreeMap を返す。 \\ \hline
{\tt TreeMap<K,V> delete(K key)} & TreeMap に{\tt key} とペアで格納されている値を削除し、新しい TreeMap を返す。\\ \hline
{\tt Iterator<K> keys()} & TreeMap が保持している全ての {\tt key} を Iteratorで返す。 \\ \hline
\end{tabular}
\label{RedBlackTreeAPI}
\end{center}
\end{table}

非破壊 TreeMapは、put・deleteを行うと編集後の新しい TreeMap を返すため、新しい TreeMap で受ける必要がある(ソースコード\ref{src:TreeMapEditExample})。
この時返ってくる {\tt newMap}と、編集前の {\tt map} は別オブジェクトである。

\begin{lstlisting}[frame=lrbt,numbers=left,label=src:TreeMapEditExample,caption=TreeMapの編集例]
TreeMap<String,String> map = new TreeMap<>();
TreeMap<String,String> newMap = map.put("key","value");
\end{lstlisting}

\section{非破壊 Red Black Treeへのデータの挿入}
非破壊 Red Black Treeへのデータの挿入は、以下の手順で行われる。

\begin{enumerate}
\item 挿入を行うノードと、現在のノードを比較する。
\item 比較の結果、大きかった場合右に、小さかった場合左のノードに進む。
\item 挿入を行う場所にたどり着くまで、１・２を繰り返す。
\item 現在の位置に、赤色でノードを挿入する。
\item 木のバランスを取りながら、ルートまでの経路の複製を行う。その際、変更が加えられないノードへは参照を行い過去の木と最大限共有を行う。
\end{enumerate}

Red Black Treeのデータ挿入時のバランスは、次の5パターンに分けられる。
これ以降の説明では、挿入したノードは、ノードinsと記述する。

\section{データ挿入時のバランス ケース1}

\begin{enumerate}
\item ノードを挿入した位置がルート
\end{enumerate}
挿入時上記の条件を満たしている場合、ルートノードの色を黒に変更することで木のバランスを取る。
ルートノードの色を黒に変更しても、左右のSub Treeの黒の個数が一つ増えるだけなので、Red Black Treeの条件は守られる。


\section{データ挿入時のバランス ケース2}
\begin{enumerate}
\item 挿入したノードinsの親ノードBが黒。
\end{enumerate}

バランス時、上記の条件を満たしている場合、Red Black Treeの条件は崩れないため、赤色でノードを挿入して問題はない。%(図\ref{fig:RedBlackTreeInsert1})。

%\begin{figure}[htpb]
%\begin{center}
%\includegraphics[scale=0.5]{figures/RedBlackTreeInsert1.pdf}
%\caption{データ挿入時のバランス2}
%\label{fig:RedBlackTreeInsert1}
%\end{center}
%\end{figure}

\section{データ挿入時のバランス ケース3}
\begin{enumerate}
\item 挿入したノードinsの親の親ノードAが黒。
\item ノードAの両方の子ノードB・Cが赤。
\end{enumerate}

バランス時、上記の条件を満たしている場合、ノードB・Cを黒に、ノードAを赤に変更する(図\ref{fig:RedBlackTreeInsert2})。

また、本章の図に表記されている四角のノードの色は、Red Black Treeの条件を守られているなら問わず、それ以下の子ノードは省略してあるものとする。
\begin{figure}[htpb]
\begin{center}
\includegraphics[scale=0.5]{figures/RedBlackTreeInsert2.pdf}
\caption{データ挿入時のバランス3}
\label{fig:RedBlackTreeInsert2}
\end{center}
\end{figure}


バランス後、ノードAの色が変わってしまったため、ノードAを新しくノードinsとして再帰的に木のバランスを行う。
この変更は最悪の場合ルートまで続く。

\section{データ挿入時のバランス ケース4}
\begin{enumerate}
\item 挿入したノードinsの親の親ノードAが黒。
\item ノードAの、挿入したノード側の子ノードBが赤。
\item 逆側の子ノードCが黒。
\item ノードinsがノードBの木の中心側の子。
\end{enumerate}

バランス時、上記の条件を満たしている場合、ノードBを中心に外側に回転処理を行い(図\ref{fig:RedBlackTreeInsert3})、次節に記述するバランス5を行う。
その際、ノードBをノードinsとして扱う。

\begin{figure}[htpb]
\begin{center}
\includegraphics[scale=0.5]{figures/RedBlackTreeInsert3.pdf}
\caption{データ挿入時のバランス4}
\label{fig:RedBlackTreeInsert3}
\end{center}
\end{figure}



\section{データ挿入時のバランス ケース5}
\begin{enumerate}
\item 挿入したノードinsの親の親ノードAが黒。
\item ノードAの、挿入したノード側の子ノードBが赤。
\item 逆側の子ノードCが黒
\item ノードinsがノードBの木の外側の子。
\end{enumerate}

バランス時、上記の条件を満たしている場合、ノードAを中心に内側に回転処理を行い、回転後ノードAとノードBの色を入れ替える。

\begin{figure}[htpb]
\begin{center}
\includegraphics[scale=0.5]{figures/RedBlackTreeInsert4.pdf}
\caption{データ挿入時のバランス5}
\label{fig:RedBlackTreeInsert4}
\end{center}
\end{figure}


赤黒木は、データ挿入時にこれらの処理を行うことで、木のバランスを取る。

\section{Red Black Treeのノード削除}
Red Black Treeのノード削除は、以下の手順で行われる。

\begin{enumerate}
\item 削除を行うノードと、現在のノードを比較する。
\item 比較の結果、大きかった場合右、小さかった場合左のノードに進む。
\item 削除を行うノードにたどり着くまで、１・２を繰り返す。
\item ノードに子が無い場合削除を行う。
\item 片側に部分木(子ノード)がある場合、ノードを削除した後、部分木のルートを昇格させる。
\item 両側に部分木(子ノード)がある場合は、左部分木の最大の値を持つノードの値を取得し、削除を行うノードと同じ色に変更した後、置換する。
\item 置換したノードを削除する(ここで削除させるノードは部分木の最大値であるため、子ノードは1つ以下、つまり削除の手順4・5どちらかの手順で削除できる)。
\item 削除したノードから、木のバランスを取りながら、ルートまでの経路の複製を行う。その際、変更が加えられないノードへは参照を行い過去の木と最大限共有を行う。
\end{enumerate}


RedBlackTreeのバランスは、ノード削除時の状態によって、次の6パターンに分けられる。
また。これ以降削除したノードを、ノードdelと記述する。


\section{データ削除時のバランス ケース1}
\begin{enumerate}
\item ノードdelがルート。
\end{enumerate}

上記の条件を満たしている場合、全ての経路の黒ノード数が1つ減った状態で条件が成立しバランスは終了する。

\section{データ削除時のバランス ケース2}
\begin{enumerate}
\item ノードdelが黒。
\item ノードA・B・C・D・E・Fが黒。
\end{enumerate}

バランス時、上記の条件を満たしている場合、ノードBを赤に変える(図\ref{fig:RedBlackTreeDelete1})。
そうすることで、ノードB・E・F以下の黒ノードの階層が減って、ノードA以下の木のバランスが回復する。
その後、Aを新たなノードdelとして木のバランスを行う。
このバランスは最悪の場合ルートまで続き、ケース2で終了する。

\begin{figure}[htpb]
\begin{center}
\includegraphics[scale=0.45]{figures/RedBlackTreeDelete1.pdf}
\caption{データ削除時のバランス2}
\label{fig:RedBlackTreeDelete1}
\end{center}
\end{figure}


\newpage
\section{データ削除時のバランス ケース3}
\begin{enumerate}
\item ノードdelが黒。
\item ノードA・C・D・E・Fが黒
\item ノードBが赤。
\end{enumerate}

上記の条件を満たしている場合、ノードAを中心に外側に回転、その後ノードAを赤に、ノードBを黒に変更する(図\ref{fig:RedBlackTreeDelete2})。
その後、ノードdelを基準に再び木のバランスを行う。
この時のバランスは、図\ref{fig:RedBlackTreeDelete2}における、ノードEの子供の色に応じてケース4・5・6のどれかに帰着する。

\begin{figure}[htpb]
\begin{center}
\includegraphics[scale=0.45]{figures/RedBlackTreeDelete2.pdf}
\caption{データ削除時のバランス3}
\label{fig:RedBlackTreeDelete2}
\end{center}
\end{figure}

\newpage

\section{データ削除時のバランス ケース4}
\begin{enumerate}
\item ノードdelが黒。
\item ノードB・C・D・E・Fが黒
\item ノードAが赤。
\end{enumerate}

上記の条件を満たしている場合、ノードAを黒に、ノードBを赤に変更する(図\ref{fig:RedBlackTreeDelete3})。
そうすることで、ノードA側の右側のSub Treeの黒の深さを変えることなく、左側のSub Treeの黒の深さが1つ増え、バランスが取れる。
\begin{figure}[htpb]
\begin{center}
\includegraphics[scale=0.45]{figures/RedBlackTreeDelete3.pdf}
\caption{データ削除時のバランス4}
\label{fig:RedBlackTreeDelete3}
\end{center}
\end{figure}


\newpage
\section{データ削除時のバランス ケース5}
\begin{enumerate}
\item ノードdelが黒。
\item ノードB・C・D・Fが黒。
\item ノードEの色が赤。
\end{enumerate}

上記の条件を満たしている場合、ノードBを中心に外側に回転、その後、ノードEを黒に、ノードBを赤に変更する(図\ref{fig:RedBlackTreeDelete4})。
そして、データ削除時のバランス ケース7に帰着する。

\begin{figure}[htpb]
\begin{center}
\includegraphics[scale=0.45]{figures/RedBlackTreeDelete4.pdf}
\caption{データ削除時のバランス5}
\label{fig:RedBlackTreeDelete4}
\end{center}
\end{figure}


\newpage
\section{データ削除時のバランス ケース6}
\begin{enumerate}
\item ノードdelが黒。
\item ノードB・C・Dが黒。
\item ノードFの色が赤。
\end{enumerate}

上記の条件を満たしている場合、ノードAを中心にノードdel側に回転、その後、ノードAとノードBの色を交換し、ノードFを黒にする(図\ref{fig:RedBlackTreeDelete5})。
そうすることで、ノードE・Fの黒の深さを変えること無く、ノードrepの黒の深さを1増やせるため、木のバランスが取れる。

\begin{figure}[htpb]
\begin{center}
\includegraphics[scale=0.45]{figures/RedBlackTreeDelete5.pdf}
\caption{データ削除時のバランス6}
\label{fig:RedBlackTreeDelete5}
\end{center}
\end{figure}

Red Black Treeは、削除時に上記のバランスを行うことで、木のバランスを保っている。

これらの機能を実装することで、非破壊TreeMapは完成した。