\chapter{Red Black Jungle Tree}
Jungle は木に編集を加えた際、ルートから編集を行う位置までのノードをコピーする。
その為、木の編集の手間は木の大きさにも依存している。
バランスの取れた木構造を構築することで、編集の手間をn(logN)にすることは可能だが、
Default Jungle Tree の場合、ユーザーが Path を用いて、バランスを取りながら木を構築する必要がある。
しかし、ユーザーが全ての木構造の形を把握し、バランスの取れた木を構築するのは困難である。
そこで、自動で木のバランスを取り、最適な形の木構造を構築する機能を持つ Red Black Jungle Tree に実装した。
バランスは、木の生成時に特定の {\tt Balance Key} 決定し、それを使って行う。
木のバランスを取るアルゴリズムは、前述した非破壊 TreeMap と同じものを使用する。

しかし、木の編集を加えた際、木がどのようにバランスを取るか予想するのは困難であるため、木の構造で、組織構造等のデータを表現するのは難しい。
なので、この機能が使えるのは、木の構造自体がデータを表現していない場合に限る。

また、自身の木構造が、{\tt Balance Key} を使った Index と同じ働きを持つため、木の Commit 時に別途 Index を構築する必要が無い、といったメリットもある。


\section{Red Black Jungle Treeの作成}
Red Black Jungle Treeを作成するため、Jungle に新しい API を実装した(表\ref{createRedBlackTreeAPI})。

\begin{table}[htb]
\begin{center}
\caption{Jungleに新しく実装したAPI}
\begin{tabular}{|p{15em}|p{24em}|}        \hline
{\small {\tt createNewRedBlackTree(String treeName, String balanceKey)}} &{\small Jungleに新しく Red Black Jungle Tree を生成する。第一引数に木の名前、第二引数に木のバランスを取る時に使用する {\tt Blance Key} を受け取る。木の名前が重複した場合、生成に失敗しnullを返す。}     \\ \hline
\end{tabular}
\label{createRedBlackTreeAPI}
\end{center}
\end{table}

{\tt createNewRedBlackTree} を使用したサンプルコード\ref{createRedBlackTree}を記述する。

\begin{lstlisting}[frame=lrbt,numbers=left,label=createRedBlackTree,caption=Red Black Jungle Treeの生成]
Jungle jungle = new DefaultJungle(null, "hogehoge", new DefaultTraverser());
String treeName = "redBlackTree";
String balanceKey = "balanceKey";
JungleTree tree = jungle.createNewRedBlackTree(treeName,balanceKey);
\end{lstlisting}

サンプルコード\ref{createRedBlackTree}では、3行目で指定した {\tt balance Key} を用いて木のバランスを取る、Red Black Jungle Tree が構築される。

\section{NodePath の拡張}
Red Black Jungle Treeは、ノードを追加・削除するたびに木のバランスが行われ、各ノードの Path が変わってしまう。
その為、数字を使った NodePath では、編集を加える際、編集対象のノードの Path を毎回調べる必要がある。
その問題を解決するために、NodePath を拡張した Red Black Tree Node Path を作成し 属性名 BalanceKey 属性値 valueのペアでノードを指定できるようにした。
RedBlackTreeNodePathは、引数にString型のBalanceKeyとByteBuffer型のvalueを取る。
ソースコード\ref{createRedBlackNodePath}に、属性名 {\tt "balanceKey"} 属性値 {\tt value}を持つノードを指定する Red Black Tree Node Path を作成するサンプルを記述する。

\begin{lstlisting}[frame=lrbt,numbers=left,label=createRedBlackNodePath,caption=Red Black Tree Node Pathの生成]
String balanceKey = "balanceKey";
ByteBuffer value = ByteBuffer.wrap(("value").getBytes());
NodePath path = new RedBlackTreeNodePath(balanceKey,value);
\end{lstlisting}

\section{Red Black Jungle Treeの編集}

\begin{comment}
Red Black Jungle Treeへノードの追加を行う際は、追加するノードに、木のバランスを取るために必要な属性名 BalanceKey が必要になる。
しかし、JungleTreeEditorには、ノードと値を同時に追加するAPIは存在しなかったため、新しく実装した。
表\ref{NewEditorAPI}に新しく実装したAPIを記述する。

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

