Binary trees equipped with semivaluations

We consider the set Tn of binary trees with n leaves. This set can be ordered by the so-called "imbalance" order, where two trees are related in the order iff the second is less "balanced" than the first. This order forms a lattice and has been applied by Parker and Ram to obtain improvements of the Huffman algorithm for file compressions. Our interest in this lattice stems from its application to binary decision trees. Binary decision trees form a crucial tool for algorithmic time analysis. The lattice properties of Tn are studied and we show that every Tn has a sublattice isomorphic to T n−1 and prove that Tn is generated by T n−1. Also we show that the distance from any node of a binary tree to the root is a join co-valuation. Since this distance reflects the running time for the algorithm, we obtain that this complexity measure satisfies a generalized valuation property.