Name
Abstract | ||
|---|---|---|
Problems associated with m-ary trees have been studied by computer scientists and combinatorialists. It is well known that a simple generalization of the Catalan numbers counts the number of m-ary trees on n nodes. In this paper we consider τm, n, the number of m-ary search trees on n keys, a quantity that arises in studying the space of m-ary search trees under the uniform probability model. We prove an exact formula for τm, n, both by analytic and by combinatorial means. We use uniform local approximations for sums of i.i.d. random variables to study the asymptotic development of τm, n for fixed m as n→∞. |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1017/S0963548397003118 | Combinatorics, Probability & Computing |
Keywords | Field | DocType |
n keys,n node,m-ary search tree,combinatorial mean,catalan number,asymptotic development,uniform probability model,m-ary search trees,m-ary tree,uniform local approximation,computer scientist,n key,random variable | Exact formula,Discrete mathematics,Probability model,Random variable,Combinatorics,Catalan number,Weight-balanced tree,Mathematics | Journal |
Volume | Issue | Citations |
6 | 4 | 3 |
PageRank | References | Authors |
0.54 | 1 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| James Allen Fill | 1 | 253 | 40.88 |
| Robert P. Dobrow | 2 | 35 | 5.28 |