# HG changeset patch
# User atton <atton@cr.ie.u-ryukyu.ac.jp>
# Date 1485135402 -32400
# Node ID 2db27c32eaad8f129e6a1550f43e16adbb64424f
# Parent  925d7e02b712b35d93db8910c75f571464234255
Add rbtree figure

diff -r 925d7e02b712 -r 2db27c32eaad paper/cbc.tex
--- a/paper/cbc.tex	Mon Jan 23 10:00:41 2017 +0900
+++ b/paper/cbc.tex	Mon Jan 23 10:36:42 2017 +0900
@@ -173,4 +173,46 @@
 % }}}
 
 \section{メタ計算ライブラリ akasha を用いた赤黒木の実装の検証}
+現状の GearsOS に実装されているメタ計算として、非破壊赤黒木が存在する。
+メタ計算として定義することにより、ノーマルレベルからは木のバランスを必要なく要素の挿入と探索、削除が行なえる。
+赤黒木とは二分探索木の一種であり、木の各ノードが赤と黒の色を持っている。
+木に対して要素の挿入や削除を行なった際、その色を用いて木のバランスを保つ。
 
+二分探索木の条件は以下である。
+
+\begin{itemize}
+    \item 左の子孫の値は親の値より小さい
+    \item 右の子孫の値は親の値より大きい
+\end{itemize}
+
+加えて、赤黒木が持つ具体的な条件は以下のものである。
+
+\begin{itemize}
+    \item 各ノードは赤か黒の色を持つ。
+    \item ルートノードの色は黒である。
+    \item 葉ノードの色は黒である。
+    \item 赤ノードは2つの黒ノードを子として持つ(よって赤ノードが続くことは無い)。
+    \item ルートから最下位ノードへの経路に含まれる黒ノードの数はどの最下位ノードでも一定である。
+\end{itemize}
+
+
+数値を要素に持つ赤黒木の例を図\ref{fig:rbtree}に示す。
+ルートノードは黒であり、赤ノードは連続していない。
+加えて各最下位ノードへの経路に含まれる黒ノードの個数は全て2である。
+
+\begin{figure}[htbp]
+    \begin{center}
+        \includegraphics[scale=0.5]{fig/rbtree.pdf}
+        \caption{赤黒木の例}
+        \label{fig:rbtree}
+    \end{center}
+\end{figure}
+
+これらの条件より、木をルートから辿った際に最も長い経路は最も短い経路の高々二倍に収まる。
+
+GearsOS で実装されている赤黒木は特に非破壊赤黒木であり、一度構築した木構造は破壊される操作ごとに新しい木構造が生成される。
+非破壊赤黒木の実装の基本的な戦略は、変更したいノードへのルートノードからの経路を全て複製し、変更後に新たなルートノードとする。
+この際に変更が行なわれていない部分は変更前の木と共有する(図\ref{fig:non-destructive-rbtree})。
+これは一度構築された木構造は破壊されないという非破壊の性質を用いたメモリ使用量の最適化である。
+
+% TODO: rbtree
diff -r 925d7e02b712 -r 2db27c32eaad paper/fig/rbtree.graffle
Binary file paper/fig/rbtree.graffle has changed
diff -r 925d7e02b712 -r 2db27c32eaad paper/fig/rbtree.pdf
Binary file paper/fig/rbtree.pdf has changed