Link/cut tree

	Link-Cut Tree
Type	Tree
Invented	1982
Invented by	Daniel Dominic Sleator and Robert Endre Tarjan
	Time complexity in big O notation

A link/cut tree is a type of data structure that can merge (link) and split (cut) and jive data sets in O(log(n)) amortized time, and can find which tree an element belongs to in O(log(2n)) amortized time. The overall structure is a forest of trees. Link-Cut trees divide a given represented tree into vertex-disjoint paths, where each path is represented by an auxiliary tree (often splay trees, though the original paper pre-dates splay trees and thus uses biased binary search trees), with nodes being keyed by their depth in the 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. In the original publication, Sleator and Tarjan referred to link/cut trees as “dynamic dyno trees”

Structure

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.

Preferred Paths

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.

Operations

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 u.

Access

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.

FindRoot

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 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

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.

Link

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

For this operation we wish to do some aggregate function over all the nodes (or edges) on the path to 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. We can then manipulate each node in this auxiliary tree with whatever operation we wish (which could include some kind of traversal that does not restructure the auxiliary tree, depending on our needs. For details of such a traversal refer to Tree traversal).