Every other link-cut operation starts with access 57:49, 1:12:57.

What it must accomplish

  • Make the root-to-v path preferred in v's represented tree 58:14, 59:34.
  • That forces preferred-child changes: some formerly preferred edges stop being preferred and the paths must be re-split and re-merged 58:40, 58:59.
  • After the access, v has no preferred child (by the definition), so its old preferred child must be cut off 1:00:05.
  • Goal state: v is the root of the root aux tree of the tree of aux trees 1:00:45, 1:01:03, 1:01:40.

Step 1 — splay v and detach its descendants

  • Splay v inside its own aux tree so v becomes that tree's root 1:02:18.
  • Keyed by depth ⇒ the right subtree holds v's descendants on the path, which are no longer preferred. Detach it as its own aux tree 1:03:08, 1:03:29.
r = v.right
r.path_parent = v        # the old preferred edge becomes a path-parent pointer
r.parent      = none
v.right       = none

1:03:29, 1:04:01, 1:07:01

Step 2 — walk up, splicing aux trees together (loop)

  • v now has a path-parent pointer to some w in another aux tree; w need not be that tree's root 1:04:53.
  • Who is w? the represented-tree parent of the minimum-keyed (shallowest) element of v's aux tree, i.e. the parent of the top of v's path 1:05:17.
  • Splay w to the root of its aux tree, then swap w's old preferred descendants for v's path:
splay(w)
w.right.path_parent = w      # w's OLD preferred child becomes a path parent
w.right.parent      = none
w.right = v                  # v's path becomes w's new preferred descendant
v.parent = w
v.path_parent = w.path_parent   # v/w path-parent bookkeeping
w.path_parent = none
splay(v)                     # bring v back up

1:05:43, 1:06:18, 1:06:32, 1:07:01, 1:07:29, 1:08:03

  • Repeat in a while loop until v sits in the root aux tree, then splay once more 1:08:29.
  • Nelson's own warning after nearly dropping it: "you need to make sure you maintain the path parents" 1:09:20, 1:09:37.
  • Everything spliced under w on the right is at greater depth than w, since it all hangs off w in the represented tree — so BST order by depth is preserved 1:10:41, 1:11:15.
  • In effect: splice two paths together and cut off whatever hung below w before, because w's preferred child just changed 1:10:11, 1:10:41.
  • Net effect of each splice step: a parent pointer becomes a path-parent pointer and vice versa 1:07:01.

Cost

  • The running time of access is governed by the number of preferred-child changes encountered walking up the tree — one splice per change 1:11:59, 1:12:57.
  • This is the quantity the amortized analysis (next class) has to bound 1:12:57.