Hubbry Logo
Link/cut treeLink/cut treeMain
Open search
Link/cut tree
Community hub
Link/cut tree
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Link/cut tree
Link/cut tree
Link/cut tree
View on Wikipedia
from Wikipedia

Link/cut tree
TypeTree
Invented1982
Invented by
Time complexity in big O notation
AverageWorst case
Link O(log n) amortized O(log n)
Cut O(log n) amortized O(log n)
Path O(log n) amortized O(log n)
FindRoot O(log n) amortized O(log n)

A link/cut tree is a data structure for representing a forest, a set of rooted trees, and offers the following operations:

  • Add a tree consisting of a single node to the forest.
  • Given a node in one of the trees, disconnect it (and its subtree) from the tree of which it is part.
  • Attach a node to another node as its child.
  • Given a node, find the root of the tree to which it belongs. By doing this operation on two distinct nodes, one can check whether they belong to the same tree.

The represented forest may consist of very deep trees, so if we represent the forest as a plain collection of parent pointer trees, it might take us a long time to find the root of a given node. However, if we represent each tree in the forest as a link/cut tree, we can find which tree an element belongs to in O(log(n)) amortized time. Moreover, we can quickly adjust the collection of link/cut trees to changes in the represented forest. In particular, we can adjust it to merge (link) and split (cut) in O(log(n)) amortized time.

Link/cut trees divide each tree in the represented forest into vertex-disjoint paths, where each path is represented by an auxiliary data structure (often splay trees, though the original paper predates splay trees and thus uses biased binary search trees). The nodes in the auxiliary data structure are ordered by their depth in the corresponding represented tree. In one variation, Naive Partitioning, the paths are determined by the most recently accessed paths and nodes, similar to Tango Trees. In Partitioning by Size paths are determined by the heaviest child (child with the most children) of the given node. This gives a more complicated structure, but reduces the cost of the operations from amortized O(log n) to worst case O(log n). It has uses in solving a variety of network flow problems and to jive data sets.

In the original publication, Sleator and Tarjan referred to link/cut trees as "dynamic trees", or "dynamic dyno trees".

Structure

[edit]

We take a tree where each node has an arbitrary degree of unordered nodes and split it into paths. We call this the represented tree. These paths are represented internally by auxiliary trees (here we will use splay trees), where the nodes from left to right represent the path from root to the last node on the path. Nodes that are connected in the represented tree that are not on the same preferred path (and therefore not in the same auxiliary tree) are connected via a path-parent pointer. This pointer is stored in the root of the auxiliary tree representing the path.

Demonstrating how nodes are stored by depth in the link-cut tree

Preferred paths

[edit]

When an access to a node v is made on the represented tree, the path that is taken becomes the preferred path. The preferred child of a node is the last child that was on the access path, or null if the last access was to v or if no accesses were made to this particular branch of the tree. A preferred edge is the edge that connects the preferred child to v.

In an alternate version, preferred paths are determined by the heaviest child.

Showing how a link cut tree transforms preferred paths into a forest of trees.

Operations

[edit]

The operations we are interested in are FindRoot(Node v), Cut(Node v), Link(Node v, Node w), and Path(Node v). Every operation is implemented using the Access(Node v) subroutine. When we access a vertex v, the preferred path of the represented tree is changed to a path from the root R of the represented tree to the node v. If a node on the access path previously had a preferred child u, and the path now goes to child w, the old preferred edge is deleted (changed to a path-parent pointer), and the new path now goes through w.

Access

[edit]

After performing an access to node v, it will no longer have any preferred children, and will be at the end of the path. Since nodes in the auxiliary tree are keyed by depth, this means that any nodes to the right of v in the auxiliary tree must be disconnected. In a splay tree this is a relatively simple procedure; we splay at v, which brings v to the root of the auxiliary tree. We then disconnect the right subtree of v, which is every node that came below it on the previous preferred path. The root of the disconnected tree will have a path-parent pointer, which we point to v.

We now walk up the represented tree to the root R, breaking and resetting the preferred path where necessary. To do this we follow the path-parent pointer from v (since v is now the root, we have direct access to the path-parent pointer). If the path that v is on already contains the root R (since the nodes are keyed by depth, it would be the left most node in the auxiliary tree), the path-parent pointer will be null, and we are done the access. Otherwise we follow the pointer to some node on another path w. We want to break the old preferred path of w and reconnect it to the path v is on. To do this we splay at w, and disconnect its right subtree, setting its path-parent pointer to w. Since all nodes are keyed by depth, and every node in the path of v is deeper than every node in the path of w (since they are children of w in the represented tree), we simply connect the tree of v as the right child of w. We splay at v again, which, since v is a child of the root w, simply rotates v to root. We repeat this entire process until the path-parent pointer of v is null, at which point it is on the same preferred path as the root of the represented tree R.

During an access old preferred paths are broken and replaced with path-parent pointers, while the accessed node is splayed to the root of the tree

FindRoot

[edit]

FindRoot refers to finding the root of the represented tree that contains the node v. Since the access subroutine puts v on the preferred path, we first execute an access. Now the node v is on the same preferred path, and thus the same auxiliary tree as the root R. Since the auxiliary trees are keyed by depth, the root R will be the leftmost node of the auxiliary tree. So we simply choose the left child of v recursively until we can go no further, and this node is the root R. The root may be linearly deep (which is worst case for a splay tree), we therefore splay it so that the next access will be quick.

Cut

[edit]

Here we would like to cut the represented tree at node v. First we access v. This puts all the elements lower than v in the represented tree as the right child of v in the auxiliary tree. All the elements now in the left subtree of v are the nodes higher than v in the represented tree. We therefore disconnect the left child of v (which still maintains an attachment to the original represented tree through its path-parent pointer). Now v is the root of a represented tree. Accessing v breaks the preferred path below v as well, but that subtree maintains its connection to v through its path-parent pointer.

