Mercurial > hg > Papers > 2016 > kkb-master

--- a/paper/Makefile	Thu Feb 18 19:44:11 2016 +0900
+++ b/paper/Makefile	Thu Feb 18 23:01:23 2016 +0900
@@ -9,6 +9,11 @@
 RM      = rm -f
 EBB     = extractbb

+PDFUNITE = pdfunite
+PDF1 = sigos2014
+PDF2 = sigos2015
+TMP = tmp
+
 #  Option definitions
 DVIPDFMOPT =
 DVIPSOPT   = -D 720 -mode esphi -O 0mm,0mm -N0
@@ -18,6 +23,9 @@

 #  Recipes
 all: pdf# $(TARGET).ps
+	$(PDFUNITE) $(TARGET).pdf $(PDF1).pdf $(PDF2).pdf $(TMP).pdf
+	$(RM) $(TARGET).pdf
+	mv $(TMP).pdf $(TARGET).pdf
 	open $(TARGET).pdf

 dvi:
--- a/paper/gearsos.tex	Thu Feb 18 19:44:11 2016 +0900
+++ b/paper/gearsos.tex	Thu Feb 18 23:01:23 2016 +0900
@@ -192,7 +192,7 @@
 \lstinputlisting[label=insert, caption=Insert Case]{src/insert.c}

 木の左回転を行う Code Gear はソースコード:\ref{rotateLeft}の通りである。
-自分、親、兄弟の3点のノードの回転である。
+自分、親、子の3点のノードの回転である。
 回転を行ったあとにも Red-Black Tree の条件を満たしているか確認する必要があるので回転後に変更された親ノードを再びスタックに記憶する。
 また、回転の際に現在見ているノードが変更する必要がある。
Binary file paper/master_paper.pdf has changed
Binary file paper/sigos2014.pdf has changed
Binary file paper/sigos2015.pdf has changed
--- a/slide/index.html	Thu Feb 18 19:44:11 2016 +0900
+++ b/slide/index.html	Thu Feb 18 23:01:23 2016 +0900
@@ -87,7 +87,7 @@
 <!-- === begin markdown block ===

       generated by markdown 1.1.1 on Ruby 2.0.0 (2013-02-24) [x86_64-darwin12.3.0]
-                on 2016-02-18 15:55:53 +0900 with Markdown engine kramdown (1.4.0)
+                on 2016-02-18 21:56:50 +0900 with Markdown engine kramdown (1.4.0)
                   using options {}
   -->

@@ -480,6 +480,55 @@
 </ul>

 <p><img src="./pictures/tree.svg" alt="非破壊木構造" /></p>
+
+
+</div>
+<div class='slide '>
+<!-- _S9SLIDE_ -->
+<h1 id="persistent-data-tree-1">Persistent Data Tree</h1>
+<ul>
+  <li>木構造を構築するとき最悪なケースでは事実上の線形リストになり、計算量が O(n) となる</li>
+  <li>挿入・削除・検索における処理時間を保証するために Red-Black Tree アルゴリズムを用いて木構造の平衡性を保つ</li>
+  <li>Red-Black Tree では変更したノードからルートに上りながら条件を満たすように色の変更や木の回転を行う</li>
+  <li>Code Gear の継続では呼び出し元に戻ることが出来ないので Context に辿ったパスを記憶するためのスタックを準備する。</li>
+</ul>
+
+<pre lang="C"><code>// Unique Data Gear
+enum UniqueData {
+    Tree,
+    Traverse,
+    Node,
+};
+
+// Context definication
+struct Context {
+    stack_ptr node_stack;
+};
+
+// Red-Black Tree definication
+union Data {
+    // size: 8 byte
+    struct Tree {
+        struct Node* root;
+    } tree;
+    // size: 12 byte
+    struct Traverse {
+        struct Node* current;
+        int result;
+    } traverse;
+    // size: 32 byte
+    struct Node {
+        int key;
+        union Data* value;
+        struct Node* left;
+        struct Node* right;
+        enum Color {
+            Red,
+            Black,
+        } color;
+    } node;
+};
+</code></pre>
 <!-- === end markdown block === -->
 </div>
--- a/slide/index.md	Thu Feb 18 19:44:11 2016 +0900
+++ b/slide/index.md	Thu Feb 18 23:01:23 2016 +0900
@@ -308,3 +308,42 @@
 * Code Gear の継続では呼び出し元に戻ることが出来ないので Context に辿ったパスを記憶するためのスタックを準備する。

 ```C
+// Unique Data Gear
+enum UniqueData {
+    Tree,
+    Traverse,
+    Node,
+};
+
+// Context definication
+struct Context {
+    stack_ptr node_stack;
+};
+
+// Red-Black Tree definication
+union Data {
+    // size: 8 byte
+    struct Tree {
+        struct Node* root;
+    } tree;
+    // size: 12 byte
+    struct Traverse {
+        struct Node* current;
+        int result;
+    } traverse;
+    // size: 32 byte
+    struct Node {
+        int key;
+        union Data* value;
+        struct Node* left;
+        struct Node* right;
+        enum Color {
+            Red,
+            Black,
+        } color;
+    } node;
+};
+```
+
+# Persistent Data Tree
+* 自分、親、
\ No newline at end of file