Multivariate normal limit laws for the numbers of fringe subtrees in m m -ary search trees and preferential attachment trees

preprint2016arXivOpen access

Abstract

We study fringe subtrees of random m m -ary search trees and of preferential attachment trees, by putting them in the context of generalised Pólya urns. In particular we show that for the random m m -ary search trees with m≤26 m\leq 26 and for the linear preferential attachment trees, the number of fringe subtrees that are isomorphic to an arbitrary fixed tree T T converges to a normal distribution; more generally, we also prove multivariate normal distribution results for random vectors of such numbers for different fringe subtrees. Furthermore, we show that the number of protected nodes in random mm-ary search trees for m≤26 m\leq 26 has asymptotically a normal distribution.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.