Name
Abstract | ||
|---|---|---|
Multiway trees, also known as m-ary search trees, are data struc- tures generalizing binary search trees. A common probability model for anlayzing the behavior of these structures is the random permu- tation model. The probability mass function Q on the set of m-ary search trees under the random permutation model is the distribution induced by sequentially inserting the records of a uniformly random permutation into an initially empty m-ary search tree. We study some basic properties of the functional Q, which serves as a measure of the "shape" of the tree. In particular, we determine exact and asymptotic expressions for the maximum and minimum values of Q and identify and count the trees achieving those values. |
Year | DOI | Venue |
|---|---|---|
1996 | 10.1017/S096354830000211X | Combinatorics, Probability & Computing |
Keywords | Field | DocType |
probability mass function,random permutation | Discrete mathematics,Random element,Random variate,Combinatorics,Random variable,Random permutation,Cumulative distribution function,Probability distribution,Random binary tree,Mathematics,Random function | Journal |
Volume | Issue | Citations |
5 | 04 | 3 |
PageRank | References | Authors |
0.88 | 5 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Robert P. Dobrow | 1 | 35 | 5.28 |
| James Allen Fill | 2 | 253 | 40.88 |