About: Rotation distance

An Entity of Type: Thing, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

In discrete mathematics and theoretical computer science, the rotation distance between two binary trees with the same number of nodes is the minimum number of tree rotations needed to reconfigure one tree into another. Because of a combinatorial equivalence between binary trees and triangulations of convex polygons, rotation distance is equivalent to the for triangulations of convex polygons.

thumbnail
Property Value
dbo:abstract
  • In discrete mathematics and theoretical computer science, the rotation distance between two binary trees with the same number of nodes is the minimum number of tree rotations needed to reconfigure one tree into another. Because of a combinatorial equivalence between binary trees and triangulations of convex polygons, rotation distance is equivalent to the for triangulations of convex polygons. Rotation distance was first defined by Karel Čulík II and Derick Wood in 1982. Every two n-node binary trees have rotation distance at most 2n − 6, and some pairs of trees have exactly this distance. The computational complexity of computing the rotation distance is unknown. (en)
dbo:thumbnail
dbo:wikiPageID
  • 62539802 (xsd:integer)
dbo:wikiPageLength
  • 14118 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 1117724896 (xsd:integer)
dbo:wikiPageWikiLink
dbp:wikiPageUsesTemplate
dcterms:subject
rdfs:comment
  • In discrete mathematics and theoretical computer science, the rotation distance between two binary trees with the same number of nodes is the minimum number of tree rotations needed to reconfigure one tree into another. Because of a combinatorial equivalence between binary trees and triangulations of convex polygons, rotation distance is equivalent to the for triangulations of convex polygons. (en)
rdfs:label
  • Rotation distance (en)
owl:sameAs
prov:wasDerivedFrom
foaf:depiction
foaf:isPrimaryTopicOf
is dbo:wikiPageWikiLink of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License