6533b7d7fe1ef96bd1268ccd
RESEARCH PRODUCT
A distance metric on binary trees using lattice-theoretic measures
Jean Marcel Pallosubject
Binary treeData structureRandom binary treeComputer Science ApplicationsTheoretical Computer ScienceHeight functionCombinatoricsTree structureLattice (order)Signal ProcessingMetric (mathematics)Metric treeComputer Science::DatabasesInformation SystemsMathematicsdescription
A so called height function which is a strictly antitone supervaluation is defined on binary trees. Via lattice-theoretic results and using the height function, we can define a distance metric on binary trees of size n which can be computed in expected time O(n 3/2 )
| year | journal | country | edition | language |
|---|---|---|---|---|
| 1990-04-01 | Information Processing Letters |