Persistent Data Structure

其中一種 implement partially persistence binary tree (或 constant degree tree) 的方法結合了 fat node + path copying
可以做到
Time slowdown = O(1) (+ O(log N) for finding root)
Additional memory = O(1) per modification (amortized)

做法是, 原本的 node 變成可以儲著 2 個 version 的 fat node (多出的稱為 modification box)
Access 時, 比較想 access 的 version 和 modification box (如有) 的 time stamp 來決定使用哪一個
所以 access slowdown = O(1)

Modify 時, 如果未使用 modification box, 則把新 version 寫在 modification box
否則, 把新 version 寫在 branch 開的新 node 中, 然後使用 path copy 一路 cascade 上去

Memory complexity analysis:
設 d =最新 version 的 tree 中用了 modification box 的 node 的數量
每次 modify 時, 必定是最底的 k 個 node branch 開了新 node, 然後上面一個 node 寫了 modification box, 再上面的不變
即 d' = d - k + 1

由於 d 不可能小於 0, 每次 branch new node 會使 d 減 1
而每次 modify 會使 d 增加 1
即 M 次 modify 後, 最多只會 branch 開 M + O(1) 個 new node
均攤每次為 O(1)

References: http://en.wikipedia.org/wiki/Persistent_data_structure