Persistent data structure: Difference between revisions

Revision as of 13:57, 20 June 2025

Revision as of 14:02, 20 June 2025

Line 44:

===A combination===

Driscoll, Sarnak, [[Daniel Sleator|Sleator]], [[Robert Tarjan|Tarjan]] came up<ref name=Driscoll /> with a way to combine the techniques of fat nodes and path copying, achieving O(1) access slowdown and O(1) modificationamortized overhead in space and time complexityper modification. Their method assumes a linked data structure with at most ''d'' incoming pointers to each node, where ''d'' is a known constant.

In each node, one modification box is stored. This box can hold one modification to the node—either a modification to one of the pointers, or to the node's key, or to some other piece of node-specific data—and a timestamp for when that modification was applied. Initially, every node's modification box is empty.