\chapter{Red Black Jungle Tree}
Default Jungle Treeにおいて、Indexの更新は大きな手間となっている。
Indexに使用する属性名が1種類で、木構造の形がデータを表現していない場合、Jungle Tree自身をIndexとしたほうが、効率的に木構造を変更できる。
そこで、Red Black Treeの性質を組み込んだRed Black Jungle Treeの実装を行った。
Red Black Jungle Tree は、木にノードの削除・追加を行った際、前述した、非破壊 Tree Map のバランスと同じアルゴリズムで木のバランスを取る。

\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{NodePath の拡張}
Red Black Jungle Treeは、ノードを追加・削除するたびに木のバランスが行われ、各ノードの Path が変わってしまう。
その為、数字を使った NodePath では、編集を加える際、編集対象のノードの Path をいちいち調べる必要がある。
その問題を解決するために、NodePath を拡張した RedBlackTreeNodePath を作成し 属性名 BalanceKey 属性値 valueのペアでノードを指定できるようにした。
RedBlackTreeNodePathは、引数にString型のBalanceKeyとByteBuffer型のBalanceValueを取る。

\section{Red Black Jungle Treeの編集}

Red Black Jungle Treeへノードの追加を行う際は、追加するノードに、木のバランスを取るために必要な属性名 BalanceKeyとそのペアの属性値 BalanceValue が必要になる。
しかし、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}


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{16em}|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> 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";
JungleTree tree = jungle.createNewRedBlackTree("TreeName", balanceKey)
JungleTreeEditor editor = tree.getJungleTreeEditor();
NodePath path = new RedBlackTreeNodePath();
ByteBuffer balanceValue = ByteBuffer.wrap(("Elphelt").getBytes());
Either<Error, JungleTreeEditor> either = editor.addNewChildAndPutAttribute(path, 0, balanceKey, balanceValue);
if (either.isA())  return either.a();
editor = either.b();
NodePath rbtPath = new RedBlackTreeNodePath(balanceKey,balanceValue));
String key = "key";
ByteBuffer value = ByteBuffer.wrap(("value").getBytes())
Either<Error, JungleTreeEditor> either = editor.putAttribute(rbtPath, key, testPutValue);
if (either.isA())  return either.a();
editor = either.b();
either = editor.success();
\end{lstlisting}


ソースコード\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}

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 は、これらの実装により、木構造の構築・検索を行える。