On the shape of the fringe of various types of random trees

We analyze a fringe tree parameter w in a variety of settings, utilizing a variety of methods from the analysis of algorithms and data structures. Given a tree t and one of its leaves a, the w(t, a) parameter denotes the number of internal nodes in the subtree rooted at a's father. The closely related w?(t, a) parameter denotes the number of leaves, excluding a, in the subtree rooted at a's father. We define the cumulative w parameter as W(t) = Σ_aw(t, a), i.e. as the sum of w(t, a) over all leaves a of t. The w parameter not only plays an important rôle in the analysis of the Lempel–Ziv '77 data compression algorithm, but it is captivating from a combinatorial viewpoint too. In this report, we determine the asymptotic behavior of the w and W parameters on a variety of types of trees. In particular, we analyze simply generated trees, recursive trees, binary search trees, digital search trees, tries and Patricia tries. The final section of this report briefly summarizes and improves the previously known results about the w? parameter's behavior on tries and suffix trees, originally published in one author's thesis (see Analysis of the multiplicity matching parameter in suffix trees. Ph.D. Thesis, Purdue University, West Lafayette, IN, U.S.A., May 2005; Discrete Math. Theoret. Comput. Sci. 2005; AD :307–322; IEEE Trans. Inform. Theory 2007; 53 :1799–1813). This survey of new results about the w parameter is very instructive since a variety of different combinatorial methods are used in tandem to carry out the analysis. Copyright © 2008 John Wiley & Sons, Ltd.