Binary trees equipped with semivaluations

Abstract

We consider the set T_n 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 T_n are studied and we show that every T_n has a sublattice isomorphic to T_n-1 and prove that T_n 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.

Keywords:Binary tree; lattice; semivaluation

Quaestiones Mathematicae 30(2007), 123–131