Link/Cut Tree

Link/cut tree (also known as a Sleator–Tarjan dynamic tree) is a dynamic forest data structure in computation and algorithms invented by Daniel D. Sleator and Robert E. Tarjan in 1981 (journal publication 1983; recipient of the 1999 ACM Paris Kanellakis Theory and Practice Award). It maintains a collection of vertex-disjoint rooted trees on N total vertices under topological structural modifications—specifically linking a tree root as a child of another vertex (Link), cutting the edge between a vertex and its parent (Cut), and changing the root of a tree (Evert)—together with associative path queries and path updates in O(log N) amortized time per operation (or O(log N) worst-case time when implemented with globally biased search trees).

Whereas a static heavy–light decomposition partitions a fixed tree into static heavy chains based on immutable subtree sizes, a link/cut tree dynamically partitions each represented tree into preferred paths based on the most recently accessed vertices. Each preferred path is stored by depth in an auxiliary splay tree connected to its parent path by a one-way path-parent pointer. Using a single unifying primitive called Access(v), which makes the root-to-v path into a single preferred splay tree with v at its root, all dynamic forest and path-aggregation operations reduce to constant numbers of splay-tree split and join steps.

Represented Trees vs. Auxiliary Splay Trees

Let F be a forest of rooted represented trees on N vertices. In each represented tree T ∈ F, every vertex u holds at most one preferred child:

• If the most recent Access operation within u's subtree T_u occurred at a vertex inside the subtree of child w ∈ children(u), then w is the preferred child of u, and the edge (u, w) is called a preferred edge.
• If the most recent Access operation within T_u was at u itself (or if T_u has never been accessed), then u has no preferred child, and all outgoing child edges of u are non-preferred (dashed) edges.

Because every vertex has at most one preferred child, the preferred edges partition the vertices of T into vertex-disjoint downward paths called preferred paths (analogous to heavy chains in heavy–light decomposition).

To manipulate these variable-length preferred paths dynamically, each preferred path P is represented by an auxiliary binary search tree—specifically a splay tree—keyed by represented tree depth:

• For any node x in the auxiliary splay tree, its left subtree contains vertices on P that are shallower (closer to the represented root) than x, and its right subtree contains vertices on P that are deeper than x.
• Consequently, an in-order traversal of an auxiliary splay tree visits the vertices of its preferred path P in top-to-bottom order from the shallowest vertex on P (the path head) to the deepest vertex on P.

Solid Pointers vs. Dashed Path-Parent Pointers

How are different auxiliary splay trees connected to one another to reflect the non-preferred edges of T? Sleator and Tarjan unified both intra-splay pointers and inter-path pointers inside a single three-pointer node structure (left, right, parent):

