\chapter{Red Black Jungle Tree}
Default Jungle Treeにおいて、Indexの更新は大きな手間となっている。
Indexに使用する属性名が1種類で、木構造の形がデータを表現していない場合、Jungle Tree自身をIndexとしたほうが、効率的に木構造を構築できる。
そこで、ノードの挿入を行うと木のバランスを取る、Red Black Treeの性質を組み込んだRed Black Jungle 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{Red Black Jungle Treeの作成}
Red Black Jungle Treeを作成するため、Jungleに{\tt createNewRedBlackTree(String treeName, String balanceKey)}を実装した。
これは、第一引数{\tt treeName}で受け取った名前の、第二引数{\tt balanceKey}とペアになる属性値でバランスを取るRed Black Treeを構築する。

またこれ以降の説明で使用するbalanceKeyは、Red Black Jungle Treeを作成する時に設定したkey、BalanceValueは属性名 BalanceKeyとペアの属性値のことである。

\section{Red Black Jungle Treeの編集}
Red Black Jungle Treeへノードの追加を行う際は、追加するノードに、木のバランスを取るために必要な属性名 BalanceKeyとそのペアの属性値が必要になる。
しかし、JungleTreeEditorには、ノードと値を同時に追加するAPIは存在しなかったため、新しく実装した。
また、Red Black Jungle Treeにおいて、特定の属性名と属性値のペアを持つノードを削除するAPIも同時に実装した。
表\ref{NewEditorAPI}に新しく実装したAPIを記述する。

\begin{table}[htb]
\begin{center}
\caption{新たにJungle Tree Editorに定義したAPI}
\begin{tabular}{|p{15em}|p{24em}|}        \hline
{\tt Either<Error, JungleTreeEditor> addNewChildAndPutAttribute(NodePath path, int pos, String key, ByteBuffer value)} & pathで指定した位置にあるノードのpos番目に、属性名 keyと属性値 valueの組を持つノードを追加する。\\ \hline
{\tt Either<Error, JungleTreeEditor> deleteChildAt(String Key, ByteBuffer value)} & 木から特定の属性名 keyと属性名 valueを持っているノード検索し、削除する。\\ \hline
\end{tabular}
\label{NewEditorAPI}
\end{center}
\end{table}


Red Black Jungle Tree Editorは、既存のJungle Tree EditorとくらべてAPIの使い方が異なる。
具体的にはaddNewChildAtでPathが使われなかったりする。
表\ref{EditorDifference}にDefault Jungle Tree EditorとRed Black Jungle Tree EditorのAPIの使い方の違いを記述する。

\begin{table}[htb]
\begin{center}
\caption{Red Black Jungle TreeとDefault Jungle TreeのAPIの違い}
\begin{tabular}{|p{15em}|p{24em}|}        \hline
{\tt  Either<Error, JungleTreeEditor> addNewChildAt(NodePath path, int pos)} & pathとposは使用せず、属性名 balanceKey 属性値 "Default Value"を持ったノードを、Red Black Treeの挿入アルゴリズムに則って挿入し、バランスを取る。 \\ \hline
{\tt  Either<Error, JungleTreeEditor> addNewChildAt(NodePath path, int pos, String key, String value)} & pathとposは使用せず、属性名 key 属性値 valueを持ったノードを、Red Black Treeの挿入アルゴリズムに則って挿入し、バランスを取る。 第二引数にBalanceKey以外の値を渡した場合、バランスが取れない為、ノードの挿入は失敗する。\\ \hline
{\tt  Either<Error, JungleTreeEditor> replaceNewRootNode()} &  赤黒木は、新しくルートを追加する意味が無いので使用しない。実行した場合エラーを返す。\\ \hline
{\tt  Either<Error, JungleTreeEditor> moveChild(NodePath path, int childNum, String move)} &  ノードを動かすと木のバランスが崩れるため使用しない。実行した場合エラーを返す。 \\ \hline
\end{tabular}
\label{EditorDifference}
\end{center}
\end{table}



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

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

Jungle Red Black Treeのバランスは、データ挿入時の状態によって、次の5パターンに分けられる。

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

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


