\chapter{Red Black Jungle Tree}
Jungle は、木に編集を加えた際、編集を加えたノードと、経路にあるノードの複製を取る。
その為、木の編集の手間は、木の大きさにも依存している。
最適なバランスの取れた木構造を構築することで、編集の手間をn(logN)にすることは可能だが、
Default Jungle Tree だと、ユーザーが Path を用いて、木のバランスを取る必要ある。
しかし、ユーザーが全ての木構造の形を把握し、バランスの取れた木を構築するのは難しい。
そこで、自動で木のバランスを取り、最適な木構造を構築する機能を 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を取る。

\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の使い方の違いを記述する。
また、これらの API の返り値は全て \verb|Either<Error, JungleTreeEditor>| である。
表中では省略して記述する。

\begin{table}[htb]
\begin{center}
\caption{Red Black Jungle TreeとDefault Jungle TreeのAPIの違い}
\begin{tabular}{|p{16em}|p{24em}|}        \hline
{\tt addNewChildAt(NodePath path, int pos)} &前節に記述した Red Black Tree Node Path を使用する。 Path 生成時に指定した、{\tt Key} と {\tt Value} の組のデータを持つノードを Red Black Treeの挿入アルゴリズムに則って挿入し、バランスを取る。pos は使用しない。 \\ \hline
{\tt replaceNewRootNode()} &  赤黒木では使用しない。実行した場合エラーを返す。\\ \hline
{\tt 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";
String treeName = "treeName";
JungleTree tree = jungle.createNewRedBlackTree(treeName, balanceKey)
JungleTreeEditor editor = tree.getJungleTreeEditor();
ByteBuffer value = ByteBuffer.wrap(("Elphelt").getBytes());
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}

1 - 2行目で木の名前と、バランスを取る際に使用する Key を宣言している。
3 - 4行目で実際に Red Black Jungle Tree を作り、Editor を取得している。
5行目で実際にノードが持つ値を作り、6行目で、ノードを挿入する際に使用するRed Black Tree Node Path を作る。
7行目では実際に{\tt addNewChildAt} でノードを挿入している。

\begin{comment}
ソースコード\ref{src:rbtEdit}の解説を以下に記す。
\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 は、これらの実装により、木構造の構築・検索を行える。