Link-cut tree is a data structure invented by Sleator and Tarjan, which supports various operations and queries on a $n$-node forest in time $O(\log n)$. (For example, operation link combines two trees in the forest into one, while operation cut divide a tree in the forest into two trees.)

Several applications are known by using link-cut trees, and here I'm particularly interested in Goodrich's separator decomposition, which given a $n$-node plane graph $G$ one can obtain a corresponding binary tree where nodes are subgraphs of $G$, and the children of a node $H$ are the subgraphs of $H$ divided by the separator on $H$. Such a decomposition can be easily constructed in $O(n \log n)$ time (since a separator can be found in $O(n)$ time, and since the separator divides the graph so balanced, after $O(\log n)$ level of separations the leaves of the tree are of size $O(1)$). The main contribution of Goodrich is that he can construct such a decomposition in time $O(n)$, by maintaining and reusing the data structures used for finding separators in each level.

One of the data structures being used in the construction, is indeed the link-cut tree. In page 7 of the paper by Goodrich, he claimed that the initialization of the link-cut tree can be done in time $O(n)$. While I go through all the papers cited there, it seems to me that if we construct a link-cut tree via operation link, it takes time $O(n \log n)$ in total.

Do I misunderstand something? Can the initialization of a link-cut tree be done in time $O(n)$?


2 Answers 2


Many thanks to Hsueh-I Lu, my teacher in National Taiwan University, who provides the following solution.

It turns out that the answer is rather simple; in the initialization of a data structure, we don't have to construct the structure by the queries and operations it supports. Of course, we cannot perform queries during the construction like we usually do if we build the tree by link operation; but in this separator decomposition application we don't need it.

That is to say, in the application to the separator decomposition, when we have to construct the link-cut trees L(T) for the spanning tree T on input graph G, instead of computing the structures and values of the trees L(T) by link operation, we directly compute the heavy-light path decomposition of the tree T, and construct the corresponding binary tree structure for each paths, and gluing the binary trees according to the path decomposition. All the steps can be done in linear time.

For each necessary values on the nodes of L(T), since each value can be compute from T in linear time (in this application), instead of assigning values on binary tree structures and updating when gluing the trees, we assign the precomputed values directly onto the nodes of the final link-cut trees L(T). There are only a constant type of values need to be assigned, and again this can be done in linear time.


Chapter 5.1 in "Data Structures and Network Algorithms", which is ref. 43 in the paper you cited, seems like it might have the answer:


...In discussing this problem we shall use 'm' to denote the number of operations and 'n' to denote the numebr of vertices (maketree operations). One way to solve this problem is to store with each vertex its parent and its cost. With this representation each maketree, link, or cut operation takes O(1) time, and each findroot, findcost, or addcost operation takes time proportiatonl to the depth of the input vertex, which is O(n)...

Several more successive pages are available in the preview.

  • $\begingroup$ This chapter is pretty much similar to the link-cut tree paper itself; see the last three paragraph in p.365 of citeseerx.ist.psu.edu/viewdoc/… $\endgroup$ Nov 24, 2010 at 14:37
  • $\begingroup$ Since later in the algorithm the operations which cost $O(n)$ are essential, this naive implementation can not be used. I'm looking for the main implementation introduced in the same paper, which have a time bound $O(\log n)$ for each operation. $\endgroup$ Nov 24, 2010 at 14:40
  • $\begingroup$ i was unable to find any other information to backup this claim, so i think they must either be, a. referring to this 'naive' construction (perhaps mistakenly), b. referring to the 'make_tree' operation which simply initializes a new one-node tree, or perhaps c. conflating the two. otherwise, barring additional evidence i'm inclined to think that you are correct. $\endgroup$
    – s8soj3o289
    Nov 24, 2010 at 22:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.