{
  "id": "2403.03151",
  "version": "v1",
  "published": "2024-03-05T17:43:49.000Z",
  "updated": "2024-03-05T17:43:49.000Z",
  "title": "Binary search trees of permuton samples",
  "authors": [
    "Benoît Corsini",
    "Victor Dubach",
    "Valentin Féray"
  ],
  "comment": "27 pages, 6 figures",
  "journal": "Advances in Applied Mathematics, Volume 162, January 2025, 102774",
  "doi": "10.1016/j.aam.2024.102774",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "Binary search trees (BST) are a popular type of data structure when dealing with ordered data. Indeed, they enable one to access and modify data efficiently, with their height corresponding to the worst retrieval time. From a probabilistic point of view, binary search trees associated with data arriving in a uniform random order are well understood, but less is known when the input is a non-uniform random permutation. We consider here the case where the input comes from i.i.d. random points in the plane with law $\\mu$, a model which we refer to as a permuton sample. Our results show that the asymptotic proportion of nodes in each subtree depends on the behavior of the measure $\\mu$ at its left boundary, while the height of the BST has a universal asymptotic behavior for a large family of measures $\\mu$. Our approach involves a mix of combinatorial and probabilistic tools, namely combinatorial properties of binary search trees, coupling arguments, and deviation estimates.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-03-05T17:43:49.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60C05",
      "05C05",
      "05A05"
    ],
    "keywords": [
      "binary search trees",
      "permuton sample",
      "worst retrieval time",
      "uniform random order",
      "non-uniform random permutation"
    ],
    "tags": [
      "journal article"
    ],
    "publication": {
      "publisher": "Elsevier"
    },
    "note": {
      "typesetting": "TeX",
      "pages": 27,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}