Binary trees and topologies on binary trees.
by
Homeira Pajoohesh
University College Cork
Coauthors: Michel Schellekens

We consider a binary tree as a Ú-semilattice. Decision trees are binary trees representing the comparisons carried out during the computation of a comparison-based algorithm. The distance from the root ("input") to a leaf ("output") gives the comparison time for the algorithm (i.e. the total number of comparisons) to compute the output corresponding to the given leaf. We show that the distance from any node of a binary tree to the root is a join co-valuation and study the induced topologies by this semivaluation.

Date received: June 15, 2004