Perzistentné dátové štruktúry

Sources

• lectures L01, L02, L03 by Erika Demaina from MIT: http://courses.csail.mit.edu/6.851/spring12/lectures/

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

Pointer machine

• 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