Red Black Jungle Tree Editorは、既存のJungle Tree EditorとくらべてAPIの使い方が異なる。
表\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{16em}|p{24em}|}        \hline
{\tt  Either<Error, JungleTreeEditor> addNewChildAt(NodePath path, int pos)} &前節に記述した Red Black Node Path を使用する。 Path 生成時に指定した、{\tt Key} と {\tt Value} の組のデータを持つノードを Red Black Treeの挿入アルゴリズムに則って挿入し、バランスを取る。また、 \\ \hline
{\tt  Either<Error, JungleTreeEditor> addNewChildAndPutAttribute (NodePath path, int pos, String key, ByteBuffer 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}

\newpage
Red Black Jungle Tree にノードを挿入するサンプルコードを記載する(ソースコード\ref{src:rbtEdit})。

\begin{lstlisting}[frame=lrbt,label=src:rbtEdit,caption=RedBlackJungleTreeの編集例,numbers=left]
String balanceKey = "balanceKey";
ByteBuffer value = ByteBuffer.wrap(("Elphelt").getBytes());
JungleTree tree = jungle.createNewRedBlackTree("TreeName", balanceKey)
JungleTreeEditor editor = tree.getJungleTreeEditor();
NodePath path = new RedBlackTreeNodePath(balanceKey,value));
Either<Error, JungleTreeEditor> either = editor.addNewChildAt(path,0);
if (either.isA())  return either.a();
editor = either.b();
either = editor.success();
\end{lstlisting}


ソースコード\ref{src:rbtEdit}の解説を以下に記す。

1 - 2行目で、挿入するノードが持つ 属性名 {\tt balanceKey} と属性値 {\tt value}を作成する。
3行目で、木の名前が{\tt "TreeName"} バランスを {\tt balanceKey} を使って行う Red Black Jungle Tree を作成する。
4行目で、Editorを取得し、5行目でPath作成している。
6行目で、Path で指定した属性名 {\tt balanceKey} 属性値 {\tt value} の組の値を持つノードを木に挿入している。
そして9行目で、今回行った変更を Commit して編集を終了している。


\begin{comment}
\begin{enumerate}
\item 木のバランスに使用するbalanceKeyを宣言する。
\item 1で宣言したbalanceKeyを使って、Red Black Jungle Treeを{\tt TreeName}という名前で作成する。
\item 2で作成した木からEditorを取得する。
\item 木の編集に使用するPathを作成する。
\item 木にノードを値を挿入する際、属性名 balanceKeyとペアになる属性値 balanceValueを作成する。
\item 木に1・5で作成した属性名 属性値のペアの値を持つノードを追加し、木のバランスを取る。
\item 編集が成功したかを調べ、失敗していた場合エラーを返す。
\item 成功していた場合{\tt either}から、編集後の木を持つEditorを取得する。
\item 6で追加したノードを指し示すNodePathを作成する(属性名 balanceKey 属性値 balanceValueを持つノード)。
\item ノードに追加する属性値 keyを宣言する。
\item ノードに追加する属性名 valueを宣言する。
\item 属性名 balanceKey 属性値 balanceValueを持つノードに、10・11で作成した属性名key 属性値 valueを追加する。
\item 編集が成功したかを調べ、失敗していた場合エラーを返す
\item 成功していた場合{\tt either}から、編集後の木を持つEditorを取得する。
\item 編集を木にCommitする。
\end{enumerate}
\end{comment}

Red Black Jungle Tree は、木の編集時 Index を更新しないので、Default Jungle Tree より高速に木の変更を行える。


\section{Jungle Red Black Treeの検索}
Red Black Jungle Treeへの検索は、Red Black Jungle Tree Interface Traverser が提供しているAPIを用いて行う(表\ref{RedBlackTreeInterfaceTraverserApi})。

\begin{table}[htb]
\begin{center}
\caption{Red Black Jungle Tree Interface Traverser が提供しているAPI}
\begin{tabular}{|p{16em}|p{24em}|}        \hline
{\tt Iterator<TreeNode> find(Query query, String Balancekey, String BalanceValue)} & 第二引数と第三引数で指定した値を持ち、Queryの条件と一致するノードを返す。BalanceKey と BalanceValue を用いて木の二分探索を行うので、探索オーダーはO(Log n)である。また第二引数に、木の生成時指定した、Balance Key 以外を渡した場合、探索は失敗する。\\ \hline
{\tt Iterator<TreeNode> find(Query query)} & Query の条件と一致するノードを、木の全探索で検索する。探索オーダーはO(n)である。\\ \hline
\end{tabular}
\label{RedBlackTreeInterfaceTraverserApi}
\end{center}
\end{table}

Red Black Jungle Tree は、これらの実装により、木構造の構築・検索を行える。