Hostname: page-component-78c5997874-m6dg7 Total loading time: 0 Render date: 2024-11-05T11:01:31.120Z Has data issue: false hasContentIssue false
  • English
  • Français

On Some Parameters in Heap Ordered Trees

Published online by Cambridge University Press:  24 September 2004

KATE MORRIS ,
ALOIS PANHOLZER  and
HELMUT PRODINGER
KATE MORRIS
Affiliation:
The John Knopfmacher Centre for Applicable Analysis and Number Theory, School of Mathematics, University of the Witwatersrand, P. O. Wits, 2050 Johannesburg, South Africa (e-mail: [email protected], [email protected])
ALOIS PANHOLZER
Affiliation:
Institut für Algebra und Computermathematik, TU Wien, Wiedner Hauptstr. 8–10, 1040 Wien, Austria (e-mail: [email protected])
HELMUT PRODINGER
Affiliation:
The John Knopfmacher Centre for Applicable Analysis and Number Theory, School of Mathematics, University of the Witwatersrand, P. O. Wits, 2050 Johannesburg, South Africa (e-mail: [email protected], [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Heap ordered trees are planted plane trees, labelled in such a way that the labels always increase from the root to a leaf. We study two parameters, assuming that $p$ of the $n$ nodes are selected at random: the size of the ancestor tree of these nodes and the smallest subtree generated by these nodes. We compute expectation, variance, and also the Gaussian limit distribution, the latter as an application of Hwang's quasi-power theorem.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 13 , Issue 4-5 , July 2004 , pp. 677 - 696
Copyright
© 2004 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)