A distance metric on binary trees using lattice-theoretic measures

DOI10.1016/0020-0190(90)90088-FzbMATH Open0695.68017MaRDI QIDQ910191FDOQ910191

N. E. Zubov

Publication date: 1990

Published in: Information Processing Letters (Search for Journal in Brave)

Recommendations

• Distances between rooted trees
• The agreement metric for labeled binary trees
• An \(O(n \log n)\) time algorithm for computing the path-length distance between trees
• A metric for rooted trees with unlabeled vertices based on nested parentheses
• scientific article; zbMATH DE number 1113982

zbMATH Keywords

binary treesdistance metricrotation lattice

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Lattices (06B99)

Cites Work

• The average height of binary trees and other simple trees
• Metrics on partially ordered sets - a survey
• Enumerating, Ranking and Unranking Binary Trees
• Path length in the covering graph of a lattice
• On the upper bound on the rotation distance of binary trees
• Metrics on spaces of finite trees
• Height on posets and graphs

Cited In (13)

• A metric for rooted trees with unlabeled vertices based on nested parentheses
• Metrics on the multirubric lattice of a rubricator tree
• A tight bound on approximating arbitrary metrics by tree metrics
• On the rotation distance between binary trees
• Two shortest path metrics on well-formed parentheses strings
• The phagocyte lattice of Dyck words
• A tight bound on approximating arbitrary metrics by tree metrics
• Matchings In Three Catalan Lattices
• On the intercluster distance of a tree metric
• Computing the Gromov-Hausdorff Distance for Metric Trees
• An algorithm to compute the möbius function of the rotation lattice of binary trees
• Extremal distances for subtree transfer operations in binary trees
• The higher Stasheff‐Tamari posets

This page was built for publication: A distance metric on binary trees using lattice-theoretic measures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q910191)