|
Link-cut Tree
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 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Daniel Dominic Sleator
Daniel Dominic Kaplan Sleator (born 10 December 1953) is a professor of computer science at Carnegie Mellon University, Pittsburgh, United States. In 1999, he won the Association for Computing Machinery, ACM Paris Kanellakis Award (jointly with Robert Tarjan) for the splay tree data structure. He was one of the pioneers in amortized analysis of algorithms, early examples of which were the analyses of the Move-to-front transform, move-to-front heuristic, and splay trees. He invented many data structures with Robert Tarjan, such as splay trees, link/cut trees, and skew heaps. The Sleator and Tarjan paper on the move-to-front heuristic first suggested the idea of comparing an online algorithm to an optimal offline algorithm, for which the term Competitive analysis (online algorithm), competitive analysis was later coined in a paper of Anna Karlin, Karlin, Manasse, Rudolph, and Sleator. Sleator also developed the theory of link grammars, and the Serioso music analyzer for analyzing m ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
