Persistent data structure: Difference between revisions

Revision as of 06:10, 20 March 2025

Revision as of 06:12, 20 March 2025

Line 53:

====Complexity of the combination====

Time and space for modifications require amortized analysis. A modification takes O(1) amortized space, and O(1) amortized time. To see why, use a [[Potential method|potential function]] ''ϕ'', where ''ϕ''(T) is the number of full live nodes in T . The live nodes of T are just the nodes that are reachable from the current root at the current time (that is, after the last modification). The full live nodes are the live nodes whose modification boxes are full.

Each modification involves some number of copies, say ''k'', followed by 1 change to a modification box. Consider each of the ''k'' copies. Each costs O(1) space and time, but decreases the potential function by one. (First, the node to be copied must be full and live, so it contributes to the potential function. The potential function will only drop, however, if the old node isn't reachable in the new tree. But it is known that it isn't reachable in the new tree—the next step in the algorithm will be to modify the node's parent to point at the copy. Finally, it is known that the copy's modification box is empty. Thus, replaced a full live node has been replaced with an empty live node, and ''ϕ'' goes down by one.) The final step fills a modification box, which costs O(1) time and increases ''ϕ'' by one.

Putting it all together, the change in ''ϕ'' is ΔϕΔ''ϕ'' =1−1 − ''k''. Thus, the algorithm takes O(''k'' +ΔϕΔ''ϕ'')= O(1) space and O(''k'' +ΔϕΔ''ϕ'' +1) = O(1) time

==Generalized form of persistence==