Mercurial > hg > Papers > 2017 > tatsuki-master
diff jungleUpdatePoint.tex @ 6:498b8f4175f9
commit
author | tatsuki |
---|---|
date | Wed, 01 Feb 2017 08:24:04 +0900 |
parents | 90e06e17ca6b |
children | f75a57018792 |
line wrap: on
line diff
--- a/jungleUpdatePoint.tex Mon Jan 30 03:54:57 2017 +0900 +++ b/jungleUpdatePoint.tex Wed Feb 01 08:24:04 2017 +0900 @@ -6,7 +6,7 @@ しかし、Functional Javaは、処理が重く、実用的な性能ではなかったため、非破壊の TreeMap の実装を新しく行った。 \section{Indexの差分 Update} -Jungleの木はIndexの更新をCommit時に Full Updateで行っている。 +Jungleの木は、Indexの更新をCommit時に Full Updateで行っている。 そのため、Commitを行うたび、O(n)のIndexのUpdateが入り、木の編集時大きなネックとなっていた。 前の木との差分だけIndexを更新する機能をJungleに追加することで、この問題を解決した。 @@ -29,8 +29,9 @@ \section{Red Black Jungle Tree} Default Jungle Treeにおいて、Indexの更新は大きな手間となっている。 Indexに使用する属性名が1種類で、木構造の形がデータを表現していない場合、Jungle Tree自身をIndexとしたほうが、効率的に木構造を構築できる。 -そこで、ノードの挿入を行うと木のバランスを取る、Red Black Treeの性質を組み込んだRed Black Jungle Treeの実装を行った。 +そこで、Red Black Treeの性質を組み込んだRed Black Jungle Treeの実装を行った。 Red Black Jungle Tree は、生成時に木のバランスを取る際に使用する属性名(Balance Key)を指定する。 +ノードの挿入・削除時、Balance Keyを用いて木のバランスを取る・ Red Black Jungle Tree の木の編集は、Red Black Jungle Tree Editorを用いて行う。 ノードの挿入時に、木のバランスを取るための属性値が必要になるため、ノードと値の挿入を同時に行うAPIを実装した。