Mercurial > hg > Papers > 2020 > soto-midterm
annotate tex/rbtree.tex @ 7:acad18934981
add description of rbtree
| author | soto@cr.ie.u-ryukyu.ac.jp |
|---|---|
| date | Mon, 14 Sep 2020 05:41:23 +0900 |
| parents | |
| children | a8bc8c6b48bd |
| rev | line source |
|---|---|
| 7 | 1 \section{赤黒木} |
| 2 赤黒木とは平衡2分探索木の一つである。 | |
| 3 2分探索木の点にランクという概念を追加し、そのランクの違いを赤と黒の色で分け、以下の定義に基づくように | |
| 4 木を構成した物である。 | |
| 5 | |
| 6 \begin{enumerate} | |
| 7 \item 各点は赤か黒の色である。 | |
| 8 \item 点が赤である場合の親となる点の色は黒である。 | |
| 9 \item 外点(葉。つまり一番下の点)は黒である。 | |
| 10 \item 任意の点から外点までの黒色の点はいずれも同数となる。 | |
| 11 \end{enumerate} | |
| 12 参考となるグラフを以下に示す。上記の定義を満たしていることが分かる。 | |
| 13 \begin{center} | |
| 14 \includegraphics[height=3.5cm]{pic/rbtree.pdf} | |
| 15 \caption{CodeGear、DataGear での Hoare Logic} | |
| 16 \label{hoare} | |
| 17 \end{center} |