Asymptotic distribution of two-protected nodes in ternary search trees

Cecilia Holmgren, Svante Janson

We study protected nodes in $m$-ary search trees, by putting them in context of generalised Pólya urns. We show that the number of two-protected nodes (the nodes that are neither l…