\section{新しい非破壊TreeMap}\label{section:TreeMap}
Jungle内で実装しているIndexや、Nodeのattributeを、FunctionalJavaのTreeMapを用いて実装していた。
しかし、測定を行った結果FunctionalJavaのTreeMap部分がネックとなり性能が低下していたため、新しく非破壊的木構造のTreeMapの実装を行った。
自作TreeMapの構造は、データの検索、編集時の計算量から赤黒木を採用した。
赤黒木とは、二分木の一種で、次のような特徴がある
\begin{itemize}
\item 各ノードは赤か黒の色をもつ。
\item 根は必ず黒。
\item 葉は全て黒。
\item 赤のノードの子ノードは必ず黒。
\item 全てのノードから子孫の葉までの経路に含まれる黒ノードの数は全て同じ。
\end{itemize}

上記の条件より、根から葉までの最長経路が最短経路の2倍以上にならないため、極めて高速にデータの検索が行える。

TreeMapの実装を行う際に、赤と黒のノードをStatePatternを用いて、可読性を向上させた。
TreeMapを実装したことにより、Jungleがより高速に動作するようになった。