[edit]

If v is a tree root and w is a vertex in another tree, link the trees containing v and w by adding the edge(v, w), making w the parent of v. To do this we access both v and w in their respective trees, and make w the left child of v. Since v is the root, and nodes are keyed by depth in the auxiliary tree, accessing v means that v will have no left child in the auxiliary tree (since as root it is the minimum depth). Adding w as a left child effectively makes it the parent of v in the represented tree.

Path

[edit]

For this operation we wish to do some aggregate function over all the nodes (or edges) on the path from root R to node v (such as "sum" or "min" or "max" or "increase", etc.). To do this we access v, which gives us an auxiliary tree with all the nodes on the path from root R to node v. The data structure can be augmented with data we wish to retrieve, such as min or max values, or the sum of the costs in the subtree, which can then be returned from a given path in constant time.

Pseudocode of operations

[edit]
Switch-Preferred-Child(x, y):
    if (right(x) is not null)
        path-parent(right(x)) = x
    right(x) = y
    if (y is not null)
        parent(y) = x

Access(v):
    splay(v)
    Switch-Preferred-Child(v, null)
    if (path-parent(v) is not null) 
        w = path-parent(v)
        splay(w)
        Switch-Preferred-Child(w, v)
        Access(v)

Link(v, w):
    Access(v)
    Access(w)
    left(v) = w
    parent(w) = v

Cut(v):
    Access(v)
    if (left(v) is not null)
        path-parent(left(v)) = path-parent(v)
        left(v) = null
    path-parent(v) = null

Analysis

[edit]

Cut and link have O(1) cost, plus that of the access. FindRoot has an O(log n) amortized upper bound, plus the cost of the access. The data structure can be augmented with additional information (such as the min or max valued node in its subtrees, or the sum), depending on the implementation. Thus Path can return this information in constant time plus the access bound.

So it remains to bound the access to find our running time.

Access makes use of splaying, which we know has an O(log n) amortized upper bound. So the remaining analysis deals with the number of times we need to splay. This is equal to the number of preferred child changes (the number of edges changed in the preferred path) as we traverse up the tree.

We bound access by using a technique called Heavy-Light Decomposition.

Heavy-light decomposition

[edit]
Main article: Heavy path decomposition

This technique calls an edge heavy or light depending on the number of nodes in the subtree. ⁠⁠ represents the number of nodes in the subtree of v in the represented tree. An edge is called heavy if size(v) > 1⁄2 size(parent(v)). Thus we can see that each node can have at most 1 heavy edge. An edge that is not a heavy edge is referred to as a light edge.

The light-depth refers to the number of light edges on a given path from root to vertex v. Light-depth ≤ lg n because each time we traverse a light-edge we decrease the number of nodes by at least a factor of 2 (since it can have at most half the nodes of the parent).

So a given edge in the represented tree can be any of four possibilities: heavy-preferred, heavy-unpreferred, light-preferred or light-unpreferred.

First we prove an upper bound.

O(log 2 n) upper bound

[edit]

The splay operation of the access gives us log n, so we need to bound the number of accesses to log n to prove the O(log 2 n) upper bound.

Every change of preferred edge results in a new preferred edge being formed. So we count the number of preferred edges formed. Since there are at most log n edges that are light on any given path, there are at most log n light edges changing to preferred.

The number of heavy edges becoming preferred can be ⁠⁠ for any given operation, but it is ⁠⁠ amortized. Over a series of executions we can have n-1 heavy edges become preferred (as there are at most n-1 heavy edges total in the represented tree), but from then on the number of heavy edges that become preferred is equal to the number of heavy edges that became unpreferred on a previous step. For every heavy edge that becomes unpreferred a light edge must become preferred. We have seen already that the number of light edges that can become preferred is at most log n. So the number of heavy edges that become preferred for m operations is ⁠⁠. Over enough operations (⁠⁠) this averages to ⁠⁠.

Improving to O(log n) upper bound

[edit]

We have bound the number of preferred child changes at ⁠⁠, so if we can show that each preferred child change has cost O(1) amortized we can bound the access operation at ⁠⁠. This is done using the potential method.

Let s(v) be the number of nodes under v in the tree of auxiliary trees. Then the potential function . We know that the amortized cost of splaying is bounded by:

We know that after splaying, v is the child of its path-parent node w. So we know that:

We use this inequality and the amortized cost of access to achieve a telescoping sum that is bounded by:

where R is the root of the represented tree, and we know the number of preferred child changes is ⁠⁠. s(R) = n, so we have ⁠⁠ amortized.

Application

[edit]

Link/cut trees can be used to solve the dynamic connectivity problem for acyclic graphs. Given two nodes x and y, they are connected if and only if FindRoot(x) = FindRoot(y). Another data structure that can be used for the same purpose is Euler tour tree.

In solving the maximum flow problem, link/cut trees can be used to improve the running time of Dinic's algorithm from to .

See also

[edit]

Further reading

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Link/cut tree

View on Grokipedia
from Grokipedia
A link–cut tree (also known as an ST-tree or dynamic tree) is a self-adjusting data structure that represents and maintains a dynamic forest of rooted trees with n nodes, enabling efficient updates to the forest structure—such as linking two trees by adding an edge or cutting an edge to split a tree—along with queries for path aggregates (e.g., sums, minima, or maxima of edge weights from a node to its root), all in amortized O(log n) time per operation. Introduced by Daniel D. Sleator and Robert E. Tarjan in 1983, the structure achieves this efficiency through a preferred-path decomposition of each tree into vertex-disjoint paths, where each path is represented as an auxiliary binary search tree that self-adjusts to recent accesses. The core mechanism relies on representing the forest as a collection of these preferred paths connected by non-preferred edges, with the auxiliary trees originally formulated as path-biased binary search trees but commonly implemented using splay trees for their amortized balancing properties via rotations. Key operations, such as access(v)—which restructures the tree to make the path from v to the root a single preferred path—are built around splaying the relevant nodes into the auxiliary tree root, followed by linking or splicing paths as needed for updates like link(v, w) or cut(v). This design not only supports basic connectivity queries like finding the root of a node's tree but also generalizes to weighted trees for applications in network optimization, geometric searching, and other dynamic graph problems requiring fast path maintenance. The amortized time bounds hold across sequences of operations, with worst-case O(log n) per operation possible using globally biased trees instead of self-adjusting ones.

