Mercurial > hg > Papers > 2018 > nozomi-master
changeset 25:9325a5d0a6e0
Add figure
| author | atton <atton@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Mon, 23 Jan 2017 10:39:15 +0900 |
| parents | 2db27c32eaad |
| children | 5510bb043a74 |
| files | paper/cbc.tex paper/fig/non-destructive-rbtree.pdf |
| diffstat | 2 files changed, 9 insertions(+), 1 deletions(-) [+] |
line wrap: on
line diff
--- a/paper/cbc.tex Mon Jan 23 10:36:42 2017 +0900 +++ b/paper/cbc.tex Mon Jan 23 10:39:15 2017 +0900 @@ -210,9 +210,17 @@ これらの条件より、木をルートから辿った際に最も長い経路は最も短い経路の高々二倍に収まる。 +\newpage % for layout + GearsOS で実装されている赤黒木は特に非破壊赤黒木であり、一度構築した木構造は破壊される操作ごとに新しい木構造が生成される。 非破壊赤黒木の実装の基本的な戦略は、変更したいノードへのルートノードからの経路を全て複製し、変更後に新たなルートノードとする。 この際に変更が行なわれていない部分は変更前の木と共有する(図\ref{fig:non-destructive-rbtree})。 これは一度構築された木構造は破壊されないという非破壊の性質を用いたメモリ使用量の最適化である。 -% TODO: rbtree +\begin{figure}[htbp] + \begin{center} + \includegraphics[scale=0.5]{fig/non-destructive-rbtree} + \caption{非破壊赤黒木の編集} + \label{fig:non-destructive-rbtree} + \end{center} +\end{figure}