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

$ curl repovive.com/roadmaps/data-structures/persistent-data-structures/version-trees

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

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

$ curl repovive.com/roadmaps/data-structures/persistent-data-structures/version-trees

Repovive

Version Trees - Persistent Data Structures | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

Version Trees

Tracking version relationships

With full persistence, versions form a tree (or DAG with confluence):

class VersionedStructure:
    roots: map from version_id to root
    parent: map from version_id to parent_version_id

    function update(version, ...)
        newRoot := ...
        newVersion := nextId()
        roots[newVersion] := newRoot
        parent[newVersion] := version
        return newVersion

    function getAncestors(version)
        result := []
        while version is not null
            result.append(version)
            version := parent[version]
        return result

You can traverse the version tree for debugging or analysis.