Each simply generated family of trees is unambiguously associated with another simply generated family of trees such that the total weight of the trees with leaves in is equal to the total weight of the leftist trees with leaves in . This interrelation induces a partition on the set of trees with leaves appearing in such that each block is associated with exactly one leftist tree with leaves. Given (resp. ), we shall establish an explicit transformation defined on the trees for the construction of (resp. ). The presented approach implies a compressed representation of a simply generated family of trees with leaves by leftist simply generated trees with the same number of leaves.
Back to the Index