Introduction

Definition and purpose

A link/cut tree (LCT), also known as a dynamic tree or ST-tree, is a data structure designed to represent and maintain a forest of rooted trees under dynamic updates, where the trees are partitioned into vertex-disjoint preferred paths represented by auxiliary splay trees. This representation enables efficient handling of connectivity changes in the forest while supporting queries on paths between nodes. The primary purpose of an LCT is to support operations such as linking two trees by adding an edge, cutting an edge to separate a subtree, finding the root of a tree containing a given node, and aggregating values (e.g., sum or minimum) along the path from a node to its root, all in dynamic environments where the forest structure frequently changes. These capabilities make LCTs particularly useful for graph-theoretic problems, such as maintaining connectivity in undirected graphs subject to edge additions and deletions. Key advantages of LCTs include achieving amortized O(log n) time per operation, which matches the complexity of Euler tour trees for dynamic path queries but leverages self-adjusting splay trees for amortized guarantees, and provides greater flexibility than heavy-light decomposition for handling frequent structural modifications without full tree rebuilds. By leveraging splay trees for path representation, LCTs balance efficiency and adaptability in applications like network flow algorithms and dynamic minimum spanning trees.

Historical background

The link/cut tree data structure was developed in 1981 by Daniel D. Sleator and Robert E. Tarjan, initially termed "dynamic trees" to support efficient operations on collections of rooted forests, such as linking and cutting edges while maintaining path information. The foundational work was presented at the 13th Annual ACM Symposium on Theory of Computing in 1981 and published in full in 1983 in the Journal of Computer and System Sciences. This development was driven by needs in network design, including faster algorithms for maximum flow computations, and in computational geometry, such as finding constrained minimum spanning trees. By 1985, Sleator and Tarjan had refined the approach in their paper on splay trees, extending the self-adjusting mechanism to dynamic trees and adopting the name "link/cut trees" to highlight the primitive link and cut operations at its core. This evolution built directly on splay trees, another self-adjusting structure invented by the same authors, enabling amortized O(log n) time for path manipulations. In the 1990s, link/cut trees were extended to handle more general path aggregates, such as minimum queries or sums along paths, through related structures like Euler tour trees and top trees that preserved the logarithmic efficiency. Extensions for parallel, batch, and unrooted operations have appeared in the 2010s and 2020s, though practical implementations have gained prominence in areas like competitive programming during the 2010s.

Data Structure Components

Splay trees as auxiliary structures

In link/cut trees, preferred paths are represented using splay trees as auxiliary data structures, where each path forms a binary tree in which the nodes are ordered according to their depth in the original forest, with left and right children denoting the predecessor and successor along the path, respectively. This representation treats the path as a sequence from the rootward end to the leafward end, enabling efficient manipulation of path segments through standard binary tree operations adapted to splay trees. The self-adjusting nature of splay trees is central to their role in link/cut trees: following an access to a node, the splay operation performs a series of rotations to bring that node to the root of its auxiliary tree, thereby restructuring the tree based on recent access patterns and amortizing the cost over a sequence of operations. This dynamic reorganization ensures that frequently accessed nodes remain near the root, reducing the depth for subsequent operations on the same path. Each node in the link/cut tree incorporates fields typical of splay tree nodes—such as left child, right child, and parent pointers—alongside additional path-parent pointers that link the auxiliary splay trees into the broader forest structure by connecting the rootward end of a child path to its parent node in the parent path. These path-parent pointers distinguish the auxiliary trees from standalone splay trees, allowing the representation of the entire dynamic forest as a collection of interconnected paths. Splay trees are employed in this context because they support amortized O(log n) time for accesses, searches, splits, and joins without requiring explicit balancing mechanisms, making them ideal for the frequent rotations needed to manipulate paths during link and cut operations. Their ability to handle these operations efficiently stems from the potential method analysis, which bounds the total cost by the logarithmic potential of the tree structure.

Preferred paths and path partitioning

In link-cut trees, each non-root node selects one preferred child, initially chosen arbitrarily, which defines a preferred edge to that child and contributes to forming chains known as preferred paths that extend from leaves toward the roots of the trees in the forest. These preferred paths result from the preferred child relation, where the preferred child of a node is the one leading toward the most recently accessed descendant in its subtree, ensuring that recent accesses influence the path structure dynamically. The forest represented by link-cut trees is partitioned into a collection of these disjoint preferred paths, with non-preferred edges (dashed edges) connecting the paths through path-parent pointers that link the root of one path to a node in another path higher in the tree. This decomposition allows the entire structure to be viewed as a set of vertex-disjoint paths, where each path captures a sequence of nodes connected by preferred edges, and the path-parent pointers maintain the overall tree connectivity without forming cycles. The selection of preferred children evolves during operations such as access, where the preferred child pointers are updated along the accessed path to reflect the new most recent access, effectively rotating the partitioning to prioritize the accessed node. In the naive partitioning approach, these changes occur dynamically based on access history without size constraints, leading to potentially long paths but amortized efficiency. An alternative size-based partitioning, akin to heavy-light decomposition, designates a child as preferred if its subtree size is at least half the parent's subtree size, ensuring that any root-to-leaf path traverses at most O(log⁡n)O(\log n) preferred paths and providing worst-case logarithmic bounds. Preferred paths are represented as chains of preferred edges, with the root of each path (the highest node in the chain) maintaining a path-parent pointer to the appropriate node in the parent path unless it is the root of the entire tree. This representation facilitates efficient manipulation, as each path is typically stored using an auxiliary structure like a splay tree to handle local operations within the path.

