Mercurial > hg > Papers > 2020 > soto-midterm
view tex/rbtree.tex @ 11:a8bc8c6b48bd default tip
fix
author | soto@cr.ie.u-ryukyu.ac.jp |
---|---|
date | Tue, 15 Sep 2020 07:06:29 +0900 |
parents | acad18934981 |
children |
line wrap: on
line source
\section{RedBlackTree} RedBlackTree (または赤黒木)とは平衡2分探索木の一つである。 2分探索木の点にランクという概念を追加し、そのランクの違いを赤と黒の色で分け、以下の定義に基づくように 木を構成した物である。図では省略しているが、値を持っている点の下に黒色の空の葉があり、それが外点となる \begin{enumerate} \item 各点は赤か黒の色である。 \item 点が赤である場合の親となる点の色は黒である。 \item 外点(葉。つまり一番下の点)は黒である。 \item 任意の点から外点までの黒色の点はいずれも同数となる。 \end{enumerate} 参考となる\figref{rbtree}を以下に示す。上記の定義を満たしていることが分かる。 \begin{center} \includegraphics[height=3.5cm]{pic/rbtree.pdf} \caption{RedBlackTree の一例} \label{rbtree} \end{center}