{
  "id": "1102.2541",
  "version": "v3",
  "published": "2011-02-12T22:26:27.000Z",
  "updated": "2012-11-02T07:52:05.000Z",
  "title": "The total path length of split trees",
  "authors": [
    "Nicolas Broutin",
    "Cecilia Holmgren"
  ],
  "comment": "Published in at http://dx.doi.org/10.1214/11-AAP812 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)",
  "journal": "Annals of Applied Probability 2012, Vol. 22, No. 5, 1745-1777",
  "doi": "10.1214/11-AAP812",
  "categories": [
    "math.PR",
    "cs.DS",
    "math.CO"
  ],
  "abstract": "We consider the model of random trees introduced by Devroye [SIAM J. Comput. 28 (1999) 409-432]. The model encompasses many important randomized algorithms and data structures. The pieces of data (items) are stored in a randomized fashion in the nodes of a tree. The total path length (sum of depths of the items) is a natural measure of the efficiency of the algorithm/data structure. Using renewal theory, we prove convergence in distribution of the total path length toward a distribution characterized uniquely by a fixed point equation. Our result covers, using a unified approach, many data structures such as binary search trees, m-ary search trees, quad trees, median-of-(2k+1) trees, and simplex trees.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2012-11-02T07:52:05.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "total path length",
      "split trees",
      "data structures",
      "binary search trees",
      "m-ary search trees"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1102.2541B"
    }
  }
}