Persistent data structure: Difference between revisions

Revision as of 13:33, 20 June 2025

Revision as of 13:36, 20 June 2025

Line 37:

===Path copying===

This method assumes that the data structure is a linked graph of nodes.

WithOn theupdate, patha copyingcopy methodis a copymade of all nodes is made on the path to any node which is about to be modified. These changes must then be [[Fractional cascading|cascaded]] back through the data structure: all nodes that pointed to the old node must be modified to point to the new node instead. These modifications cause more cascading changes, and so on, until the root node is reached.

====Complexity of path copying====