--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/tex/rbtree.tex	Mon Sep 14 05:41:23 2020 +0900
@@ -0,0 +1,17 @@
+\section{赤黒木}
+赤黒木とは平衡2分探索木の一つである。
+2分探索木の点にランクという概念を追加し、そのランクの違いを赤と黒の色で分け、以下の定義に基づくように
+木を構成した物である。
+
+\begin{enumerate}
+  \item 各点は赤か黒の色である。
+  \item 点が赤である場合の親となる点の色は黒である。
+  \item 外点(葉。つまり一番下の点)は黒である。
+  \item 任意の点から外点までの黒色の点はいずれも同数となる。
+\end{enumerate}
+参考となるグラフを以下に示す。上記の定義を満たしていることが分かる。
+\begin{center}
+\includegraphics[height=3.5cm]{pic/rbtree.pdf}
+\caption{CodeGear、DataGear での Hoare Logic}
+\label{hoare}
+\end{center}