Perzistentné dátové štruktúry

Sources

Persistent data structures

keep old versions of the data structure
partial persistence: update only current version, query any old version, linearly ordered versions
full persistence: update any version, versions form a tree
confluent persistence: combine versions together, versions form a DAG
fully functional: never modify nodes, only create new
backtracking: query and update only current version, revert to an older version
retroactive: insert updates to the past, delete past updates, query at any past time relative to current set of updates

model of computation, without arrays
constant-size nodes, holding data (numbers, characters, etc) and pointers to other nodes
pointers can be assigned: address of a newly created node, copy of another pointer, null
no pointer arithmetic
root node with all global variables, all variable names in the program of the form root.current.left.x

First, let us prove that the algorithm for the update will terminate

assume that outdegree of each node is at most 2p-1
update on one node may trigger other updates etc, in the worst case the each newest node might be rebuilt (replaced by another)
However, no node is replaced by a new node twice within one recursive update
Assume by contradiction that such a node exists and consider the first node that is rebuilt the second time. Between its first and second rebuild it must have acquired 2p mods, but these mods must have been caused by nodes to which this nodes points to being rebuilt. There are at most 2p-1 such nodes and none of them was rebuilt more than once because we consider the first node which is rebuilt twice.

Notes for the amortized analysis:

as real cost, count the number of recursive calls (all other computation proportional to that)
want to prove that the amortized cost of one update is 2
- if there is space in the node for another mod, real cost is 1 (only one call to modify), change of potential is 1, so amortized cost is 2
- if the node is full, real cost is 1, change of potential is -2p plus amortized cost of all subsequent recursive calls. By induction, each of these calls has amortized cost 2, so overall amortized cost is 1
- what is the induction on? The depth in the tree of recursive calls (leaves are the base cases where node not full). We have already proved that this node is finite.