Core Operations

Access operation

The Access operation in a link-cut tree restructures the auxiliary tree representation to expose the path from a specified vertex vv to the root of its underlying tree, making vv the root of its auxiliary splay tree through a sequence of rotations and updates to preferred child edges. This operation serves as the core mechanism for path manipulation, enabling efficient access to the path for queries or modifications. The procedure initiates by splaying vv to the root of its current auxiliary tree, which brings vv to the forefront of that path's representation. If vv has a preferred child, this child is detached, and the subtree rooted at that child is reassigned a path-parent pointer to vv, effectively splitting the path at vv. While vv is not the overall tree root, the algorithm identifies the path-parent ww of vv's auxiliary tree, splays ww to the root of its own auxiliary tree, detaches ww's right subtree (if any) by setting its path-parent to ww, and then attaches vv's auxiliary tree as ww's new right subtree. This rotation extends the preferred path upward. To preserve the depth-based ordering in splay trees, path directions are reversed as needed during these attachments, ensuring left children represent shallower nodes (closer to the tree root) and right children deeper ones. The process repeats until the path-parent is null, indicating the tree root has been reached. Upon completion, the entire path from the tree root to vv is consolidated into a single preferred path, represented as one auxiliary splay tree with vv at its root; with the tree root now the leftmost node in this auxiliary splay tree and the path-parent of vv set to null, any intersecting preferred paths are dismantled or reformed to maintain the vertex-disjoint partitioning. This reconfiguration destroys old preferred edges along the accessed path and establishes new ones, isolating subtrees via path-parent pointers. Preferred paths thus provide the structural backbone adjusted by this operation. The Access operation runs in amortized O(log⁡n)O(\log n) time, where nn is the number of vertices, leveraging the amortized efficiency of splay trees for rotations and the potential method to bound the total cost across a sequence of operations. The link operation in a link/cut tree merges two distinct trees in the forest by adding an edge that connects a vertex uu from one tree as a child of a vertex vv from the other tree, with the precondition that uu is the root of its tree. To perform link(u,vu, v), the procedure first checks that uu and vv reside in different trees using the FindRoot operation on both vertices; if they share the same root, the operation is aborted to prevent cycles. Assuming distinct trees and uu is a tree root, the Access operation is invoked on vv to expose the path from its tree root to vv. Then, attach uu's auxiliary tree as the preferred (deeper) child of vv by setting uu's path-parent to vv and updating the child pointer of vv accordingly (e.g., right(vv) = uu in the splay tree), and the roots are updated to reflect the new connectivity, thereby combining the trees into a single structure while preserving acyclicity. The cut operation disconnects a subtree from the rest of its tree by removing the edge between a vertex uu and its parent, resulting in two separate trees in the forest, with the precondition that uu is not the root of its tree. For cut(uu), the procedure starts with Access(uu), which restructures the preferred paths to isolate the path from the tree root to uu. Set the left child of uu to null in its auxiliary splay tree, detaching the path from the original tree root to uu's parent and thereby isolating uu's subtree as a new tree with uu as root; preferred edges are adjusted to complete the separation without altering other connections. This modifies the forest's tree connectivity by increasing the number of trees by one, maintaining the overall acyclicity without necessitating a complete rebuild.

Supporting Operations

FindRoot operation

The FindRoot operation in a link-cut tree, denoted as FindRoot(v), returns the root node of the tree containing a given node v within the underlying forest representation. This operation first invokes Access(v) to restructure the preferred paths such that the path from the true root to v becomes a single exposed preferred path, represented as a splay tree rooted at v. In this configuration, the true root appears as the leftmost node in the splay tree, since the path is ordered with shallower nodes to the left and deeper nodes to the right. To identify this root, after Access(v), the algorithm traverses leftward from v by repeatedly setting v to its left child until reaching a node with no left child. This leftmost node is then splayed to the root of its auxiliary tree to optimize future accesses. The process concludes by returning this splayed node as the tree root. Although Access(v) internally relies on path-parent pointers to aggregate and expose the full path by linking intermediate path trees, the FindRoot traversal itself operates solely within the now-unified splay tree, without further path-parent navigation. This operation serves to determine the root for connectivity checks prior to performing a Link, ensuring nodes belong to different trees, and facilitates root-relative queries, such as computing distances or aggregates from the root to v. The amortized time complexity is O(log n), where n is the number of nodes, primarily due to the cost of Access(v); the subsequent left traversal and splay contribute at most O(1) amortized time under the potential method analysis.

Path aggregation and evaluation

In link-cut trees, path aggregation enables the efficient computation of functions such as sums, minima, or custom operations over the values associated with nodes or edges along a path from a given vertex to the root of its tree. This is achieved by augmenting the auxiliary splay trees that represent preferred paths, where each node stores not only structural information but also the necessary aggregate values for its subtree. After performing the Access operation on a vertex vv, the preferred path from the root to vv is restructured such that vv becomes the root of its auxiliary splay tree, and the path itself forms the left spine of this tree. Aggregates can then be evaluated by traversing this left spine or, more efficiently, by directly accessing the precomputed aggregate value stored at the root vv, which represents the combination of values along the entire exposed path. The supported aggregates include path sums, minimums, maximums, and other associative operations that can be maintained through subtree augmentations in the splay trees. Each node in the auxiliary tree holds the aggregate of its subtree, updated during splay operations via rotations that preserve the in-order traversal order corresponding to the path depth. For evaluation, the Access operation splays vv to the root and aggregates the left-path subtree, ensuring that the direction from vv to the root is correctly represented; if the reverse direction (root to vv) is needed, the aggregate can be computed by adjusting the stored values or performing a reversal operation on the path. This mechanism allows queries in amortized O(log⁡n)O(\log n) time, leveraging the self-adjusting properties of splay trees to keep frequently accessed paths near the root. Custom functions can be supported by defining appropriate combination rules for the augmentations, as long as they are invertible or associative to handle path reversals. Extensions to path aggregation accommodate edge weights or node labels by associating values directly with the edges (stored at child nodes) or nodes themselves, enabling aggregates over weighted paths in dynamic forests. For undirected graphs, the structure supports reversibility by allowing the Evert operation to flip path directions, ensuring aggregates can be queried bidirectionally without disrupting the overall tree representation. These features make link-cut trees particularly useful for applications requiring dynamic path queries, such as network flow optimizations or geometric searching, while maintaining the core amortized efficiency bounds.

