Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich. mehr Informationen...
Ergebnis 23 von 38
Open Access
Weighted height of random trees
Acta informatica, 2008-06, Vol.45 (4), p.237-277
2008
Volltextzugriff (PDF)

Details

Autor(en) / Beteiligte
Titel
Weighted height of random trees
Ist Teil von
  • Acta informatica, 2008-06, Vol.45 (4), p.237-277
Ort / Verlag
Berlin/Heidelberg: Springer-Verlag
Erscheinungsjahr
2008
Quelle
Alma/SFX Local Collection
Beschreibungen/Notizen
  • We consider a model of random trees similar to the split trees of Devroye (SIAM J. Comput. 28(2), 409–432, 1998) in which a set of items is recursively partitioned. Our model allows for more flexibility in the choice of the partitioning procedure, and has weighted edges. We prove that for this model, the height H n of a random tree is asymptotic to c log n in probability for a constant c that is uniquely characterized in terms of multivariate large deviations rate functions. This extension permits us to obtain the height of pebbled tries, pebbled ternary search tries, d -ary pyramids, and to study geometric properties of partitions generated by k -d trees. The model also includes all polynomial families of increasing trees recently studied by Broutin et al. (The height of increasing trees. Random Structures and Algorithms, 2007, in press).

Weiterführende Literatur

Empfehlungen zum selben Thema automatisch vorgeschlagen von bX