Link/cut tree
| Splay tree | |||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Type | tree | ||||||||||||||
| Invented | 1982 | ||||||||||||||
| Invented by | Daniel Dominic Sleator and Robert Endre Tarjan | ||||||||||||||
| |||||||||||||||
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. Link-Cut trees divide a 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. The overall structure is thus a forest of trees. The underlying represented tree is not modified. 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
See also
Further reading
- Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1145/800076.802464, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with
|doi=10.1145/800076.802464instead. - Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1145/3828.3835, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with
|doi=10.1145/3828.3835instead. - Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1145/76359.76368, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with
|doi=10.1145/76359.76368instead. — Application to min-cost circulation - http://compgeom.cs.uiuc.edu/~jeffe/teaching/datastructures/2006/notes/07-linkcut.pdf
 | This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it. |