\chapter{既存のJungleとの変更点}
本章では、本研究で既存のJungleに行った大まかな変更概要を記述する。

\section{非破壊 Red Black Treeの実装}
JungleのIndexは、Java上で関数型プログラミングが行えるFunctional Java の非破壊 TreeMapを使って実装されていた。
しかし、Functional Javaは、処理が重く、実用的な性能ではなかったため、非破壊の TreeMap の実装を新しく行った。

\section{Indexの差分 Update}
Jungleの木は、Indexの更新をCommit時に Full Updateで行っている。
そのため、Commitを行うたび、O(n)のIndexのUpdateが入り、木の編集時大きなネックとなっていた。

前の木との差分だけIndexを更新する機能をJungleに追加することで、この問題を解決した。


\section{Differential Jungle Treeの実装}
Jungleの木の変更の手間は木の形によって異なる。
特に線形の木は、変更の手間がO(n)となってしまう。
線形の木をO(1)で変更するために、Jungleは、ルートノードを追加していくPushPopの機能を持つ
しかし、PushPopは、木の並びが逆順になってしまう。
なので、正順の木を構築する際には使用できない。
その問題を解決するために、Differential Jungle Treeの実装を行った。
Differential Jungle Treeは、木のバージョンごとに、自身の末尾のノードを保持する。

Differential Jungle Treeの木の編集は、Differential Jungle Tree Editor を使って行う。
編集時、Differential Jungle Tree Editor は、自身が保持しているSub Treeに対して、破壊的な編集を行う。
そして commit 時に、構築した Sub Tree を末尾ノードに Append することで木の編集を行う。
また、データの検索時は、自身が保持している末尾ノード以下のSub Treeを検索対象から除外することで、木構造の版管理を行っている。

\section{Red Black Jungle Tree}
Default Jungle Treeにおいて、Indexの更新は大きな手間となっている。
Indexに使用する属性名が1種類で、木構造の形がデータを表現していない場合、Jungle Tree自身をIndexとしたほうが、効率的に木構造を構築できる。
そこで、Red Black Treeの性質を組み込んだRed Black Jungle Treeの実装を行った。
Red Black Jungle Tree は、生成時に木のバランスを取る際に使用する属性名(Balance Key)を指定する。
ノードの挿入・削除時、Balance Keyを用いて木のバランスを取る・

Red Black Jungle Tree の木の編集は、Red Black Jungle Tree Editorを用いて行う。
ノードの挿入時に、木のバランスを取るための属性値が必要になるため、ノードと値の挿入を同時に行うAPIを実装した。

Red Black Jungle Treeの検索は、Balance Key を用いた検索は極めて高速に行える。
しかし用いなかった場合は、全探索を行うためO(n)になってしまう。