{
  "id": "math/0502422",
  "version": "v2",
  "published": "2005-02-20T19:28:59.000Z",
  "updated": "2005-04-25T06:09:46.000Z",
  "title": "A repertoire for additive functionals of uniformly distributed m-ary search trees",
  "authors": [
    "James Allen Fill",
    "Nevin Kapur"
  ],
  "comment": "26 pages; v2 expands on the introduction by comparing the results with other probability models",
  "journal": "Discrete Mathematics and Theoretical Computer Science Proceedings AD (2005) 105-114",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "Using recent results on singularity analysis for Hadamard products of generating functions, we obtain the limiting distributions for additive functionals on $m$-ary search trees on $n$ keys with toll sequence (i) $n^\\alpha$ with $\\alpha \\geq 0$ ($\\alpha=0$ and $\\alpha=1$ correspond roughly to the space requirement and total path length, respectively); (ii) $\\ln \\binom{n}{m-1}$, which corresponds to the so-called shape functional; and (iii) $\\mathbf{1}_{n=m-1}$, which corresponds to the number of leaves.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2005-04-25T06:09:46.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "68W40",
      "60F05",
      "60C05"
    ],
    "keywords": [
      "uniformly distributed m-ary search trees",
      "additive functionals",
      "repertoire",
      "correspond",
      "total path length"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 26,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2005math......2422F"
    }
  }
}