\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 の更新処理を高速に行えるようにするため、
前の木との差分だけIndexを更新する機能を Jungle に追加した。


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

Differential Jungle 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を用いて木のバランスを取る。

木の探索に関してはBalanceKeyを用いた場合N(Logn)、そうでない場合はO(n)で行える。