𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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

✍ Scribed by Michael Drmota; Bernhard Gittenberger; Alois Panholzer; Helmut Prodinger; Mark Daniel Ward

Publisher
John Wiley and Sons
Year
2009
Tongue
English
Weight
304 KB
Volume
32
Category
Article
ISSN
0170-4214

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

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) = Ξ£~a~w(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.

πŸ“œ SIMILAR VOLUMES

On the profile of random trees
On the profile of random trees
✍ Michael Drmota; Bernhard Gittenberger πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 302 KB πŸ‘ 2 views

Let T be a plane rooted tree with n nodes which is regarded as family tree of a Galton-Watson branching process conditioned on the total progeny. The profile of the tree ' may be described by the number of nodes or the number of leaves in layer t n , respectively. It is shown that these two processe

On the log-product of the subtree-sizes
On the log-product of the subtree-sizes of random trees
✍ A. Meir; J. W. Moon πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 190 KB πŸ‘ 2 views

We determine the asymptotic behavior of the expected value and the variance of the log-product of the subtree-sizes of trees T belonging to simply generated families of n

On the average shape of simply generated
On the average shape of simply generated families of trees
✍ Peter Kirschenhofer πŸ“‚ Article πŸ“… 1983 πŸ› John Wiley and Sons 🌐 English βš– 377 KB

## Abstract This paper deals with the limiting distribution of the level number of the jth leaf of a planted plane tree (where leaves are enumerated from left to right) for the so‐called β€œsimply generated families” introduced by Meir and Moon. The mathematical apparatus is determined by the idea of

On the Total Heights of Random Rooted Bi
On the Total Heights of Random Rooted Binary Trees
✍ L. Takacs πŸ“‚ Article πŸ“… 1994 πŸ› Elsevier Science 🌐 English βš– 306 KB

Denote by \(S_{n}\) the set of all distinct rooted binary trees with \(n\) unlabeled vertices. Define \(\sigma_{n}\) as a total height of a tree chosen at random in the set \(S_{n}\), assuming that all the possible choices are equally probable. The total height of a tree is defined as the sum of the

On the location of a tree-shaped facilit
On the location of a tree-shaped facility
✍ Kim, Tae Ung; Lowe, Timothy J.; Tamir, Arie; Ward, James E. πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 769 KB

This paper considers the problem of locating a central facility on a tree network. The central facility takes the form of a subtree of the network and provides service to several demand points located at the nodes of the network. Two types of costs are involved in evaluating a given facility selecti