--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/differential.tex	Sat Jan 28 19:28:01 2017 +0900
@@ -0,0 +1,226 @@
+\chapter{Differential Jungle Tree}
+Jungleの木の変更の手間は木の形によって異なる。
+に線形の木は、変更の手間がO(n)となってしまう。
+線形の木をO(1)で変更するために、Jungleは、ルートノードを追加していくPushPopの機能を持つ。
+しかし、PushPopはルートノードを追加していくため、図\ref{fig:pushpop}のようにノードの並びが逆順になってしまうため、正順の木を構築する際は、PushPopを使用できない。
+
+\begin{figure}[htpb]
+\begin{center}
+\includegraphics[scale=0.3]{figures/PushPopDemerit.pdf}
+\caption{PushPopの問題点}
+\label{fig:pushpop}
+\end{center}
+\end{figure}
+
+その問題を解決するために、木の編集の手間をO(1)で、正順の木を構築できるDifferential Jungle Treeの実装を行った。
+Differential Jungle Treeは、木のバージョンごとに、自身の木の最後尾を表す末尾のノードを保持する。
+
+
+\section{Differential Tree Context}
+Jungleの木はTreeContextというオブジェクトに自身の木の情報を保持する。 
+表\ref{TreeContext}にTreeContextが保持するデータを記述する。
+
+\begin{table}[htb]
+\begin{center}
+\caption{TreeContextが保持している値}
+\begin{tabular}{|l|}        \hline
+{\tt } 自身のルートノード\\ \hline
+{\tt } 1つ前のversionのTreeContext\\ \hline
+{\tt } 編集のログ\\ \hline
+{\tt } 木のuuid    \\ \hline
+{\tt } 木の名前    \\ \hline
+{\tt } 木のversion    \\ \hline
+{\tt } 木の検索に使うTraverser    \\ \hline
+\end{tabular}           
+\label{TreeContext}
+\end{center}                  
+\end{table}  
+
+Differential Jungle Treeでは、現在の版の木構造の末尾ノード保持することが可能な DifferentialTreeContext 作成した。
+
+
+\section{Differential Jungle Treeの作成}
+Differential Jungle Treeを作成するためにJungleに、新しいAPIを実装した(表\ref{createDifferentialTree})。 
+\begin{table}[htb]
+\begin{center}
+\caption{Jungleに新しく実装したAPI}
+\begin{tabular}{|p{15em}|p{24em}|}        \hline
+{\tt  createNewDifferentialTree} {\tt (String treeName) } & Jungleに新しくDifferential Treeを生成する。木の名前が重複した場合、生成に失敗しnullを返す。     \\ \hline
+\end{tabular}
+\label{TreeContext}
+\end{center}
+\end{table}
+
+ソースコード\ref{newDifferentialTree}に新しいDifferential Jungle Treeを作成するサンプルコードを記載する。
+
+\begin{lstlisting}[frame=lrbt,numbers=left,label=newDifferentialTree]
+Jungle jungle = new DefaultJungle(null, "hogehoge", new DefaultTraverser()); // jungleの作成
+JungleTree tree = jungle.createNewDifferenceTree("df"); //Differential Treeの作成
+\end{lstlisting}
+
+
+
+
+\section{末尾ノードを使用した木の編集}
+Differential Jungle Treeの木の編集は、Differential Jungle Tree Editorを使用して行う。
+Differential Jungle Tree Editorは、Jungle Tree Editor インターフェースを実装しているため、使い方はDefault Jungle Tree Editorと同じである。
+
+処理の違いは、Default Jungle TreeのEditorは、木の複製を行い、過去の木を保持するのに対して、Differential Jungle TreeのEditor は、Sub Treeを保持しており、そのSub Treeに対して破壊的に編集を行う。
+そして、Commitを行う際に、構築したSub Treeを末尾ノードにAppendすることで木の編集を行う。
+そうすることで、木の複製を行う必要が無いため、木の変更の手間はO(1)で行える。
+
+また、Differential TreeはSub Treeに対する変更しか行えないため、一度Commitした木に対して変更は行えない。
+図\ref{fig:EditDifTree}にDifferential Jungle Treeの編集の流れを記述する。
+
+\begin{figure}[htpb]
+\begin{center}
+\includegraphics[scale=0.28]{figures/EditDifferencialTree.pdf}
+\caption{末尾ノードを使用した木の編集}
+\label{fig:EditDifTree}
+\end{center}
+\end{figure}
+
+\newpage
+\begin{enumerate}
+\item  木から{\tt getTreeEditor}でEditorを取得する。(このとき取得するEditorはSub Treeを持つ)。
+\item  SubTreeに対して{\tt addNewChild(<-1,0>)}を実行し、ノードの追加を行う。
+\item  Commitを行い、Treeの末尾ノードにSub TreeをAppendする。
+\end{enumerate}
+
+Sub Tree に最後に追加したノードが、新しい木の末尾ノードとなる。
+また、Differential TreeのIndexのアップデートは、Commit 時に Sub Treeの中身をIndexに追加するだけで良い。
+
+
+\section{Differential Jungle Treeの整合性}
+
+Differential Jungle Treeに対する変更が競合した場合、先にCommitを行った方の変更が適応される。
+末尾ノードへのAppendは、破壊的な変更であるため、Commit成功後に行う。
+そうすることで、編集が競合した際の整合性を保っている。
+
+
+また、Differential Jungle Treeは、木を破壊的に変更する。
+よって、過去の木を取得し、変更を加えた場合、末尾ノードに複数のSub TreeがAppendされてしまい、木の整合性が崩れてしまう。
+その問題を解決するため、Differential Jungle Treeでは、末尾ノードは一つしか子ノードを持つことができない。
+
+ソースコード\ref{src:Append}にSub TreeのAppend部分のコードを記述する。
+
+\begin{lstlisting}[frame=lrbt,label=src:Append,caption=Sub TreeのAppend部分のコード,numbers=left]
+Either<Error, TreeNode> appendSubTree(TreeNode subTreeRoot) {
+  TreeNode appendedNode = treeContext.getEndNode();
+  TreeNodeChildren children = appendedNode.getChildren();
+  if (children.size() != 0)
+    return DefaultEither.newA(APPEND_FAILD); 
+  return children.addNewChildAt(0, subTreeRoot);
+}
+\end{lstlisting}
+
+ソースコード\ref{src:Append}の解説を行う。
+
+\begin{enumerate}
+\item 関数{\tt appendSubTree}でSub TreeのAppendを行う。引数にSub Treeのルートを持つ。
+\item Differential Treeから末尾ノードを取得する。
+\item 末尾ノードからChildrenを取得する。
+\item 末尾ノードにSub TreeがすでにAppendされているか(子供を持っているか)を調べる。
+\item 他のSub TreeがAppendされている(今編集を行っているのが過去の木)場合、木のAppendは失敗するため、エラーを返す。
+\item そうでない場合、Sub Treeを末尾ノードにAppendする。
+\end{enumerate}
+
+このように、末尾ノードが複数の子を持つことを禁止することで、過去の木を取得した際の木の整合性を保証している。
+
+\section{Commit Operation}
+Default Jungle Treeでは、木に対しての変更は全てメインの木に対する変更であるため、Logに書き出された全ての変更を一回の Commit で行える。
+しかし、Differential Jungle Treeの変更は、Editorが保持しているsubTreeに対する変更を加えた後、 Commit 時にメインの木にAppendを行っている。
+そのため、適切なタイミングでCommitを行わないと、実際に行われた変更とズレが生じて、正しい木を構築できない。
+
+以下に、Logからの木の構築をする際に、一回のCommitでは適切なDifferential Treeを構築できない例を記す。
+\begin{lstlisting}[frame=lrbt,label=src:treelog,caption=適切な木を構築できないLogの例,numbers=left]
+1.[APPEND_CHILD:<-1>:pos:0]
+2[COMMIT]
+3.[APPEND_CHILD:<-1>:pos:0]
+4.[APPEND_CHILD:<-1,0>:pos:0]
+\end{lstlisting}
+
+大文字の英字はLogとして書き出された Operation の種類を表す。
+\verb|<>| により囲まれている数字は NodePath を示す。
+NodePath の表記以降は、ノードの position などの情報を表している。
+[COMMIT]は、実際の木を構築した際にCommitが行われたタイミングを表す。
+
+[COMMIT]のタイミングでCommitを行わず、全ての変更を加えた後にCommitを行った場合、Editor 内部の Sub Treeに、図\ref{fig:badDifTreeCreate}のような変更が加えられ、Append後、図\ref{fig:badDifTree}のような木が構築される。
+
+
+\begin{figure}[htpb]
+\begin{center}
+\includegraphics[scale=0.45]{figures/badDifTreeCreate.pdf}
+\caption{適切なタイミングでCommitを行わない木の復元の流れ}
+\label{fig:badDifTreeCreate}
+\end{center}
+\end{figure}
+
+\begin{figure}[htpb]
+\begin{center}
+\includegraphics[scale=0.45]{figures/BadDifTree.pdf}
+\caption{適切なタイミングでCommitを行わなかった木}
+\label{fig:badDifTree}
+\end{center}
+\end{figure}
+
+\clearpage
+
+しかし、実際には、図\ref{fig:createGoodDifTree1}、図\ref{fig:createGoodDifTree2}のような変更が加えられる。
+以下に、適切に Commit を行った場合の木の編集の流れを記述する。
+
+\begin{figure}[htpb]
+\begin{center}
+\includegraphics[scale=0.45]{figures/goodDifTreeCreate1.pdf}
+\caption{適切なタイミングでCommitを行なう、木の復元の流れ(1回目のCommit前、Sub Tree)}
+\label{fig:createGoodDifTree1}
+\end{center}
+\end{figure}
+
+
+1. 木からEditorを取得し、Sub Treeのルートノードの0番目に子ノードを追加する。
+
+\vspace{0.15in}
+2. そして、Commitを行い、1で構築したSub Treeをメインの木にAppendする
+
+\begin{figure}[htpb]
+\begin{center}
+\includegraphics[scale=0.45]{figures/goodDifTreeCreate2.pdf}
+\caption{適切なタイミングでCommitを行なう、木の復元の流れ(2回目のCommit前、Sub Tree)}
+\label{fig:createGoodDifTree2}
+\end{center}
+\end{figure}
+
+3. 木からEditorを取得し、Sub Tree のルートノードの0番目に子ノードを追加する。
+
+\vspace{0.15in}
+4. 続いて、Sub Treeの{\tt <-1, 0>} 番目にあるノードの、0番目の子供にノードを追加する。
+
+\vspace{0.15in}
+5. 最後に2度目の Commit を行い、Sub Treeをメインの木にAppendする。
+
+\vspace{0.15in}
+
+結果、図\ref{fig:goodDifTree}のような木が構築される。
+
+\begin{figure}[htpb]
+\begin{center}
+\includegraphics[scale=0.45]{figures/goodDifTree.pdf}
+\caption{適切なタイミングでCommitを行なった木の変更。}
+\label{fig:goodDifTree}
+\end{center}
+\end{figure}
+
+このように、Logとして書き出されたTreeOperationから、適切な構造のDifferential Treeを復元するためには、木の構築時と同じタイミングでCommitを行う必要がある。
+そのため、Commitのタイミングを、Logとして書き出し、適切なタイミングでCommitを行えるようにした。
+
+
+
+
+\section{Differential Jungle Treeの検索}
+Differential Treeは、木を破壊的に編集する。
+そのため、過去の木から特定の値を持ったノードを取得する際、全てのノードを走破した場合その版の木には無いはずのノードが取得できてしまうことがある。
+そこで、その版の木が持つ末尾ノード以下のSub Treeを検索対象から除外する検索を実装した。
+
+Indexを使用した検索を行う場合、各版に対応したIndexがあるため、Default Treeと検索の方法は変わらない。
+

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/indexupdate.tex	Sat Jan 28 19:28:01 2017 +0900
@@ -0,0 +1,54 @@
+\chapter{Indexの差分Update}
+Jungleの木はIndexを持っており、木のCommit時に、Full Updateを行っている。
+そのため、Commitを行うたび、O(n)のIndexのUpdateが入り、木の編集時大きなネックとなっていた。
+なので、Indexの差分アップデートを実装した。
+
+\section{差分 Updateの実装}
+Jungleの木に編集を行う際、編集を行ったノードをリストに格納する。
+そして、Commit時にリストにあるノードと、そのノードまでの経路にあるノードに対して、IndexをのUpdateを行う。
+
+Indexの Update は、ノードの削除とノードの挿入の２つのプロセスで行われる。
+
+\section{Indexの中身の削除}
+IndexのUpdateを行う際、初めに木の編集後の木に存在しないノードをIndexから削除する。
+削除の対象は、変更を加えたノードと、ルートから変更を加えたノードまでの経路にあるノードである。
+ノードの削除は、以下の手順で行われる。
+
+\begin{enumerate}
+\item 編集を行ったノードのリストからノードを取得する。
+\item 取得したノードから、保持しているデータを扱うAttributesクラスを取得する。
+\item Attributesクラスから、ノードが保持している属性名のIteratorを取得する。
+\item Attributesクラスから、3で取得した属性名とペアの属性値を取得する。
+\item 3・4で取得した属性名・属性値を使ってIndexから自身を削除する。
+\item 自身と子供のペアを ParentIndex から削除する。
+\item ParentIndex から親を取得する。
+\item 2 - 7をルートノードにたどり着くか、ParentIndexから親を取得できなくなるまで続ける。
+\item 1 - 8をリストからノードが無くなるまで続ける。
+\end{enumerate}
+
+
+\section{Indexへのノードの挿入}
+Indexから不要なノードを削除した後は、木に編集を加えた際に新しく作られたノードをIndexに挿入する。
+ノードの挿入は、以下の手順で行われる。
+
+\begin{enumerate}
+\item 木からルートノードを取得する。 
+\item 取得したノードがIndexに登録されているかを調べる。
+\item 登録されている場合、そのノード以下のSub Treeは、全てIndexに登録されているので、次のノードに移動する。
+\item 登録されていなかった場合、取得したノードから保持しているデータを扱うAttributesクラスと、子供を扱うChildrenクラスを取得する。
+\item Attributesクラスから、ノードが保持している属性名のIteratorを取得する。
+\item Attributesクラスから、5で取得した属性名とペアの属性値を取得する。
+\item 5・6で取得した属性名・属性値を使ってIndexに自身を登録する。
+\item 2で取得したChildrenクラスから自身の子ノードを取得する。
+\item 自身と取得した子ノードをParent Index に登録する。
+\item 全てのノードを挿入するまで 2 - 9 を繰り返す。
+\end{enumerate}
+
+
+\section{Full Update との使い分け}
+Indexの差分Updateは、不要なノードの削除と新しく木に追加されたノードの挿入を行っているため、1ノードに対する処理は Full Updateより大きい。
+そのため、少ない編集後の Commit は、差分Updateの方が高速に行えるが、多くの編集を行った後の Commitだと、Full Updateの方が高速に動作する。
+なので、木の編集回数によって、Indexの更新方法を変更する必要がある。
+
+
+\newpage

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/jungle.tex	Sat Jan 28 19:28:01 2017 +0900
@@ -0,0 +1,373 @@
+\chapter{非破壊的木構造データベースJungle}
+Jungleは、当研究室が開発を行っているデータベースで、Javaを用いて実装されている。
+Jungleは名前付きの複数の木の集合からなり、木は複数のノードの集合で出来ている。
+ノードは自身の子のリストと属性名と属性値の組でデータを持ち、データベースのレコードに相当する。
+通常のレコードと異なるのは、ノードに子供となる複数のノードが付くところである。
+Jungleでは、親から子への片方向の参照しか持たない。
+
+通常のRDBと異なり、Jungleは木構造をそのまま読み込むことができる。例えば、XMLやJsonで記述された構造を、データベースを設計することなく読み込むことが可能である。
+この木を、そのままデータベースとして使用することも可能である。しかし、木の変更の手間は木の構造に依存する。
+%特に非破壊木構造を採用しているJungleでは木構造の変更にo(1)からo(n)の様々な選択肢がある。つまり、アプリケーションに合わせて木を設計しない限り、
+特に非破壊木構造を採用しているJungleでは、木構造の変更の手間はO(1)からO(n)となりえる。つまり、アプリケーションに合わせて木を設計しない限り、
+十分な性能を出すことはできない。逆に、正しい木の設計を行えば高速な処理が可能である。
+
+Jungleは基本的にon memoryで使用することを考えており、一度、木のルートを取得すれば、その上で木構造として自由にアクセスして良い。
+Jungleは分散データベースを構成するように設計されており、分散ノード間の通信は木の変更のログを交換することによって行われる。
+持続性のある分散ノードを用いることでJungleの持続性を保証することができる。本論文では基本的に分散実装部分ではなく on memory DBの
+部分について考察する。
+本章ではまず破壊的木構造と、非破壊的木構造の説明をし、その後Jungleの提供しているAPIについて述べる。
+
+\section{破壊的木構造}
+破壊的木構造の編集は, 木構造で保持しているデータを直接書き換えることで行う。
+図\ref{fig:destractive}は破壊的木構造のにおけるデータ編集を表している。
+
+\begin{figure}[htpb]
+  \begin{center}
+    \includegraphics[scale=0.7]{figures/destructive_tree.pdf}
+    \caption{破壊的木構造の編集}
+    \label{fig:destractive}
+  \end{center}
+\end{figure}
+
+破壊的木構造は、編集を行う際に木のロックを掛ける必要がある。
+この時、データを受け取ろうと木を走査するスレッドは書き換えの終了を待つ必要があり、
+閲覧者がいる場合は木の走査が終わるまで書き換えを待たなければならない。
+
+\section{非破壊的木構造}
+データの編集を一度生成した木を上書きせず、ルートから編集を行うノードまでコピーを行い新しく木構造を構築し、そのルートをアトミックに入れ替えることで行う(図\ref{fig:nondestractive})。
+その際、編集に関係ないノードは参照を行い、複製元の木と共有する(図\ref{fig:nondestractive}の例ではノード1・3・4は編集に関係ないためノードAから参照を行い、過去の木と共有を行っている)。
+
+\begin{figure}[htpb]
+  \begin{center}
+    \includegraphics[scale=0.7]{figures/non_destructive_tree.pdf}
+    \caption{非破壊的木構造の編集}
+    \label{fig:nondestractive}
+  \end{center}
+\end{figure}
+
+非破壊的木構造においてデータのロックが必要となる部分は、木のコピーを作り終えた後に
+ルートノードを更新するときだけである。
+データ編集を行っている間ロックが必要な破壊的木構造に比べ、編集中においてもデータの読み込みが可能であるが、
+書き込み時の手間は大きくなる。
+
+\begin{figure}[htpb]
+  \begin{center}
+    \includegraphics[scale=0.7]{figures/non_destructive_merit.pdf}
+    \caption{非破壊的木構造による利点}
+    \label{fig:nondestractive_merit}
+  \end{center}
+\end{figure}
+
+\section{NodePath}
+Jungleでは、木のノードの位置を{\tt NodePath}クラスを使って表す。
+{\tt NodePath}クラスはルートノードからスタートし、対象のノードまでの経路を数字を用いて指し示す。また、ルートノードは例外として-1と表記される。
+{\tt NodePath}クラスを用いて{\tt< -1,1,2,3>}を表している際の例を図\ref{NodePath}に記す。
+
+\begin{figure}[htpb]
+\begin{center}
+\includegraphics[scale=0.7]{figures/nodePath.pdf}
+\caption{NodePath}
+\label{NodePath}
+\end{center}
+\end{figure}
+
+\section{Either}
+Jungleは、失敗する可能性のある関数では返り値を{ \tt Either<A、B>}に包んで返す。
+AにはのError、Bには処理に成功した際の返り値の型が入る。
+Eitherは、AかBどちらかの値しか持たない。
+以下にEitherクラスが提供しているAPI(表\ref{EitherAPI})を記す。
+\begin{table}[htb]
+\begin{center}
+\caption{Eitherに実装されているAPI}
+\begin{tabular}{|p{15em}|p{24em}|}        \hline
+{\tt boolean isA()} & EitherがAを持っているかどうかを調べる。持っている場合trueを返す。\\ \hline
+{\tt boolean isB()} & EitherがBを持っているかどうかを調べる。持っている場合trueを返す。\\ \hline
+{\tt A a()} & Aの値を取得する。\\ \hline
+{\tt B b()} & Bの値を取得する。\\ \hline
+\end{tabular}
+\label{EitherAPI}
+\end{center}
+\end{table}
+
+{\tt Either<A、B>}は、{\tt isA()}を用いて関数が{\tt Error}を返していないかを調べる。
+{\tt Error}でない場合は{\tt b()}で関数の返り値を取得する。
+
+
+\section{木の生成}
+初めにJungleにおける木の生成について述べる。
+Jungleは複数の木構造を、名前を利用して作成・編集・削除を行い管理している。
+以下にJungleクラスが提供している木の生成・管理を行うAPI(表\ref{jungleAPI})を記す。
+
+\begin{table}[htb]
+  \begin{center}
+  \caption{Jungleに実装されているAPI}
+    \begin{tabular}{|p{15em}|p{24em}|}        \hline
+      {\tt JungleTree createNewTree(String treeName) } & Jungleに新しく木を生成する。木の名前が重複した場合、生成に失敗しnullを返す。     \\ \hline
+      {\tt JungleTree getTreeByName(String treeName)}  & JungleからtreeNameと名前が一致するtreeを取得する。名前が一致するTreeがない場合取得は失敗しnullを返す       \\ \hline
+    \end{tabular}
+    \label{jungleAPI}
+  \end{center}
+\end{table}
+
+
+\section{JungleTree}
+Jungleは複数の木の集合で出来ている。
+ユーザーは、この木に対して検索や編集を行う。
+以下にJungleTreeクラスが提供しているAPI(表\ref{JungleTreeAPI})を記す
+\begin{table}[htb]
+\begin{center}
+\caption{JungleTreeに実装されているAPI}
+\begin{tabular}{|p{15em}|p{24em}|}        \hline
+{\tt TreeNode getRootNode()} &木のルートノードを取得する。   \\ \hline
+{\tt long revision()} & 木のバーションを取得する。初めは0から始まり、木への変更がCommitされる度に1上昇する。 \\ \hline
+{\tt JungleTreeEditor getJungleTreeEditor()} & 木へ変更を加えるEditorを取得する。\\ \hline
+{\tt Either<Error, JungleTree> getOldTree(long revision)} & 引数で指定したint revisionに等しいバージョンの木を取得する。 \\ \hline
+{\tt InterfaceTraverser getTraverser()} & 木の検索を行うTraverserを取得する。 \\ \hline
+{\tt Either<Error, TreeNode> getNodeOfPath(NodePath path)} & {\tt NodePathで指定した位置と値なるノードを取得する。}  \\ \hline
+{\tt NodePath getNodePath(TreeNode node)} & 引数で渡したノードの位置を表す{\tt NodePath}を返す。\\ \hline
+\end{tabular}
+\label{JungleTreeAPI}
+\end{center}
+\end{table}
+
+
+\section{TreeNode}
+Jungleの木構造は、複数のノードの集合で出来ている。
+ノードは、自身の子のListと属性名と属性値の組でデータを持つ。
+ノードに対するアクセスは、表\ref{TreeNodeAPI}に記述されているAPIを用いて行われる。
+
+\begin{table}[htb]
+  \begin{center}
+    \caption{TreeNodeに実装されているAPI}
+    \begin{tabular}{|p{15em}|p{24em}|}                                  \hline
+      {\tt Children getChildren()} & ノードの子供を扱うChildrenオブジェクトを返す。\\ \hline
+      {\tt Attribute getAttribute()} &ノードが保持しているデータを扱うAttribteオブジェクトを返す。    \\ \hline
+    \end{tabular}
+    \label{TreeNodeAPI}
+  \end{center}
+\end{table}
+
+Childrenクラスは表\ref{Children}に記述されたAPIを、Attributeクラスは表\ref{Attribute}に記述されたAPIを提供する。
+これらを利用しノードが保持している値や、子供にアクセスする。
+\begin{table}[htbH]
+  \begin{center}
+    \caption{Childrenに実装されているAPI}
+    \begin{tabular}{|p{15em}|p{24em}|}                                  \hline
+      {\tt int size()}  &  子供の数を返す。\\ \hline
+      {\tt <Either Error,TreeNode> at(int num)} &ノードが持つ子供の中から、 変数{\tt num}で指定された位置にある子ノードを返す。   \\ \hline
+    \end{tabular}
+  \label{Children}
+  \end{center}
+\end{table}
+
+
+
+\begin{table}[htbH]
+  \begin{center}
+    \caption{Attributeに実装されているAPI}
+    \begin{tabular}{|p{15em}|p{24em}|} \hline
+      {\tt ByteBuffer get(String key)}   &ノードが持つ値から、属性名 {\tt key}とペアの属性値を{\tt ByteBuffer}型で返す。 \\ \hline
+      {\tt String getString(String key)} &ノードが持つ値から、属性名 {\tt key} とペアの属性値を{\tt String}型で返す。 \\ \hline
+    \end{tabular}
+  \label{Attribute}
+  \end{center}
+\end{table}
+
+\newpage
+以下にルートノードの2番目の子供から、属性名 {\tt name}とペアになっている属性値を取得するサンプルコードを記述する。
+\begin{lstlisting}[frame=lrbt,numbers=left,label=getAttributeCode]
+JungleTree tree = jungle.getTreeByName("TreeName");
+TreeNode root = tree.getRootNode();
+Children children = root.getChildren();
+Either<Error,TreeNode> either = children.at(2);
+if (either.isA()) 
+  return either.a();
+TreeNode child = either.b();
+Attribute attribute = child.getAttribute();
+String value = attribute.getString("name");
+\end{lstlisting}
+
+\begin{enumerate}
+  \item Jungleから名前が{\tt "TreeName"}の木を取得する。 
+  \item 取得した木のルートノードを取得する。
+  \item 木のルートノードから{\tt Children}を取得する。
+  \item 3で取得した{\tt Children}から2番目の子供を取得する。
+  \item 関数{\tt Either.isA()}を用いて、2番目の子供が取得できたかを調べる。
+  \item 取得できていなかった場合{\tt Either.a()}でErrorを返す。
+  \item 取得に成功していた場合、{\tt Either.b()}で子ノードを取得する。
+  \item 取得した子ノードから{\tt Attribute}クラスを取得する。
+  \item 取得した{\tt attribute}から属性名 {\tt name}とペアの属性値を取得する。
+\end{enumerate}
+
+\section{木の編集API}
+Jungleの木の編集は{\tt Default Jungle Tree Editor}クラスを用いて行われる。
+{\tt Default Jungle Tree Editor}クラスは、木に対する編集を行うAPIが定義されているJungle Tree Editorインターフェースを実装している。
+表\ref{editor}にJungle Tree Editorインターフェースに定義されているAPIを記述する。
+
+\begin{table}[htb]
+  \begin{center}
+    \caption{Editorに実装されているAPI}
+    \begin{tabular}{|p{15em}|p{24em}|}        \hline
+      {\tt Either<Error, JungleTreeEditor> addNewChildAt( NodePath path,  int pos)} &
+      変数{\tt path}で指定した場所にあるノードの、変数{\tt pos}で指定した位置に子ノードを追加する\\ \hline
+      {\tt Either<Error, JungleTreeEditor> deleteChildAt( NodePath path,int pos)}      &
+      変数{\tt path}で指定した場所にあるノードの、変数{\tt pos}で指定した位置の子ノードを削除する。 \\ \hline
+      {\tt Either<Error, JungleTreeEditor> putAttribute( NodePath path,String key,ByteBuffer value)} &
+      変数{\tt path}で指定した場所にあるノードに、属性名 変数{\tt key} 属性値 変数{\tt value} のペアで値を挿入する。 \\ \hline
+      {\tt Either< Error, JungleTreeEditor> deleteAttribute( NodePath path,String key)}&
+      変数{\tt path}で指定した場所にあるノードが持つ、属性名 変数{\tt key}とペアで保存されている属性値を削除する。\\ \hline
+      {\tt Either<Error, JungleTreeEditor> moveChild( NodePath path,int num,String move)} &
+      変数{\tt path}で指定した場所にあるノードの、変数{\tt num}で指定された位置の子供を変数{\tt move}の方向に移動させる。 \\ \hline
+      {\tt Either<Error, JungleTreeEditor> pushPop()} &
+      ルートノードの上に新しいルートノードを追加する。線形の木を作る際に使用することで木の変更の手間をO(n)からO(1)にできる。\\ \hline
+      {\tt Either<Error, JungleTreeEditor> success()}  &
+      木へ行った変更をコミットする。自分が編集を行っていた間に、他のJungleTreeEditorクラスによって木が更新されていた場合、コミットは失敗する。 \\ \hline
+    \end{tabular}
+  \label{editor}
+  \end{center}
+\end{table}
+
+
+
+編集後に返される{\tt JungleTreeEditor}クラスは、編集後の木構造を保持しているため、編集前の木構造を保持している{\tt JungleTreeEditor}クラスとは別のオブジェクトである。
+編集を行った後は、関数{\tt editor.success()}で今までの編集をコミットすることができる。他の{\tt JungleTreeEditor}クラスによって木が更新されていた場合はコミットは失敗し、{\tt success()}は{\tt Error}を返す。
+その場合は、木の編集を最初からやり直す必要がある。
+
+以下に{\tt JungleTreeEditor}クラスを用いて、木の編集を行うサンプルコードを記述する。
+
+\begin{lstlisting}[frame=lrbt,numbers=left,label=editorCode]
+JungleTreeEditor editor = tree.getTreeEditor();
+DefaultNodePath editNodePath = new DefaultNodePath();
+Either<Error, JungleTreeEditor> either = editor.addNewChildAt(editNodePath, 0);
+if (either.isA()) 
+  return either.a();
+editor = either.b();
+editor.success();
+\end{lstlisting}
+
+\begin{enumerate}
+  \item 関数{\tt tree.getEditor()}で編集を行う木から、{\tt JungleTreeEditor}クラスを取得する。 
+  \item 次に変更するノードの場所を示す、{\tt NodePath}クラスを作成する。
+  \item 関数{\tt editor.addNewChildAt()}を用いて、変数{\tt path}で指定したノードの子供の0番目に子ノードを追加する。
+  \item 返り値の変数{\tt either}が{\tt Error}クラスを保持していないか(編集に失敗していないか)を確認する。
+  \item {\tt Error}クラスを保持していた場合{\tt Either.a()}でErrorを返す。
+  \item 編集に成功していた場合、編集後木を持った、{\tt JungleTreeEditor}クラスを取得する。
+  \item 取得した{\tt JungleTreeEditor}クラスを用いて木の変更をコミットする。
+\end{enumerate}
+
+また、木に対して行われた変更は、Logとして書き出される。
+これらのAPIにより、Jungleは木構造を格納、編集する機能を持っている。
+
+
+\section{検索APIの実装}
+これまでに紹介したAPIにより、Jungleは木構造を構築できるようになった。
+しかし、木に問い合わせを行う検索APIが実装されていなかったため、属性名 {\tt key} 属性値 {\tt value}の組で検索を行うAPIの実装を、木の走査を行う{\tt Traverser}クラス内に、lambda式を用いて行った。
+以下に検索を行う関数{\tt find}の定義を記述する。
+\begin{lstlisting}[frame=lrbt,label=query,numbers=left]
+public Iterator<TreeNode> find(Query query, String key, String searchValue);
+\end{lstlisting}
+
+関数{\tt find}は、第一引数には、探索の条件を記述する関数{\tt boolean comdition(TreeNode)}を定義した{\tt Query}を。
+第二、第三引数には、Indexを用いた絞込に使用する{\tt String key、String value}を取り、条件に一致したノードの{\tt Iterator}を返す。
+{\tt 関数find}の使用例を以下に記す
+
+\begin{lstlisting}[frame=lrbt,label=find,numbers=left]
+InterfaceTraverser traverser = tree.getTraverser(true);
+Iterator<TreeNode> resultNodeIterator = traverser.find((TreeNode node) -> {
+    String personId = node.getAttributes().getString("name");
+      if (personId == null) return false;
+        return personId.equals("kanagawa");
+}, "belong", "ryukyu");
+\end{lstlisting}
+
+
+上記コードについて解説する。
+\begin{enumerate}
+  \item 木の走査を行う{\tt Traverser}クラスを取得する。
+
+  \item Indexから{\tt find}の第2、第3引数である、属性名 {\tt belong}、属性値 {\tt ryukyu}の組のデータを持つノードを取得し、Queryに渡す(ノードの絞込を行う)。
+
+  \item 引数のノードから関数{\tt getAttributes().getString("name")}で属性名 {\tt name}とペアになっている属性値を取得する。
+  
+  \item 属性値が{\tt null}だった場合、このノードには属性名が{\tt name}の組のデータは存在しないので、{\tt false}を返し次のノードの評価を行う。
+
+  \item 属性値が{\tt null}でなかった場合、{\tt kanagawa}と一致するかどうかを調べ結果を返す。
+
+\end{enumerate}
+
+このコードの結果として、{\tt ryukyu}に所属する、名前が{\tt kanagawa}のデータが入ったノードが取得できる。
+
+
+\section{Indexの実装}
+Jungleには、検索の際に使用するIndexが無かったため、実装を行った。
+Jungleは、非破壊的木構造というデータ構造上、過去の版の木構造を全て保持している。
+よって、全ての版に独立したIndexが必要となるため、前の版のIndexを破壊すること無く、Indexを更新する必要があった。
+既存のTreeMapでは、一度Indexの複製を行ない、その後更新する必要があったため、Indexの更新オーダーがO(n)となっていた。
+その問題を解決するため、非破壊TreeMapを自作し、それを用いてIndexの実装を行った。
+このTreeMapは、Jungleと同じようにルートから変更を加えたノードまでの経路の複製を行い、データの更新を行った際、前の版と最大限データを共有した新しいTreeMapを作成する。
+Jungleとの違いは、木の回転処理が入ることである。
+これにより複数の版全てに対応したIndexをサポートすることが可能になった。
+以下にJungleにおけるIndexの型を記述する
+
+\begin{lstlisting}[frame=lrbt,label=index,numbers=left]
+TreeMap<String key,TreeMap<String attribute,List<TreeNode> node> index> indexMap
+\end{lstlisting}
+
+JungleのIndexは{\tt IndexMap}内に保持されている。
+属性名で{\tt IndexMap}に{\tt get}を行うと、対応したIndexが取得できる。
+取得したIndexに属性値で{\tt get}を行うと、ノードのリストが返ってくる。
+以下にIndexから属性名 name 属性値 kanagawaのデータを持つ、ノードのIteratorを取得するサンプルコードを記述する。
+
+\begin{lstlisting}[frame=lrbt,label=find,numbers=left]
+Optional<TreeMap<String, List<TreeNode>>> indexOp = indexMap.get("name");
+if (!indexOp.isPresent())
+  return new NulIterator<TreeNode>();
+TreeMap<String, List<TreeNode>> index = indexOp.get();
+Optional<List<TreeNode>> nodeListOp = index.get("kanagawa");
+if (!nodeListOp.isPresent())
+  return new NulIterator<TreeNode>();
+return nodeListOp.get().iterator();
+\end{lstlisting}
+
+
+\begin{enumerate}
+\item {\tt indexMap}に、今回検索で使用する属性名 {\tt name}を使用して{\tt get("name")}を行う。すると属性名 {\tt name}に対応したIndexが、{\tt Optional}クラスで包まれて返ってくる。
+
+\item {\tt Optional}オブジェクトに対して、中身を保持しているか(属性名 {\tt name}に対応したIndexを木が持っているか)を調べる。
+
+\item 持っていなかった場合、空の{\tt Iterator}オブジェクトを返す。
+
+\item 持っていた場合、{\tt Optional}オブジェクトからIndexを取得する。
+
+\item 取得したIndexに、検索で使用する属性値{\tt kanagawa}で{\tt get()}を行う。すると、属性名 {\tt name} 属性値{\tt  kanagawa}の値を持つノードのリストが、{\tt Optional}クラスに包まれて返ってくる。
+
+\item {\tt Optional}オブジェクトに対して中身を保持しているか(属性名 {\tt name} 属性値 {\tt kanagawa}を持つノードを木が持っているか)を調べる。
+
+\item 持っていなかった場合、空の{\tt Iterator}オブジェクトを返す。
+
+\item 持っていた場合{\tt Optional}オブジェクトからノードリストの{\tt Iterator}を返す。
+
+\end{enumerate}
+
+JungleはこれらのAPIにより、木構造を格納、編集、検索する機能を持っている。
+
+\section{Log}
+Jungle は、 Editor を用いて木に編集を加える際、使用した API に応じて対応する NodeOperation を作成する。
+NodeOperation は NodePath とペアで扱わなければならず、このペアを TreeOperation という。
+Jungle によるデータの編集は TreeOperation が複数集まった単位で commit されていく.
+この TreeOperation の集まりを TreeOperationLog という。
+TreeOperationLogの仕様をソースコード\ref{src:treeoperationlog}に示す.
+\begin{lstlisting}[frame=lrbt,label=src:treeoperationlog,caption=TreeOperationLogの仕様,numbers=left]
+public interface TreeOperationLog extends Iterable<TreeOperation>
+{
+  public TreeOperationLog add(NodePath _p,NodeOperation _op);
+  public TreeOperationLog append(TreeOperationLog _log);
+  public int length();
+}
+\end{lstlisting}
+
+\verb|Iterable<TreeOperation>|を継承しているためIteratorによりTreeOperationを取り出せるようになっている。
+addやappendメソッドを使ってTreeOperationを積み上げていくことができる。
+
+
+\newpage

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/jungleUpdatePoint.tex	Sat Jan 28 19:28:01 2017 +0900
@@ -0,0 +1,40 @@
+\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)を指定する。
+
+Red Black Jungle Tree の木の編集は、Red Black Jungle Tree Editorを用いて行う。
+ノードの挿入時に、木のバランスを取るための属性値が必要になるため、ノードと値の挿入を同時に行うAPIを実装した。
+
+Red Black Jungle Treeの検索は、Balance Key を用いた検索は極めて高速に行える。
+しかし用いなかった場合は、全探索を行うためO(n)になってしまう。
+

