Link/cut tree
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.
The nodes in the auxiliary data structure are ordered by their depth in the corresponding represented tree.
It has uses in solving a variety of network flow problems and to jive data sets.
This pointer is stored in the root of the auxiliary tree representing the path.
We then disconnect the right subtree of v, which is every node that came below it on the previous preferred path.
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 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.
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.
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).
Accessing v breaks the preferred path below v as well, but that subtree maintains its connection to v through its path-parent pointer.
Adding w as a left child effectively makes it the parent of v in the represented tree.
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.
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.
Access makes use of splaying, which we know has an O(log n) amortized upper bound.
This technique calls an edge heavy or light depending on the number of nodes in the subtree.
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.
, so if we can show that each preferred child change has cost O(1) amortized we can bound the access operation at
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
Link/cut trees can be used to solve the dynamic connectivity problem for acyclic graphs.
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
