#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/persistent-data-structures/persistence-vs-rollback

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/persistent-data-structures/persistence-vs-rollback

Repovive

Persistence vs Rollback - Persistent Data Structures | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units

Open in Course

Persistence vs Rollback

When to use what

Persistent structures: Keep all versions, query any version.

Rollback Union-Find: Keep history stack, only access latest or rolled-back state.

	Persistent	Rollback
Query any version	Yes	No
Space	$O(n + m \log n)$	$O(m)$
Implementation	Complex	Simple
Path compression	No	No

Use rollback when you only need to undo, not query arbitrary past states.

Use persistence when you need random access to version history.

HannahHi! I'm Hannah. Let me know if you need help understanding anything!