1. Internal Splay Edges (Solid Edges): Inside an auxiliary splay tree representing a preferred path P, every non-root node x has its parent pointer pointing to its parent y in the splay tree, and y reciprocates with either y.*left* = x or y.*right* = x.
2. Inter-Path Connections (Dashed Path-Parent Pointers): Let r_P be the root of the auxiliary splay tree for preferred path P, and let h_P be the shallowest vertex on P (the leftmost node in r_P's splay tree). If h_P is not the global root of the represented tree T, then h_P has a parent p in T connected by a non-preferred edge (p, h_P). This link is stored by setting r_P.*parent* = p, while p does not point back to r_P as a left or right splay child (p.*left* ≠ r_P and p.*right* ≠ r_P).

This asymmetry provides an O(1) test isRoot(x) for whether a node x is the root of its auxiliary splay tree: x is an auxiliary splay root if and only if x.*parent* is null or (x.*parent*.*left* ≠ x and x.*parent*.*right* ≠ x). Splay rotations inside an auxiliary tree stop as soon as isRoot(x) is true, while transferring the path-parent pointer to the new splay root.

The Access(v) Primitive

The fundamental building block of a link/cut tree is Access(v), which modifies the preferred-path decomposition of v's represented tree T so that the unique path from the root of T down to v becomes a single preferred path ending at v (with v having no preferred child), and splays v to the root of that combined auxiliary splay tree:

1. Sever Deeper Preferred Tail at v: Call Splay(v) within v's current auxiliary splay tree. Now all vertices on v's preferred path deeper than v reside in v.*right*. Detach v.*right* ← null (converting the solid link to v's old right child into a dashed path-parent pointer automatically, because the old right child still has parent = v).
2. Climb Dashed Path-Parent Pointers to the Tree Root: While v.*parent* ≠ null (meaning v's auxiliary splay tree has a path-parent w = v.*parent* in an upper preferred path):
   • Call Splay(w) in w's auxiliary splay tree so w becomes the root of its auxiliary tree.
   • Replace w's old preferred tail (w.*right*, which becomes a dashed path-parent child of w) with v: set w.*right* ← v.
   • Perform a single rotation (Splay(v)) to bring v above w as the root of the newly merged auxiliary splay tree, and repeat.

Implementing Dynamic Forest Operations via Access

Once Access(v) is defined, every dynamic forest query and update reduces to a few pointer assignments:

• FindRoot(v): Execute Access(v), walk left pointers (x ← x.*left*) to find the shallowest (minimum-depth) vertex r on the root-to-v path, and call Splay(r) (for amortized time bounds) before returning r.
• PathAggregate(r, v) / PathUpdate(r, v, Δ): After calling Access(v), the auxiliary splay tree rooted at v contains the exact vertices of the root-to-v path, so its root summary field v.*agg* (or lazy tag v.*lazy*) reads or updates the entire root-to-v path in O(1) additional time.
• Cut(v) (deletes the edge between v and its represented parent p): Execute Access(v). Now p and all other ancestors of v reside in v.*left*. Set v.*left*.*parent* ← null and v.*left* ← null.
• Link(u, v) (makes root u a child of v in another tree): Execute Access(u) and Access(v), then set u.*parent* ← v (creating a dashed path-parent edge from u to v).
• Evert(v) (re-roots v's represented tree at v): Execute Access(v), and toggle a lazy in-order reversal bit v.*rev* ← ¬v.*rev* on the auxiliary splay root v (which swaps left and right children downward when pushed, reversing the depth ordering of the root-to-v path). With Evert(u) followed by Access(v), any arbitrary u–v tree path becomes the single auxiliary splay tree rooted at v.
• LCA(u, v): Execute Access(u), then execute Access(v); the last path-parent vertex w spliced during Access(v) is LCA(u, v).

Potential-Function Proof of O(log N) Amortized Complexity

Within computational complexity theory, Sleator and Tarjan proved the O(log N) amortized bound by superimposing a static heavy–light decomposition on the represented trees alongside the splay potential Φ = ∑_x ⌊log₂(size(x))⌋:

• Classify each preferred-edge creation in Access(v) as either heavy (if the newly preferred edge is a heavy edge in the static heavy–light decomposition of T) or light (if it is a light edge).
• By the splay-tree Access Lemma, splicing k preferred paths along a telescoping sequence of splay trees takes O(log N + k) amortized splay steps.
• Along any root-to-v path, at most ⌊log₂ N⌋ edges are light, so at most ⌊log₂ N⌋ light path splices occur during Access(v).
• Furthermore, whenever a heavy edge (p, c) is turned into a preferred edge, it must first have been destroyed by an earlier Access that preferred a light sibling of c. Since each Access creates at most ⌊log₂ N⌋ light preferred edges, the amortized number of heavy preferred-edge creations per Access is also bounded by ⌊log₂ N⌋, yielding O(log N) amortized time per operation.

1. Maximum Network Flow Acceleration: Sleator and Tarjan originally invented link/cut trees to represent partial augmenting trees of unsaturated residual edges, accelerating the blocking-flow phase of Dinic's algorithm from O(V²E) to O(V E log V) and accelerating the push–relabel algorithm to O(V E log(V²/E)).
2. Dynamic Minimum Spanning Trees and Online Graph Connectivity: Maintaining a minimum spanning tree under online edge insertions with decreasing weights uses a link/cut tree to query the maximum-weight edge on the cycle between u and v in O(log N) time, cutting that bottleneck edge and linking (u, v) whenever the new edge is lighter.

Why are splay trees used instead of red–black trees inside a link/cut tree?

If each preferred path were stored in a standard height-balanced red–black tree of size s_i, traversing O(log N) dashed edges during Access(v) and splitting/joining each balanced BST in O(log s_i) time would cost O(log² N) total time. Because a splay tree adapts to access weights via the telescoping Access Lemma ∑ (r(w_i+1) − r(w_i)) ≤ log₂ N, the entire sequence of O(log N) splay operations telescopes to O(log N) amortized time.

Can link/cut trees maintain general graphs containing cycles?

A link/cut tree directly maintains forests (acyclic graphs). However, for general graphs with cycles, Holm–de Lichtenberg–Thorup (HLT) dynamic connectivity and dynamic minimum spanning tree algorithms maintain a spanning forest inside a link/cut tree (or Euler tour tree) while routing non-tree replacement edges across O(log N) hierarchy levels.

1. Sleator, D. D., & Tarjan, R. E. (1983). "A data structure for dynamic trees." Journal of Computer and System Sciences, 26(3), 362–391. https://doi.org/10.1016/0022-0000(83)90006-590006-5)
2. Sleator, D. D., & Tarjan, R. E. (1985). "Self-adjusting binary search trees." Journal of the ACM, 32(3), 652–686. https://doi.org/10.1145/3828.3835
3. Goldberg, A. V., & Tarjan, R. E. (1988). "A new approach to the maximum-flow problem." Journal of the ACM, 35(4), 921–940. https://doi.org/10.1145/48014.61051
4. Holm, J., de Lichtenberg, K., & Thorup, M. (2001). "Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity." Journal of the ACM, 48(4), 723–760. https://doi.org/10.1145/502090.502095