Fractal compression rate curves in lossless compression of balanced trees

Let α be an integer ≥ 2. We define a finite rooted oriented tree to be α-balanced if (1) there is no vertex with > α children, (2) for each vertex having exactly α children, the subtrees rooted at these children have numbers of leaves differing by at most 1, and (3) each child of each internal vertex with <; α children is a leaf. For each n ≥ 1, let H_α(n) be logarithm to base two of the number of α-balanced trees having n leaves, which is roughly the codeword length needed to losslessly compress these trees via fixed-length binary codewords. Let {{x}} J denote the fractional part of x. The compression rate curve C_α is defined to be the set of limit points of the set of points of form ({{log_α n}}, H_α(n)/n). Two results about C_α are presented. The first result is that C_α is the graph of a unique real-valued nonconstant continuous function defined on [0,1]. The second result is that C_α is a 2-D fractal which is the attractor of an iterated function system S(α) consisting of α piecewise contractive 2-D mappings. For α = 2, 3, 4, we illustrate how a large number of points on C_α can be rapidly generated via S(α).