Mercurial > hg > Papers > 2020 > soto-midterm

comparison tex/rbtree.tex @ 11:a8bc8c6b48bd default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
fix
author soto@cr.ie.u-ryukyu.ac.jp
date Tue, 15 Sep 2020 07:06:29 +0900
parents acad18934981
children
comparison
equal deleted inserted replaced
10:c162ca9b997e 11:a8bc8c6b48bd
1 \section{赤黒木} 1 \section{RedBlackTree}
2 赤黒木とは平衡2分探索木の一つである。 2 RedBlackTree (または赤黒木)とは平衡2分探索木の一つである。
3 2分探索木の点にランクという概念を追加し、そのランクの違いを赤と黒の色で分け、以下の定義に基づくように 3 2分探索木の点にランクという概念を追加し、そのランクの違いを赤と黒の色で分け、以下の定義に基づくように
4 木を構成した物である。 4 木を構成した物である。図では省略しているが、値を持っている点の下に黒色の空の葉があり、それが外点となる
5 5
6 \begin{enumerate} 6 \begin{enumerate}
7 \item 各点は赤か黒の色である。 7 \item 各点は赤か黒の色である。
8 \item 点が赤である場合の親となる点の色は黒である。 8 \item 点が赤である場合の親となる点の色は黒である。
9 \item 外点(葉。つまり一番下の点)は黒である。 9 \item 外点(葉。つまり一番下の点)は黒である。
10 \item 任意の点から外点までの黒色の点はいずれも同数となる。 10 \item 任意の点から外点までの黒色の点はいずれも同数となる。
11 \end{enumerate} 11 \end{enumerate}
12 参考となるグラフを以下に示す。上記の定義を満たしていることが分かる。 12 参考となる\figref{rbtree}を以下に示す。上記の定義を満たしていることが分かる。
13 \begin{center} 13 \begin{center}
14 \includegraphics[height=3.5cm]{pic/rbtree.pdf} 14 \includegraphics[height=3.5cm]{pic/rbtree.pdf}
15 \caption{CodeGear、DataGear での Hoare Logic} 15 \caption{RedBlackTree の一例}
16 \label{hoare} 16 \label{rbtree}
17 \end{center} 17 \end{center}