Vocabulary
| Term | Meaning |
|---|
Represented tree T | The actual tree the link-cut tree is maintaining (a fragment of the level graph) 53:00, 53:45 |
| Auxiliary tree (aux tree) | The splay tree storing one preferred path 53:00 |
| Path-parent pointer | Stored at the root of each aux tree; points at the represented-tree parent of the top node of that path 51:56, 53:45, 55:15 |
How the paths are stored
- Each preferred path lives in a splay tree keyed by depth: a node higher in the represented tree has a smaller key
50:43, 51:11.
- Consequence used everywhere: within an aux tree, the left subtree = ancestors, the right subtree = descendants
1:03:08, 1:03:29.
- A balanced BST would work and give
O(log² n); splay trees are used to reach O(log n) 50:07, 50:18.
- The result is a tree of trees: aux trees linked upward by path-parent pointers, which encode the non-preferred edges
52:38, 53:00, 55:15.
- Even a single vertex forms its own singleton aux tree with its own path-parent pointer
52:38, 56:12.
Pointers go up only
- The child aux tree remembers its parent in the represented tree; the parent aux tree does not remember what hangs off it — and never needs to
56:12, 56:45.
flowchart BT
B["aux tree B<br/>(splay, keyed by depth)"] -.path parent.-> A["aux tree A<br/>(root path)"]
C["aux tree C"] -.path parent.-> A
S["singleton aux tree"] -.path parent.-> B
- Aux trees are keyed by depth, not by capacity; capacities are carried as augmented values (see topic 9)
50:43.