\subsection{データ挿入時のバランス ケース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}


\subsection{データ挿入時のバランス ケース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を新しくノードinsとして再帰的に木のバランスを行う。
この変更は最悪の場合ルートまで続く。

\subsection{データ挿入時のバランス ケース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}


\subsection{データ挿入時のバランス ケース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{Jungle Red Black Treeのノード削除}
Jungle Red Black Treeのノード削除は、以下の手順で行われる。

\begin{enumerate}
\item 削除を行うノードを検索する。
\item ノードに子が無い場合削除を行う。 
\item 片側に部分木(子ノード)がある場合、ノードを削除した後、部分木のルートを昇格させる。
\item 両側に部分木(子ノード)がある場合は、左部分木の最大の値を持つノードの値を取得し、削除を行うノードと同じ色に変更した後、置換する。
\item 昇格させたノードを削除する(ここで削除させるノードは部分木の最大値であるため、子ノードは1つ以下、つまり削除の手順2・3どちらかの手順で削除できる)。
\item 削除したノードから、木のバランスを取りながら、ルートまでの経路の複製を行う。その際Defaul Jungle Treeと同じように、変更が加えられないノードへは参照を行い過去の木と最大限共有を行う。
\end{enumerate}


RedBlackTreeのバランスは、ノード削除時の状態によって、次の6パターンに分けられる。
また。これ以降削除対象のノードと置換したノードを、ノードrepと記述する。
\subsection{データ削除時のバランス ケース1}

\begin{enumerdte}
\item 削除したノードが赤の場合。 
\end{enumerate}

上記の条件を満たしている場合、木の経路にある黒ノードの数は変らないためバランスを行う必要はない。

\begin{enumerate}
\item 削除したノードが黒。
\item 削除したノードの子ノードrepが赤。
\end{enumerate}

上記の条件を満たしている場合は、、ノードrepを置き換える際に赤から黒に色を変えることで木のバランスを取る。

以降、削除したノードの子の色が黒の場合のパターンについて記述する。
\subsection{データ削除時のバランス ケース2}
\begin{enumerate}
\item ノードrepがルートに置き換えられた。
\end{enumerate}

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

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

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

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

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

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

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

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

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

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

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

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


\subsection{データ削除時のバランス ケース7}
\begin{enumerate}
\item 削除したノードが黒。
\item ノードrepが黒。
\item ノードB・C・Dが黒。
\item ノードFの色が赤。
\end{enumerate}

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

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

Red Black Jungle Treeは、これらの処理を行うことで、データの挿入・削除時にこれらの処理を行うことで、木のバランスを保っている。
また、Red Black Jungle Treeは自身の木構造がIndexとしての機能を持つため、木の編集を行った際に別途Indexを構築する必要はない。

\section{Jungle Red Black Treeの検索}
Red Black Jungle Treeへの検索は、Red Black Jungle Tree Traverserを用いて行う。
Red Black Jungle Treeは、Indexを持たないため、Traverser.find(Query query, String balanceKey, String balanceValue)の第二・第三引数は、木を作成する時に設定したbalanceKey・属性名 balanceKeyとペアのbalanceValueを取る。
balanceKeyを使ったデータの検索は以下の手順で行う。

\begin{enumerate}
\item 現在のノードから、findの第二引数で取得した、属性名 BalanceKeyとペアになっている属性値 valueを取得する。
\item 1で取得した属性値 valueと、findの第三引数で取得したbalanceValueを比較する。
\item 比較の結果、大きかった場合、右に、小さかった場合左のノードに進む。
\item 同じ値を持つノードを発見するか、葉にたどり着くまで1~3を繰り返す。
\item 同じ値を持つノードを発見したら、そのノードを返す。
\item 葉までたどり着いた場合、その木は対応するノードを持っていないため
\item 5で取得したノードが、第一引数のqueryの条件に一致するか確かめる。
\item 一致する場合そのノードを返す。
\end{enumerate}

これらの実装により、Red Black Jungle Treeは、木の構築・検索の機能を持つ。