Persistent data structure: Difference between revisions

Revision as of 13:25, 20 June 2025

Revision as of 13:33, 20 June 2025

Line 34:

====Complexity of fat node====

With using fat node method, it requires O(1) space for every modification: just store the new data. Each modification takes O(1) additional time to store the modification at the end of the modification history. This is an [[Amortized analysis|amortized time]] bound, assuming modification history is stored in a growable [[Array data structure|array]]. At [[access time]], the right version at each node must be found as the structure is traversed. If "''m"'' modifications were to be made, then each access operation would have <math>O(\log m)</math> slowdown resulting from the cost of finding the nearest modification in the array. Alternatively, one can employ the [[van Emde Boas tree]] at each node (possibly the space-efficient version using hashing) to reduce the time for an access to <math>O(\log\log m)</math> at the cost of increasing update time to <math>O(\log\log m)</math>.

===Path copying===