Rainer Kemp: On the Representation of Simply Generated Trees by Leftist Trees

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

Bibliography

Kem99a

Rainer Kemp.
On leftist simply generated trees.
J. Autom. Lang. Comb., 4(4):313-331, 1999.

Kem99b

Rainer Kemp.
A one-to-one correspondence between a class of leftist trees and binary trees.
Inform. Process. Lett., 71(3-4):97-105, 1999.

Back to the Index