Link-Cut Trees in Java: Dynamic Tree Connectivity

While Heavy-Light Decomposition (HLD) is excellent for static trees, it struggles with dynamic trees where edges are frequently added or removed. Link-Cut Trees (LCT) are the solution to this problem, allowing us to maintain a forest of trees and perform path operations in amortized $O(\log N)$ time.

The Core Concept: Preferred Paths and Splay Trees

LCT decomposes each tree in the forest into a set of disjoint paths called preferred paths. Each preferred path is stored in an auxiliary data structure—typically a Splay Tree—where nodes are keyed by their depth in the original tree.

1. Access(v): The fundamental operation that makes the path from the root to node $v$ a preferred path.
2. Link(u, v): Adds an edge between node $u$ and node $v$, connecting two previously disjoint trees.
3. Cut(v): Removes the edge between node $v$ and its parent, splitting a tree into two.
4. FindRoot(v): Identifies the root of the tree containing node $v$, useful for checking connectivity.

Link-Cut Tree Implementation in Java (Simplified)

public class LinkCutTree {
    static class Node {
        Node left, right, parent;
        boolean reverse;
        int value, sum; // Example for path sum queries

        Node(int v) {
            this.value = this.sum = v;
        }

        boolean isRoot() {
            return parent == null || (parent.left != this && parent.right != this);
        }

        void pushDown() {
            if (reverse) {
                reverse = false;
                Node temp = left; left = right; right = temp;
                if (left != null) left.reverse = !left.reverse;
                if (right != null) right.reverse = !right.reverse;
            }
        }

        void pushUp() {
            sum = value;
            if (left != null) sum += left.sum;
            if (right != null) sum += right.sum;
        }
    }

    private void rotate(Node x) {
        Node y = x.parent, z = y.parent;
        if (!y.isRoot()) {
            if (z.left == y) z.left = x;
            else z.right = x;
        }
        x.parent = z;
        if (y.left == x) {
            y.left = x.right;
            if (x.right != null) x.right.parent = y;
            x.right = y;
        } else {
            y.right = x.left;
            if (x.left != null) x.left.parent = y;
            x.left = y;
        }
        y.parent = x;
        y.pushUp();
        x.pushUp();
    }

    private void splay(Node x) {
        while (!x.isRoot()) {
            Node y = x.parent, z = y.parent;
            if (!y.isRoot()) y.pushDown();
            x.pushDown();
            if (!y.isRoot()) {
                if ((z.left == y) == (y.left == x)) rotate(y);
                else rotate(x);
            }
            rotate(x);
        }
        x.pushDown();
    }

    public void access(Node x) {
        Node last = null;
        for (Node curr = x; curr != null; curr = curr.parent) {
            splay(curr);
            curr.right = last;
            curr.pushUp();
            last = curr;
        }
        splay(x);
    }

    public void makeRoot(Node x) {
        access(x);
        x.reverse = !x.reverse;
        x.pushDown();
    }

    public void link(Node x, Node y) {
        makeRoot(x);
        x.parent = y;
    }

    public void cut(Node x, Node y) {
        makeRoot(x);
        access(y);
        if (y.left == x && x.right == null) {
            y.left = x.parent = null;
            y.pushUp();
        }
    }
}

Link-Cut Tree vs. Heavy-Light Decomposition

Real-World Applications

1. Network Topology: Managing dynamic connections in a network and finding shortest paths or capacities.
2. Dynamic Graph Algorithms: Solving problems like dynamic Minimum Spanning Tree (MST).
3. Cluster Management: Tracking connectivity in distributed systems where nodes and links are volatile.

Summary

The Link-Cut Tree is one of the most sophisticated data structures in computer science. By combining the flexibility of Splay Trees with the concept of preferred paths, it achieves near-optimal performance for dynamic tree operations. While its implementation is a significant challenge, its ability to handle structural changes in logarithmic time makes it an invaluable tool for high-performance systems.