--- a/master_paper.tex	Tue Jan 24 14:53:52 2017 +0900
+++ b/master_paper.tex	Sat Jan 28 19:28:01 2017 +0900
@@ -77,9 +77,12 @@
 
 %chapters
 \input{introduciton.tex}
-\input{chapter1.tex} % Jungleの説明
-\input{chapter2.tex} % 差分Treeの説明
-\input{chapter3.tex} % 赤黒木の説明
+\input{jungle.tex} % Jungleの説明
+\input{jungleUpdatePoint.tex} % 卒論との変更点
+\input{redBlackTree.tex}
+\input{indexupdate.tex} % Indexの差分アップデート
+\input{differential.tex} % 差分Treeの説明
+\input{redBlackJungleTree.tex} % 赤黒木の説明
 \input{chapter4.tex} % Jungle Tree Brower
 \input{chapter5.tex} % Rendering Engine
 \input{chapter6.tex} % 

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/redBlackJungleTree.tex	Sat Jan 28 19:28:01 2017 +0900
@@ -0,0 +1,95 @@
+\chapter{Red Black Jungle Tree}
+Default Jungle Treeにおいて、Indexの更新は大きな手間となっている。
+Indexに使用する属性名が1種類で、木構造の形がデータを表現していない場合、Jungle Tree自身をIndexとしたほうが、効率的に木構造を変更できる。
+そこで、ノードの挿入を行うと、指定した{\tt }Keyで木のバランスを取る、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を取る。
+そして作成したPathをEditorに渡すと、指定したBalanceKeyとBalanceValueの組の値を持つノードに編集を行う。
+
+\section{Red Black Jungle Treeの編集}
+
+Red Black Jungle Treeへノードの追加を行う際は、追加するノードに、木のバランスを取るために必要な属性名 BalanceKeyとそのペアの属性値が必要になる。
+しかし、JungleTreeEditorには、ノードと値を同時に追加するAPIは存在しなかったため、新しく実装した。
+また、Red Black Jungle Treeにおいて、特定の属性名と属性値のペアを持つノードを削除するAPIも同時に実装した。
+表\ref{NewEditorAPI}に新しく実装したAPIを記述する。
+
+\begin{table}[htb]
+\begin{center}
+\caption{新たにJungle Tree Editorに定義したAPI}
+\begin{tabular}{|p{15em}|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{15em}|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}
+
+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}
+
+
+\section{Jungle Red Black Treeの検索}
+Red Black Jungle Treeへの検索は、Red Black Jungle Tree Traverserを用いて行う。
+Red Black Jungle Treeは、Indexを持たないため、Traverser.find(Query query, String balanceKey, String balanceValue)の第二・第三引数は、木を作成する時に設定したbalanceKey・属性名 balanceKeyとペアのbalanceValueを取る。
+balanceKeyを使ったデータの検索は以下の手順で行う。
+
+\begin{enumerate}
+\item 現在のノードから、findの第二引数で取得した、属性名 BalanceKeyとペアになっている属性値 valueを取得する。
+\item 1で取得した属性値 valueと、findの第三引数で取得したbalanceValueを比較する。
+\item 比較の結果、大きかった場合、右に、小さかった場合左のノードに進む。
+\item 同じ値を持つノードを発見するか、葉にたどり着くまで1~3を繰り返す。
+\item 同じ値を持つノードを発見したら、そのノードを返す。
+\item 葉までたどり着いた場合、その木は対応するノードを持っていないため
+\item 5で取得したノードが、第一引数のqueryの条件に一致するか確かめる。
+\item 一致する場合そのノードを返す。
+\end{enumerate}
+
+
+balanceKey・balanceValueを使用しない検索は、Default Jungle TreeのIndexを使わない検索と同じで、木の全探索を行う。

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/redBlackTree.tex	Sat Jan 28 19:28:01 2017 +0900
@@ -0,0 +1,271 @@
+\chapter{非破壊 TreeMap の実装}
+JungleのIndexでは、Functional Javaの非破壊 TreeMap を用いて実装を行っていた。
+しかし、Functional Java の TreeMap は、木の変更の手間が大きい、並列実行時処理速度が落ちるなど、実用的な性能を持っていなかった。
+なので、Jungleで使用するための非破壊 TreeMap を作成した。
+TreeMapは、Red Black Treeのアルゴリズムに基づき実装した。
+
+\section{Red Black Tree}
+Red Black Treeは二分探索木の一つで、以下の条件を満たした木のことである。
+
+\begin{enumerate}
+\item ノードは赤か黒の色を持つ。
+\item ルートノードの色は黒。
+\item 全ての葉は黒である。
+\item 赤いノードの子は黒色である。
+\item 全ての葉からルートまでのパスには、同じ個数の黒いノードがある。
+\end{enumerate}
+
+Red Black Treeは、データの挿入、削除時に、上記の条件を崩さないように木のバランスを取る。
+この条件により、Red Black Treeはデータの検索、削除、探索をO(log n)で行える。
+
+\section{非破壊 TreeMap の定義}
+非破壊 TreeMapは、Javaのジェネリクスを用いて、{\tt TreeMap<K,V>Key}と定義されており、
+TreeMapを作る際に、K,Vに任意の型を記述することで、
+KeyとValueで使用する型を設定できる。
+
+ソースコード\ref{createTreeMap}に、KeyをString型・Value を ByteBuffer 型 で宣言する例を記述する。
+
+
+
+\section{非破壊 TreeMap のAPI}
+
+非破壊 TreeMap は、表\ref{RedBlackTreeAPI}に記述してあるAPIを提供している。
+\begin{table}[htb]
+\begin{center}
+\caption{非破壊 TreeMap に実装されているAPI}
+\begin{tabular}{|p{15em}|p{24em}|}        \hline
+{\tt Node getRoot()} & TreeMap のルートノードを返す。 \\ \hline
+{\tt boolean isEmpty()} & TreeMap に値が入っているなら{\tt true}を返す。  \\ \hline
+{\tt TreeMap<K,V> put(K key, V value)} & TreeMap に{\tt key:value} の組で値を挿入し、新しい TreeMap を返す。 \\ \hline
+{\tt TreeMap<K,V> delete(K key)} & TreeMap に{\tt key} とペアで格納されている値を削除し、新しい TreeMap を返す。\\ \hline
+{\tt Iterator<K> keys()} & TreeMap が持っている全ての {\tt key} を Iteratorで返す。 \\ \hline
+\end{tabular}
+\label{RedBlackTreeAPI}
+\end{center}
+\end{table}
+
+非破壊 TreeMapは、通常の TreeMap と異なり、put・deleteを行うと編集後の新しい TreeMap を返すため、新しい TreeMap で受ける必要がある。
+この時返ってくるTreeMapと、編集前のTreeMapは別オブジェクトである。
+
+\section{非破壊 Red Black Treeへのデータの挿入}
+非破壊 Red Black Treeへのデータの挿入は、以下の手順で行われる。
+
+\begin{enumerate}
+\item 挿入を行うノードと、現在のノードを比較する。
+\item 比較の結果、大きかった場合右に、小さかった場合左のノードに進む。
+\item 挿入を行う場所にたどり着くまで、１・２を繰り返す。
+\item 現在の位置に、赤色でノードを挿入する。
+\item 木のバランスを取りながら、ルートまでの経路の複製を行う。その際、変更が加えられないノードへは参照を行い過去の木と最大限共有を行う。
+\end{enumerate}
+
+Red Black Treeのデータ挿入時のバランスは、次の5パターンに分けられる。
+
+\subsection{データ挿入時のバランス ケース1}
+
+\begin{enumerate}
+\item ノードを挿入した位置がルート
+\end{enumerate}
+挿入時上記の条件を満たしている場合、ルートノードの色を黒に変更することで木のバランスを取る。
+ルートノードの色を黒に変更しても、左右のSub Treeの黒の個数が一つ増えるだけなので、Red Black Treeの条件は守られる。
+
+
+\subsection{データ挿入時のバランス ケース2}
+\begin{enumerate}
+\item 挿入したノードinsの親ノードBが黒。
+\end{enumerate}
+
+バランス時、上記の条件を満たしている場合、Red Black Treeの条件は崩れないため、そのまま赤色でノードを挿入して問題はない。%(図\ref{fig:RedBlackTreeInsert1})。
+
+%\begin{figure}[htpb]
+%\begin{center}
+%\includegraphics[scale=0.5]{figures/RedBlackTreeInsert1.pdf}
+%\caption{データ挿入時のバランス2}
+%\label{fig:RedBlackTreeInsert1}
+%\end{center}
+%\end{figure}
+
+\subsection{データ挿入時のバランス ケース3}
+\begin{enumerate}
+\item 挿入したノードinsの親の親ノードAが黒。
+\item ノードAの両方の子ノードB・Cが赤。
+\end{enumerate}
+
+バランス時、上記の条件を満たしている場合、ノードB・Cを黒に、ノードAを赤に変更する(図\ref{fig:RedBlackTreeInsert2})。
+
+また、本章の図に表記されている四角のノードの色は、Red Black Treeの条件を守られているなら問わず、それ以下の子ノードは省略してあるものとする。
+\begin{figure}[htpb]
+\begin{center}
+\includegraphics[scale=0.5]{figures/RedBlackTreeInsert2.pdf}
+\caption{データ挿入時のバランス3}
+\label{fig:RedBlackTreeInsert2}
+\end{center}
+\end{figure}
+
+バランス後、ノードAを新しくノードinsとして再帰的に木のバランスを行う。
+この変更は最悪の場合ルートまで続く。
+
+\subsection{データ挿入時のバランス ケース4}
+\begin{enumerate}
+\item 挿入したノードinsの親の親ノードAが黒。
+\item ノードAの、挿入したノード側の子ノードBが赤。
+\item 逆側の子ノードCが黒。
+\item ノードinsがノードBの木の中心側の子。
+\end{enumerate}
+
+バランス時、上記の条件を満たしている場合、ノードBを中心に外側に回転処理を行い(\ref{fig:RedBlackTreeInsert3})、次節に記述するバランス5を行う。
+その際、ノードBをinsとして扱う。
+
+\begin{figure}[htpb]
+\begin{center}
+\includegraphics[scale=0.5]{figures/RedBlackTreeInsert3.pdf}
+\caption{データ挿入時のバランス4}
+\label{fig:RedBlackTreeInsert3}
+\end{center}
+\end{figure}
+
+
+
+\subsection{データ挿入時のバランス ケース5}
+\begin{enumerate}
+\item 挿入したノードinsの親の親ノードAが黒。
+\item ノードAの、挿入したノード側の子ノードBが赤。
+\item 逆側の子ノードCが黒
+\item ノードinsがノードBの木の外側の子。
+\end{enumerate}
+
+バランス時、上記の条件を満たしている場合、ノードAを中心に内側に回転処理を行い、回転後ノードAとノードBの色を入れ替える。
+
+\begin{figure}[htpb]
+\begin{center}
+\includegraphics[scale=0.5]{figures/RedBlackTreeInsert4.pdf}
+\caption{データ挿入時のバランス5}
+\label{fig:RedBlackTreeInsert4}
+\end{center}
+\end{figure}
+
+
+赤黒木は、データ挿入時にこれらの処理を行うことで、木のバランスを取る。
+
+\section{Red Black Treeのノード削除}
+Red Black Treeのノード削除は、以下の手順で行われる。
+
+\begin{enumerate}
+\item 削除を行うノードと、現在のノードを比較する。
+\item 比較の結果、大きかった場合右に、小さかった場合左のノードに進む。
+\item 削除を行うノードにたどり着くまで、１・２を繰り返す。
+\item ノードに子が無い場合削除を行う。
+\item 片側に部分木(子ノード)がある場合、ノードを削除した後、部分木のルートを昇格させる。
+\item 両側に部分木(子ノード)がある場合は、左部分木の最大の値を持つノードの値を取得し、削除を行うノードと同じ色に変更した後、置換する。
+\item 置換したノードを削除する(ここで削除させるノードは部分木の最大値であるため、子ノードは1つ以下、つまり削除の手順2・3どちらかの手順で削除できる)。
+\item 削除したノードから、木のバランスを取りながら、ルートまでの経路の複製を行う。その際Defaul Jungle Treeと同じように、変更が加えられないノードへは参照を行い過去の木と最大限共有を行う。
+\end{enumerate}
+
+
+RedBlackTreeのバランスは、ノード削除時の状態によって、次の6パターンに分けられる。
+また。これ以降削除対象のノードと置換したノードを、ノードrepと記述する。
+
+
+\subsection{データ削除時のバランス ケース1}
+\begin{enumerate}
+\item ノードrepがルート。
+\end{enumerate}
+
+上記の条件を満たしている場合、全ての経路の黒ノード数が1つ減った状態で条件が成立しバランスは終了する。
+
+\subsection{データ削除時のバランス ケース2}
+\begin{enumerate}
+\item ノードrepが黒。
+\item ノードA・B・C・D・E・Fが黒。
+\end{enumerate}
+
+バランス時、上記の条件を満たしている場合、ノードBを赤に変える(図\ref{fig:RedBlackTreeDelete1})。
+そうすることで、ノードB・E・F以下の黒ノードの階層が減って、ノードA以下の木のバランスが回復する。
+その後、Aを新たなノードrepとして木のバランスを行う。
+このバランスは最悪の場合ルートまで続き、ケース2で終了する。
+
+\begin{figure}[htpb]
+\begin{center}
+\includegraphics[scale=0.45]{figures/RedBlackTreeDelete1.pdf}
+\caption{データ削除時のバランス2}
+\label{fig:RedBlackTreeDelete1}
+\end{center}
+\end{figure}
+
+
+\subsection{データ削除時のバランス ケース3}
+\begin{enumerate}
+\item ノードrepが黒。
+\item ノードA・C・D・E・Fが黒
+\item ノードBが赤。
+\end{enumerate}
+
+上記の条件を満たしている場合、ノードAを中心に外側に回転、その後ノードAを赤に、ノードBを黒に変更する(図\ref{fig:RedBlackTreeDelete2})。
+その後、ノードrepを基準に再び木のバランスを行う。
+この時のバランスは、図\ref{fig:RedBlackTreeDelete2}における、ノードEの子供の色に応じてケース5・6・7のどれかに帰着する。
+
+\begin{figure}[htpb]
+\begin{center}
+\includegraphics[scale=0.45]{figures/RedBlackTreeDelete2.pdf}
+\caption{データ削除時のバランス3}
+\label{fig:RedBlackTreeDelete2}
+\end{center}
+\end{figure}
+
+\subsection{データ削除時のバランス ケース4}
+\begin{enumerate}
+\item ノードrepが黒。
+\item ノードB・C・D・E・Fが黒
+\item ノードAが赤。
+\end{enumerate}
+
+上記の条件を満たしている場合、ノードAを黒に、ノードBを赤に変更する。
+そうすることで、ノードA側の右側のSub Treeの黒の深さを変えることなく、左側のSub Treeの黒の深さが1つ増え、バランスが取れる。
+\begin{figure}[htpb]
+\begin{center}
+\includegraphics[scale=0.45]{figures/RedBlackTreeDelete3.pdf}
+\caption{データ削除時のバランス4}
+\label{fig:RedBlackTreeDelete3}
+\end{center}
+\end{figure}
+
+
+\subsection{データ削除時のバランス ケース5}
+\begin{enumerate}
+\item ノードrepが黒。
+\item ノードB・C・D・Fが黒。
+\item ノードEの色が赤。
+\end{enumerate}
+
+上記の条件を満たしている場合、ノードBを中心に外側に回転、その後、ノードEを黒に、ノードBを赤に変更する。
+そして、データ削除時のバランス ケース7に帰着する。
+
+\begin{figure}[htpb]
+\begin{center}
+\includegraphics[scale=0.45]{figures/RedBlackTreeDelete4.pdf}
+\caption{データ削除時のバランス5}
+\label{fig:RedBlackTreeDelete4}
+\end{center}
+\end{figure}
+
+
+\subsection{データ削除時のバランス ケース6}
+\begin{enumerate}
+\item ノードrepが黒。
+\item ノードB・C・Dが黒。
+\item ノードFの色が赤。
+\end{enumerate}
+
+上記の条件を満たしている場合、ノードAを中心にノードrep側に回転、その後、ノードAとノードBの色を交換し、ノードFを黒にする。
+そうすることで、ノードE・Fの黒の深さを変えること無く、ノードrepの黒の深さを1増やせるため、木のバランスが取れる。
+
+\begin{figure}[htpb]
+\begin{center}
+\includegraphics[scale=0.45]{figures/RedBlackTreeDelete5.pdf}
+\caption{データ削除時のバランス6}
+\label{fig:RedBlackTreeDelete5}
+\end{center}
+\end{figure}
+
+Red Black Treeは、削除時に上記のバランスを行うことで、木のバランスを保っている。
+
+これらの機能を実装することで、非破壊TreeMapは完成した。

Binary file 修論.xmind has changed