| http://dbpedia.org/ontology/abstract
|
In discrete mathematics and theoretical co … 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.omputing the rotation distance is unknown.
|
| http://dbpedia.org/ontology/thumbnail
|
http://commons.wikimedia.org/wiki/Special:FilePath/BinaryTreeRotations.svg?width=300 +
|
| http://dbpedia.org/ontology/wikiPageID
|
62539802
|
| http://dbpedia.org/ontology/wikiPageLength
|
14118
|
| http://dbpedia.org/ontology/wikiPageRevisionID
|
1117724896
|
| http://dbpedia.org/ontology/wikiPageWikiLink
|
http://dbpedia.org/resource/File:BinaryTreeRotations.svg +
, http://dbpedia.org/resource/NP_%28complexity%29 +
, http://dbpedia.org/resource/Associahedron +
, http://dbpedia.org/resource/Triangulation_%28geometry%29 +
, http://dbpedia.org/resource/Data_structure +
, http://dbpedia.org/resource/Euclidean_plane +
, http://dbpedia.org/resource/Category:Binary_trees +
, http://dbpedia.org/resource/Computational_complexity +
, http://dbpedia.org/resource/Approximation_ratio +
, http://dbpedia.org/resource/Tree_rotation +
, http://dbpedia.org/resource/Approximation_algorithm +
, http://dbpedia.org/resource/Hyperbolic_geometry +
, http://dbpedia.org/resource/NP-complete +
, http://dbpedia.org/resource/Binary_search_tree +
, http://dbpedia.org/resource/Derick_Wood +
, http://dbpedia.org/resource/Self-balancing_binary_search_tree +
, http://dbpedia.org/resource/Category:Triangulation_%28geometry%29 +
, http://dbpedia.org/resource/Fan_triangulation +
, http://dbpedia.org/resource/Exponential_time +
, http://dbpedia.org/resource/Theoretical_computer_science +
, http://dbpedia.org/resource/Reconfiguration +
, http://dbpedia.org/resource/Parameterized_complexity +
, http://dbpedia.org/resource/File:Flip_graphs.svg +
, http://dbpedia.org/resource/Manifold +
, http://dbpedia.org/resource/Convex_polygon +
, http://dbpedia.org/resource/Polygon +
, http://dbpedia.org/resource/Flip_distance +
, http://dbpedia.org/resource/Shortest_path_problem +
, http://dbpedia.org/resource/Discrete_mathematics +
, http://dbpedia.org/resource/Inorder_traversal +
, http://dbpedia.org/resource/Polynomial_time +
, http://dbpedia.org/resource/Flip_graph +
, http://dbpedia.org/resource/Category:Reconfiguration +
, http://dbpedia.org/resource/Complexity_class +
, http://dbpedia.org/resource/Tetrahedron +
, http://dbpedia.org/resource/Convex_polyhedron +
, http://dbpedia.org/resource/Binary_tree +
, http://dbpedia.org/resource/Hamiltonian_circuit +
|
| http://dbpedia.org/property/wikiPageUsesTemplate
|
http://dbpedia.org/resource/Template:Unsolved +
, http://dbpedia.org/resource/Template:Math +
, http://dbpedia.org/resource/Template:R +
, http://dbpedia.org/resource/Template:Harvtxt +
, http://dbpedia.org/resource/Template:Reflist +
, http://dbpedia.org/resource/Template:Mvar +
|
| http://purl.org/dc/terms/subject
|
http://dbpedia.org/resource/Category:Reconfiguration +
, http://dbpedia.org/resource/Category:Binary_trees +
, http://dbpedia.org/resource/Category:Triangulation_%28geometry%29 +
|
| http://www.w3.org/ns/prov#wasDerivedFrom
|
http://en.wikipedia.org/wiki/Rotation_distance?oldid=1117724896&ns=0 +
|
| http://xmlns.com/foaf/0.1/depiction
|
http://commons.wikimedia.org/wiki/Special:FilePath/Flip_graphs.svg +
, http://commons.wikimedia.org/wiki/Special:FilePath/BinaryTreeRotations.svg +
|
| http://xmlns.com/foaf/0.1/isPrimaryTopicOf
|
http://en.wikipedia.org/wiki/Rotation_distance +
|
| owl:sameAs |
http://dbpedia.org/resource/Rotation_distance +
, https://global.dbpedia.org/id/Byzcy +
, http://www.wikidata.org/entity/Q85797976 +
|
| rdfs:comment |
In discrete mathematics and theoretical co … 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.the for triangulations of convex polygons.
|
| rdfs:label |
Rotation distance
|
