Multivariate normal limit laws for the numbers of fringe subtrees in \(m\)-ary search trees and preferential attachment trees (Q2363114): Difference between revisions

Summary: We study fringe subtrees of random \(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\)-ary search trees with \( m\leq 26 \) and for the linear preferential attachment trees, the number of fringe subtrees that are isomorphic to an arbitrary fixed tree \(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 \(m\)-ary search trees for \(m\leq 26\) has asymptotically a normal distribution.