Asymptotic Distribution of Two-Protected Nodes in m-ary Search Trees

Abstract:

In this report, the number of two-protected nodes in m-ary search trees is studied i.e., nodes with distance at least two to any leaf in the tree. This is of interest since the protected nodes describe local properties close to the leaves of the m-ary search trees. This is done by using a generalised Pólya urn model and relating this urn model to how the tree evolves after each new key is inserted into the tree. It is proven that the number of two-protected nodes in m-ary search trees is asymptotically normally distributed when m = 4, 5, 6 which is the main result. This is in agreement with previously known results for m = 2, 3, which were obtained by using the same approach. The method and algorithms are

presented in such a way that it simpli_es calculations for larger m. Based on the results for m = 2,…, 6 conjectures are made providing a possible way to extend these results for larger m < 26.