Implementation Aspects

The pseudocode for the core operations of a link/cut tree—Access, Link, and Cut—is presented below, following common modern implementations. These incorporate a reversal flag (rev) to efficiently handle path reversals during operations, enabling support for unrooted trees or bidirectional traversals without explicit evert operations. The pseudocode assumes a forest of rooted trees represented via preferred path decomposition, where each preferred path is stored in a splay tree auxiliary structure. The following describes a common modern implementation using splay trees with lazy reversal flags for path reversals, extending the original design. The implementation includes supporting functions such as pushdown for propagating reversal flags, splay for restructuring the auxiliary tree, and make_root for changing the perceived root by reversing the path. The core operations are as follows (presented in C++-style pseudocode for clarity): Node structure:

cpp

struct Node { Node *ch[2], *fa; bool rev; Node() : fa(nullptr), rev(false) { ch[0] = ch[1] = nullptr; } };

struct Node { Node *ch[2], *fa; bool rev; Node() : fa(nullptr), rev(false) { ch[0] = ch[1] = nullptr; } };

Helper functions:

cpp

void pushdown(Node *x) { if (x->rev) { std::swap(x->ch[0], x->ch[1]); if (x->ch[0]) x->ch[0]->rev ^= true; if (x->ch[1]) x->ch[1]->rev ^= true; x->rev = false; } } bool get_dir(Node *x) { return x == x->fa->ch[1]; } void rotate(Node *x) { Node *y = x->fa, *z = y->fa; int d = get_dir(x); if (z) z->ch[get_dir(y)] = x; x->fa = z; y->ch[d] = x->ch[d ^ 1]; if (x->ch[d ^ 1]) x->ch[d ^ 1]->fa = y; x->ch[d ^ 1] = y; y->fa = x; // pushup(y); pushup(x); if size/sum maintained } void splay(Node *x) { // Push down from ancestors to x (stack-based for efficiency) // ... (omitted for brevity; standard stack pushdown) while (x->fa) { Node *y = x->fa, *z = y->fa; pushdown(z); pushdown(y); pushdown(x); if (z) { if (get_dir(x) == get_dir(y)) rotate(y); else rotate(x); } rotate(x); } }

void pushdown(Node *x) { if (x->rev) { std::swap(x->ch[0], x->ch[1]); if (x->ch[0]) x->ch[0]->rev ^= true; if (x->ch[1]) x->ch[1]->rev ^= true; x->rev = false; } } bool get_dir(Node *x) { return x == x->fa->ch[1]; } void rotate(Node *x) { Node *y = x->fa, *z = y->fa; int d = get_dir(x); if (z) z->ch[get_dir(y)] = x; x->fa = z; y->ch[d] = x->ch[d ^ 1]; if (x->ch[d ^ 1]) x->ch[d ^ 1]->fa = y; x->ch[d ^ 1] = y; y->fa = x; // pushup(y); pushup(x); if size/sum maintained } void splay(Node *x) { // Push down from ancestors to x (stack-based for efficiency) // ... (omitted for brevity; standard stack pushdown) while (x->fa) { Node *y = x->fa, *z = y->fa; pushdown(z); pushdown(y); pushdown(x); if (z) { if (get_dir(x) == get_dir(y)) rotate(y); else rotate(x); } rotate(x); } }

Access operation:

cpp

void access(Node *x) { for (Node *y = nullptr; x; y = x, x = x->fa) { splay(x); x->ch[1] = y; // pushup(x); if aggregates } }

void access(Node *x) { for (Node *y = nullptr; x; y = x, x = x->fa) { splay(x); x->ch[1] = y; // pushup(x); if aggregates } }

Make root (for root change via reversal):

cpp

void make_root(Node *x) { access(x); splay(x); x->rev ^= true; }

void make_root(Node *x) { access(x); splay(x); x->rev ^= true; }

Find root:

cpp

Node *find_root(Node *x) { access(x); splay(x); pushdown(x); while (x->ch[0]) { x = x->ch[0]; pushdown(x); } splay(x); return x; }

Node *find_root(Node *x) { access(x); splay(x); pushdown(x); while (x->ch[0]) { x = x->ch[0]; pushdown(x); } splay(x); return x; }

Link operation:

cpp

void link(Node *child, Node *parent) { make_root(child); if (find_root(parent) == child) return; // already connected child->fa = parent; }

void link(Node *child, Node *parent) { make_root(child); if (find_root(parent) == child) return; // already connected child->fa = parent; }

Cut operation:

cpp

void cut(Node *child, Node *parent) { make_root(child); access(parent); splay(parent); if (parent->ch[0] != child || child->ch[0] || child->ch[1]) return; // not direct or invalid parent->ch[0] = nullptr; child->fa = nullptr; // pushup(parent); }

void cut(Node *child, Node *parent) { make_root(child); access(parent); splay(parent); if (parent->ch[0] != child || child->ch[0] || child->ch[1]) return; // not direct or invalid parent->ch[0] = nullptr; child->fa = nullptr; // pushup(parent); }

Note: Some implementations vary in conventions for left/right children or aggregate maintenance (e.g., sum on path). The above uses a common modern variant with lazy reversal propagation, where reversal swaps children and propagates lazily during pushdown. This avoids explicit evert for many dynamic operations.

Node Fields and Conventions

Each node vv in the link/cut tree has the following fields:
  • left(v) and right(v): Pointers to left and right children in the splay tree.
  • parent(v): Pointer to the parent in the splay tree.
  • path_parent(v): Pointer to the parent of the root of vv's auxiliary tree in the overall forest (null if vv is on the root path).
  • rev(v): Boolean flag indicating whether the subtree rooted at vv is reversed (initially false).
Operations on splay trees maintain the heap property with respect to depth in the represented tree: left subtrees represent shallower (parentward) portions of the path, and right subtrees represent deeper (childward) portions. A pushdown step propagates the rev flag before rotations or traversals:

pushdown(v): if rev(v): swap(left(v), right(v)) if left(v) ≠ null: rev(left(v)) ← not rev(left(v)) if right(v) ≠ null: rev(right(v)) ← not rev(right(v)) rev(v) ← false

pushdown(v): if rev(v): swap(left(v), right(v)) if left(v) ≠ null: rev(left(v)) ← not rev(left(v)) if right(v) ≠ null: rev(right(v)) ← not rev(right(v)) rev(v) ← false

The splay subroutine rotates vv to the root of its auxiliary tree while preserving the splay tree structure and updating parents. It assumes standard single and double rotations (zig, zig-zig, zig-zag) with pushdown calls at each node visited.

splay(v): pushdown(v) while parent(v) ≠ null: pushdown(parent(parent(v))) pushdown(parent(v)) pushdown(v) if parent(parent(v)) = null: // zig: single rotation rotate(v) else if parent(v) is left child of grandparent and v is left child of parent: // zig-zig rotate(parent(v)) rotate(v) else if parent(v) is right child of grandparent and v is right child of parent: // zig-zig rotate(parent(v)) rotate(v) else: // zig-zag rotate(v) rotate(v) // After splay, v is root of its auxiliary tree

splay(v): pushdown(v) while parent(v) ≠ null: pushdown(parent(parent(v))) pushdown(parent(v)) pushdown(v) if parent(parent(v)) = null: // zig: single rotation rotate(v) else if parent(v) is left child of grandparent and v is left child of parent: // zig-zig rotate(parent(v)) rotate(v) else if parent(v) is right child of grandparent and v is right child of parent: // zig-zig rotate(parent(v)) rotate(v) else: // zig-zag rotate(v) rotate(v) // After splay, v is root of its auxiliary tree

The rotate function performs a single rotation, updating left, right, and parent pointers accordingly (details omitted for brevity, as they follow standard splay tree rotations). Post-rotation, if the auxiliary tree root changes during splay, the path_parent is transferred from the old root to the new root vv.

Access Operation

The Access operation on a node vv restructures the preferred paths so that the path from the tree root to vv becomes a single preferred path represented by one auxiliary splay tree, with vv splayed to its root. It uses a loop to iteratively splay and attach subpaths, handling path-parent pointers and detaching right subtrees (deeper portions). The rev flag is pushed down during splays to maintain correct order.

access(v): splay(v) // v becomes root of its auxiliary tree (includes pushdown) // Detach right subtree (deeper portion below v) and set its path_parent to v if right(v) ≠ null: path_parent(right(v)) ← v parent(right(v)) ← null right(v) ← null current ← v while path_parent(current) ≠ null: w ← path_parent(current) splay(w) // w becomes root of its auxiliary tree // Detach w's right subtree (deeper below w) if right(w) ≠ null: path_parent(right(w)) ← w parent(right(w)) ← null right(w) ← null // Attach current's auxiliary tree as right child of w right(w) ← current parent(current) ← w path_parent(current) ← null current ← w splay(v) // Splay v to root of the full path auxiliary tree

access(v): splay(v) // v becomes root of its auxiliary tree (includes pushdown) // Detach right subtree (deeper portion below v) and set its path_parent to v if right(v) ≠ null: path_parent(right(v)) ← v parent(right(v)) ← null right(v) ← null current ← v while path_parent(current) ≠ null: w ← path_parent(current) splay(w) // w becomes root of its auxiliary tree // Detach w's right subtree (deeper below w) if right(w) ≠ null: path_parent(right(w)) ← w parent(right(w)) ← null right(w) ← null // Attach current's auxiliary tree as right child of w right(w) ← current parent(current) ← w path_parent(current) ← null current ← w splay(v) // Splay v to root of the full path auxiliary tree

After Access(vv), vv is the root of the auxiliary tree representing the path from the tree root (the leftmost node in vv's splay tree in in-order traversal) to vv (the rightmost node). The Link operation connects two nodes uu and vv from different trees by adding an edge with vv as parent of uu, assuming uu is the root of its tree (verified via FindRoot). It first accesses both nodes to expose their paths, then attaches uu's tree as the right (deeper) child of vv.

link(u, v): // Assume FindRoot(u) ≠ FindRoot(v); otherwise, operation fails access(u) access(v) // After access(v), right(v) = null; attach u as deeper child right(v) ← u parent(u) ← v path_parent(u) ← null // Update sizes or aggregates if maintained (e.g., size(v) += size(u))

link(u, v): // Assume FindRoot(u) ≠ FindRoot(v); otherwise, operation fails access(u) access(v) // After access(v), right(v) = null; attach u as deeper child right(v) ← u parent(u) ← v path_parent(u) ← null // Update sizes or aggregates if maintained (e.g., size(v) += size(u))

This operation preserves the preferred path structure, with the new edge becoming part of vv's exposed path.

Cut Operation

The Cut operation severs the edge between vv and its parent in the represented tree, detaching the subtree rooted at vv as a new tree. It accesses vv to expose the path, then nullifies the connection to the left child (the shallower portion above vv, which becomes part of the original tree).

cut(v): access(v) // Exposes path to v; v is now splay root if left(v) ≠ null: // Detach left subtree (path above v) path_parent(left(v)) ← null parent(left(v)) ← null left(v) ← null // The left subtree now heads the remaining original tree // v remains root of its new tree (v plus descendant subtrees via path-parents)

cut(v): access(v) // Exposes path to v; v is now splay root if left(v) ≠ null: // Detach left subtree (path above v) path_parent(left(v)) ← null parent(left(v)) ← null left(v) ← null // The left subtree now heads the remaining original tree // v remains root of its new tree (v plus descendant subtrees via path-parents)

After Cut(vv), the subtree rooted at vv (consisting of vv and its descendant subtrees) becomes a separate tree with vv as root, while the original tree now extends only up to the former parent of vv.

Managing path parents and rotations

In link-cut trees, path-parent pointers connect the root of each auxiliary splay tree (representing a preferred path) to the appropriate node in the parent preferred path, enabling efficient traversal from a node up to the tree root. During the access operation, which restructures the forest to place a target node on the preferred path to the root, path-parents are updated iteratively: the target node is splayed to the root of its current splay tree, its right subtree (representing deeper nodes) is detached by setting the path-parent of that subtree's root to the splayed node, and this process repeats along the chain of path-parents until the overall tree root is reached. These updates ensure that the preferred paths remain disjoint and correctly chained, preserving the forest's partition into vertex-disjoint paths. Rotations in the underlying splay trees—specifically zig (single rotation) and zig-zag (double rotation)—are adapted to maintain the path structure while adjusting depths. A zig rotation rotates a node with its parent, updating parent pointers to reflect the new hierarchy, while a zig-zag involves two such rotations to bring a node up when it is a grandchild. Post-rotation, if the splay tree root changes, the path-parent pointer is transferred to the new root, and the forest's parent-child relationships are preserved by recalculating connections in the represented tree. In implementations supporting reversible paths, a lazy reverse flag is toggled during these rotations: when propagated, it swaps left and right subtrees (reversing the path order from top-to-bottom) and propagates to children; path-parent updates are handled consistently with the flag state to manage direction without disrupting chaining. This mechanism ensures that rotations do not violate the orientation of preferred paths. The core invariants maintained after path-parent updates and rotations are that preferred paths form valid, non-overlapping chains of preferred edges, and the entire structure represents an acyclic forest. Direction reversals are handled explicitly via the reverse flag during bottom-up access phases of operations like link or cut, flipping the path's logical order while deferring structural changes until splaying forces propagation; this avoids immediate recomputation and supports efficient aggregation along paths. For edge cases, single-node paths arise when a node lacks a preferred child, treated as a trivial splay tree with its path-parent directly to the parent path if applicable. Root changes occur during evert-like adjustments in access, where the target becomes the new root by reversing the path to it and updating all relevant path-parents. Cycles are prevented by pre-operation root checks using findroot, ensuring link operations only connect distinct trees.

Complexity Analysis

Amortized time bounds

The link/cut tree achieves amortized O(log n) time per operation for all primitive operations, including access, link, cut, findroot, and path aggregations, where n is the number of nodes in the forest. This bound holds for any sequence of m operations, yielding a total time of O(m log n). The analysis relies on the self-adjusting properties of the underlying splay trees used to represent preferred paths. The amortization arises from the access lemma of splay trees, which ensures that frequently accessed paths are restructured to have low depth, making subsequent operations on them inexpensive. A potential function, defined in terms of path depths and the costs of splaying, accounts for the restructuring overhead, charging excess costs to prior operations that benefit from the adjustments. This mechanism guarantees that the average cost per operation remains logarithmic, even though the splay tree's dynamic balancing adapts to access patterns without explicit balancing information. While individual operations can take O(n) time in the worst case due to deep paths before splaying, the amortized analysis smooths this over sequences of operations, ensuring the average remains O(log n). The structure is deterministic and does not require randomization for these guarantees, though variants using randomized search trees can achieve worst-case O(log n) per operation. In practice, the heuristics of splaying often yield performance superior to the theoretical amortized bound, particularly for workloads with locality in access patterns.

Heavy-light decomposition and potential method

The heavy-light decomposition is a technique used to analyze the amortized performance of link/cut trees by partitioning the edges of the underlying forest into heavy and light categories based on subtree sizes. An edge from a parent node pp to a child node vv is classified as heavy if the subtree size of vv, denoted size(v)\text{size}(v), satisfies size(v)>12size(p)\text{size}(v) > \frac{1}{2} \text{size}(p); otherwise, it is light. This classification ensures that each node has at most one heavy child, forming disjoint heavy paths (or chains) that connect nodes where subtree sizes decrease by less than half along the path. Light edges, by contrast, connect to subtrees at most half the size of their parent, leading to a doubling argument for path lengths: the light-depth of a node vv, defined as the number of light edges on the path from the root to vv, is at most ⌊log⁡2n⌋\lfloor \log_2 n \rfloor, where nn is the number of nodes in the tree. In link/cut trees, preferred paths—sequences of preferred edges maintained as auxiliary splay trees—mimic these heavy paths to achieve balanced decomposition. During an access operation on a node vv, the structure rotates and splays to make the path from the root to vv a single preferred path, potentially changing the status of several edges from non-preferred to preferred or vice versa. These changes primarily occur along light edges, as heavy edges tend to remain stable due to their large subtree sizes. Each time a light edge becomes preferred, the effective "layer" in the decomposition advances because the subtree size at least doubles compared to the previous light segment, ensuring that the total number of such changes per access is O(log⁡n)O(\log n). This bounds the structural modifications outside the splay operations themselves. The amortized analysis relies on a potential function that combines the splay tree potentials with the heavy-light structure. For each auxiliary splay tree TT, the potential is defined as Φ(T)=∑u∈Tlog⁡2s(u)\Phi(T) = \sum_{u \in T} \log_2 s(u), where s(u)s(u) is the size of the subtree rooted at uu within TT. The global potential Φ\Phi is the sum over all auxiliary trees. A key lemma from splay tree analysis states that the amortized cost of splaying a node xx in a tree rooted at rr is at most 3log⁡2s(r)−3log⁡2s(x)+13 \log_2 s(r) - 3 \log_2 s(x) + 1, where the potential drop during rotations offsets much of the actual work. In the context of access, the total splay costs along the path are thus amortized to O(log⁡n)O(\log n), as the initial and final potentials telescope across the O(log⁡n)O(\log n) preferred path segments affected by light edges. To formalize the overall bound, consider the changes in preferred edges during access: there are O(log⁡n)O(\log n) light edges traversed or modified, each triggering a constant number of structural updates (like setting path-parents), with costs covered by potential shifts of O(log⁡n)O(\log n) per light layer due to size doublings. Link and cut operations reduce to a constant number of accesses, preserving the bound. Without heavy-light decomposition, naive path maintenance could lead to O(log⁡2n)O(\log^2 n) time via unbalanced paths requiring O(log⁡n)O(\log n) changes each costing O(log⁡n)O(\log n) splays; the decomposition improves this to O(log⁡n)O(\log n) amortized by limiting path alterations to logarithmic in the light-depth. The total potential change per operation is thus bounded by O(log⁡n)O(\log n), proving the desired time complexity.

Applications

Dynamic connectivity in forests

Link/cut trees (LCTs) provide an efficient framework for maintaining dynamic connectivity in forests, where the structure consists of a collection of vertex-disjoint trees that evolve through edge insertions (links) and deletions (cuts). The core operations—link, cut, and findroot—enable the representation of these forests while supporting queries about whether two vertices belong to the same connected component. Specifically, the findroot operation exposes a vertex and traverses to its root in amortized O(log n) time, allowing connectivity checks between any pair of vertices by comparing their roots. For connectivity queries in such dynamic forests, LCTs mimic union-find structures but with additional path-handling capabilities. To determine if vertices u and v are connected, perform findroot(u) and findroot(v); if the roots match, they reside in the same tree. This supports union-find-like operations, such as merging components via link when adding an edge between roots of distinct trees, or splitting via cut when removing a tree edge. These operations maintain the forest invariant without explicit cycle detection beyond root comparison, achieving amortized O(log n) time per query or update. In the context of dynamic minimum spanning trees (MSTs), LCTs facilitate maintenance under edge weight changes in underlying graphs by treating the spanning forest as a dynamic tree collection. When an edge weight decreases, link it if it connects different components (verified via findroot); if it forms a cycle, cut the maximum-weight edge on the cycle path, identified through path aggregation in the LCT. For weight increases, cut the edge if it is in the MST and replace it with the minimum-weight alternative from incident non-tree edges, using level-based decomposition to bound search times. This approach yields polylogarithmic update times, such as O(log⁴ n) amortized for fully dynamic MSTs. Offline queries for dynamic connectivity can be processed in batches using LCTs by sequentially applying link and cut operations on the sequence of edge additions and deletions, tracking component roots after each update to answer connectivity at specific timestamps. This batch processing leverages the same findroot primitives to maintain and query components efficiently across the entire sequence. A representative application arises in network design, where LCTs handle node failures by cutting the subtree rooted at the failed node and relinking it to an alternative parent in the remaining forest, preserving connectivity while querying affected paths in O(log n) time per change. This enables resilient routing updates in dynamic communication networks modeled as forests.

Enhancements to graph algorithms

Link-cut trees enhance maximum flow algorithms by integrating with blocking flow methods, such as Dinic's algorithm, to efficiently manage dynamic level graphs during flow computations. In this approach, link-cut trees represent arborescences of shortest paths in the level graph, allowing link and cut operations to update the structure after augmenting paths are found, while path aggregates compute blocking flows in linear time relative to the number of edges. This results in an overall time complexity of O(VE log V) for computing maximum flow in a graph with V vertices and E edges, improving upon the standard Dinic's bound of O(V^2 E). For shortest path problems in dynamic graphs, link-cut trees facilitate the maintenance of distance aggregates along paths, enabling efficient queries and updates when edges are inserted or deleted. By representing the graph's spanning trees or path decompositions, the structure supports operations like accessing the sum of edge weights (distances) from a node to the root in amortized O(log V) time, which is crucial for recomputing affected paths after structural changes. This is particularly useful in scenarios where the graph evolves through link and cut operations, allowing real-time adjustments without full recomputation. Beyond flow and paths, link-cut trees find application in computational geometry for maintaining dynamic Voronoi diagrams, where variants like grappa trees—adapted from the link-cut framework—represent the diagram's dual tree structure to handle incremental site insertions. In these settings, the trees support link and cut to update cell boundaries and query nearest-site distances efficiently, achieving polylogarithmic time per update for n sites in the plane. Such uses extend to other domains involving evolving topologies, though specific integrations in game-theoretic network models remain exploratory. Despite these enhancements, link-cut trees are most effective for tree-like structures or graphs with low treewidth, where the forest representation aligns closely with the problem topology. For denser general graphs, they complement structures like the Holm-de Lichtenberg-Thorup (HDT) framework, which handles arbitrary connectivity via multi-level spanning forests, as link-cut trees alone cannot directly manage cycles without additional layering. Experimental comparisons confirm that while link-cut trees excel in sparse, dynamic tree operations, HDT variants offer better scalability for fully dynamic undirected graphs with higher edge densities.
Add your contribution
Related Hubs
User Avatar
No comments yet.