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

$ curl repovive.com/roadmaps/data-structures/link-cut-trees/auxiliary-trees

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

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

$ curl repovive.com/roadmaps/data-structures/link-cut-trees/auxiliary-trees

Repovive

Auxiliary Trees - Link-Cut Trees | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

Auxiliary Trees

Splay trees for paths

Each preferred path is stored in an auxiliary splay tree where:

Nodes are ordered by depth in the original tree
Left subtree = nodes closer to root
Right subtree = nodes farther from root

Original tree path: root - a - b - c
Splay tree order:   root < a < b < c

Splay tree structure (one possibility):
      b
     / \
    a   c
   /
 root

The splay tree's in-order traversal gives the path from root to deepest node.

Parent pointers: every node has a parent in its auxiliary tree, but the root of each auxiliary tree has a path-parent pointer to the original tree parent (if any).