9502325T
Faculty of Science
School of Mathematics / Abstract
Increasing trees are labelled rooted trees in which labels along any branch from the root appear in increasing order. They have numerous applications in tree representations of permutations, data structures in computer science and probabilistic models in a multitude of problems. We use a generating function approach for the computation of parameters arising from such trees. The generating functions for some parameters are shown to be related to ordinary differential equations. Singularity analysis is then used to analyze several parameters of the trees asymptotically.Various classes of trees are considered. Parameters such as depth and path length for heap ordered trees have been analyzed in [35]. We follow a similar approach to determine grand averages for such trees. The model is that p of the n nodes are labelled at random in ôn
p(ways, and the characteristic parameters depend on these labelled nodes. Also, we will
attempt to look at the limiting distributions involved. Often, when they are Gaussian, Hwang's quasi power theorem, from [18], can be employed. Spanning tree size and the Wiener index for binary search trees have been computed in [33]. The Wiener index is the sum of all distances between pairs of nodes in a tree. Arelated parameter of interest is the Steiner distance which generalises, to sets of k nodes, the Wiener index (k=2). Furthermore, the distribution of the size of the ancestor-tree and of the induced spanning subtree for random trees is presented in [30]. The same procedure is followed to obtain the Steiner distance for heap ordered trees and for other varieties of increasing trees.
| Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:wits/oai:wiredspace.wits.ac.za:10539/1473 |
| Date | 26 October 2006 |
| Creators | Morris, Katherine |
| Source Sets | South African National ETD Portal |
| Language | English |
| Detected Language | English |
| Type | Thesis |
| Format | 848454 bytes, application/pdf, application/pdf |
Page generated in 0.0015 seconds