Mercurial > hg > Papers > 2021 > soto-thesis
changeset 7:9d7e993dadbd
ADD tree image
author | soto <soto@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Thu, 11 Feb 2021 23:36:12 +0900 (2021-02-11) |
parents | dcc839d6f569 |
children | bb7e9eaf9df8 |
files | paper/final_thesis.pdf paper/pic/rbt/bst.pdf paper/pic/rbt/bt.pdf paper/pic/rbt/llrbt.pdf paper/pic/rbt/rbt.pdf paper/pic/rbt/tree.pdf paper/tex/rbt_intro.tex |
diffstat | 7 files changed, 41 insertions(+), 6 deletions(-) [+] |
line wrap: on
line diff
--- a/paper/tex/rbt_intro.tex Thu Feb 11 23:34:03 2021 +0900 +++ b/paper/tex/rbt_intro.tex Thu Feb 11 23:36:12 2021 +0900 @@ -5,15 +5,40 @@ 下図の○の部分を node (節) と呼び、top node を root(根) と呼ぶ。 特に、根を持つ木構造のことを強調して、Rooted Tree (根付き木) と呼ぶ事がある。 +\begin{figure}[H] + \begin{center} + \includegraphics[height=4.5cm]{pic/rbt/tree.pdf} + \end{center} + \caption{RedBlackTree の一例} + \label{rbtree} +\end{figure} + \section{Binary Tree} 各 node からすぐ下に辺で結ばれている node をその node の child またはson (子ある いは子供)と呼ぶ。 child 側から上の辺を parent (親) と呼ぶ。 下図のように、各 node が持つ child が高々2つである Tree を Binary Tree (2分木)と呼ぶ。 +\begin{figure}[H] + \begin{center} + \includegraphics[height=4.5cm]{pic/rbt/bt.pdf} + \end{center} + \caption{RedBlackTree の一例} + \label{rbtree} +\end{figure} + \section{Binary Search Tree} Rooted Binary Tree に対して、 以下の制約を持つものを、Binary Search Tree と呼ぶ。 -$左側の子孫にある要素 < 親 < 右側の子孫にある要素$ +$左側の子孫にある要素 < 親 < 右側の子孫にある要素$ + +\begin{figure}[H] + \begin{center} + \includegraphics[height=7.5cm]{pic/rbt/bst.pdf} + \end{center} + \caption{RedBlackTree の一例} + \label{rbtree} +\end{figure} + \section{RedBlackTree} RedBlackTree (または赤黒木)とは平衡2分探索木の一つである。 @@ -27,11 +52,14 @@ \item 任意の点から外点までの黒色の点はいずれも同数となる。 \end{enumerate} 参考となる\figref{rbtree}を以下に示す。上記の定義を満たしていることが分かる。 -\begin{center} -\includegraphics[height=3.5cm]{pic/rbtree.pdf} -%\caption{RedBlackTree の一例} -\label{rbtree}% -\end{center} + +\begin{figure}[H] + \begin{center} + \includegraphics[height=7.5cm]{pic/rbt/rbt.pdf} + \end{center} + \caption{RedBlackTree の一例} + \label{rbtree} +\end{figure} \section{Left Learing Red Black Tree} Left Learing Red Black Tree とは Red Black Tree の変形である。 @@ -44,5 +72,12 @@ 本来の Red Black Tree の実装は困難であるため、本論では Red Black Tree の仕様を満たしている Left Learning Red Black Tree を検証する。 +\begin{figure}[H] + \begin{center} + \includegraphics[height=7.5cm]{pic/rbt/llrbt.pdf} + \end{center} + \caption{RedBlackTree の一例} + \label{rbtree} +\end{figure}