2026-07-24T17:55:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20456 2024-07-18T12:12:42Z ddc:004 open_access

Binary Search Trees of Permuton Samples Corsini, Benoît Dubach, Victor Féray, Valentin Binary search trees random permutations permutons Binary search trees (BST) are a popular type of structure when dealing with ordered data. They allow efficient access and modification of data, with their height corresponding to the worst retrieval time. From a probabilistic point of view, BSTs associated with data arriving in a uniform random order are well understood, but less is known when the input is a non-uniform permutation. We consider here the case where the input comes from i.i.d. random points in the plane with law μ, a model which we refer to as a permuton sample. Our results show that the asymptotic proportion of nodes in each subtree only depends on the behavior of the measure μ at its left boundary, while the height of the BST has a universal asymptotic behavior for a large family of measures μ. Our approach involves a mix of combinatorial and probabilistic tools, namely combinatorial properties of binary search trees, coupling arguments, and deviation estimates. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Benoît Corsini and Victor Dubach and Valentin Féray 2024 Is Part Of LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.AofA.2024.21 urn:nbn:de:0030-drops-204562 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.21 eng https://creativecommons.org/licenses/by/4.0/legalcode