About: Link/cut tree

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Link/cut tree Goto Sponge NotDistinct Permalink

An Entity of Type : yago:Structure105726345, within Data Space : dbpedia.demo.openlinksw.com associated with source document(s)
QRcode icon

http://dbpedia.demo.openlinksw.com/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FLink%2Fcut_tree&invfp=IFP_OFF&sas=SAME_AS_OFF

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.

Attributes	Values
rdf:type	yago:Abstraction100002137 yago:Arrangement105726596 yago:Cognition100023271 yago:DataStructure105728493 yago:PsychologicalFeature100023100 building yago:Structure105726345
rdfs:label	Link/cut tree (en)
rdfs:comment	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. (en)
foaf:depiction
dcterms:subject	Amortized data structures Trees (data structures)
Wikipage page ID	9328337 (xsd:integer)
Wikipage revision ID	1113988896 (xsd:integer)
Link from a Wikipage to another Wikipage	Amortized data structures Robert Tarjan Rooted tree Euler tour tree Dynamic connectivity Maximum flow problem Logarithm Time complexity Tree (graph theory) Data structure Potential method Amortized analysis Daniel Sleator Dinic's algorithm Journal of the ACM Trees (data structures) Big O notation Splay tree Forest (graph theory) Parent pointer tree Tango Trees Daniel Dominic Sleator Robert Endre Tarjan Splay trees
Link from a Wikipage to an external page	https://jeffe.cs.illinois.edu/teaching/datastructures/2006/notes/07-linkcut.pdf http://courses.csail.mit.edu/6.851/spring12/scribe/L19.pdf https://www.cs.cmu.edu/~sleator/papers/dynamic-trees.pdf https://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf
sameAs	Link/cut tree Link/cut tree Link/cut tree
dbp:wikiPageUsesTemplate	dbt:CS-Trees dbt:Cite_book dbt:Cite_journal dbt:Frac dbt:Infobox dbt:Main dbt:No_footnotes dbt:Refbegin dbt:Refend dbt:Tmath dbt:Use_dmy_dates dbt:Aligned_table
thumbnail	wiki-commons:Special:FilePath/LinkCutAccess1.png?width=300
above	Link/cut tree (en)
data	1982 (xsd:integer) Tree (graph theory) Daniel Dominic Sleator Robert Endre Tarjan (en)
header	Time complexity in big O notation (en)
label	Type (en) Invented (en) Invented by (en)
headerstyle	background:#D6D6F5 (en)
has abstract	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 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 split (cut) in O(log(n)) amortized time. Link/cut trees divide each tree in the represented forest into vertex-disjoint paths, where each path is represented by an auxiliary data structure (often splay trees, though the original paper predates splay trees and thus uses biased binary search trees). The nodes in the auxiliary data structure are ordered by their depth in the corresponding 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 and to jive data sets. In the original publication, Sleator and Tarjan referred to link/cut trees as "dynamic trees", or "dynamic dyno trees". (en)
gold:hypernym	Structure
prov:wasDerivedFrom	wikipedia-en:Link/cut_tree?oldid=1113988896&ns=0
page length (characters) of wiki page	16642 (xsd:nonNegativeInteger)
foaf:isPrimaryTopicOf	wikipedia-en:Link/cut_tree
is Link from a Wikipage to another Wikipage of	List of data structures Heavy path decomposition Daniel Sleator Splay tree Top tree Euler tour technique LCT Link-cut tree Link cut tree Dynamic tree Dynamic trees
is Wikipage redirect of	Link-cut tree Link cut tree Dynamic tree Dynamic trees
is foaf:primaryTopic of	wikipedia-en:Link/cut_tree

Faceted Search & Find service v1.17_git139 as of Feb 29 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (378 GB total memory, 56 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software