|
11
|
1 \section{RedBlackTree}
|
|
|
2 RedBlackTree (または赤黒木)とは平衡2分探索木の一つである。
|
|
7
|
3 2分探索木の点にランクという概念を追加し、そのランクの違いを赤と黒の色で分け、以下の定義に基づくように
|
|
11
|
4 木を構成した物である。図では省略しているが、値を持っている点の下に黒色の空の葉があり、それが外点となる
|
|
7
|
5
|
|
|
6 \begin{enumerate}
|
|
|
7 \item 各点は赤か黒の色である。
|
|
|
8 \item 点が赤である場合の親となる点の色は黒である。
|
|
|
9 \item 外点(葉。つまり一番下の点)は黒である。
|
|
|
10 \item 任意の点から外点までの黒色の点はいずれも同数となる。
|
|
|
11 \end{enumerate}
|
|
11
|
12 参考となる\figref{rbtree}を以下に示す。上記の定義を満たしていることが分かる。
|
|
7
|
13 \begin{center}
|
|
|
14 \includegraphics[height=3.5cm]{pic/rbtree.pdf}
|
|
11
|
15 \caption{RedBlackTree の一例}
|
|
|
16 \label{rbtree}
|
|
7
|
17 \end{center}
|
