Structural complexity of random binary trees
John C. Kieffer, En‐hui Yang, Wojciech Szpankowski · 2009
For each positive integer n, let Tnbe a random rooted full binary tree having 2n-1 vertices. We can view H(Tn), the entropy of Tn, as a measure of the structural complexity of tree Tnin the sense that approximately H(Tn) bits suffice to construct Tn. We analyze some random binary tree sequences (Tn: n = 1,2...) for which the normalized entropies H(Tn)/n converge to a limit as n rarr infin, as well as some other sequences (Tn) in which the normalized entropies fail to converge.