Title :
Structural complexity of random binary trees
Author :
Kieffer, J.C. ; Yang, E.-H. ; Szpankowski, W.
Author_Institution :
ECE Dept., Univ. of Minnesota, Minneapolis, MN, USA
fDate :
June 28 2009-July 3 2009
Abstract :
For each positive integer n, let Tn be 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 Tn in 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.
Keywords :
computational complexity; entropy; trees (mathematics); entropy; random binary tree sequences; structural complexity; Binary trees; Bioinformatics; Computer science; Data structures; Entropy; Failure analysis; Genetic communication; Information theory; Probability distribution; Sequences;
Conference_Titel :
Information Theory, 2009. ISIT 2009. IEEE International Symposium on
Conference_Location :
Seoul
Print_ISBN :
978-1-4244-4312-3
Electronic_ISBN :
978-1-4244-4313-0
DOI :
10.1109/ISIT.2009.5205704