The total path length of split trees
From MaRDI portal
Publication:691101
DOI10.1214/11-AAP812zbMATH Open1254.05037arXiv1102.2541OpenAlexW3104565967MaRDI QIDQ691101FDOQ691101
Authors: Nicolas Broutin, Cecilia Holmgren 
Publication date: 29 November 2012
Published in: The Annals of Applied Probability (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1102.2541
Recommendations
- Novel characteristics of split trees by use of renewal theory
- Split trees -- a unifying model for many important random trees of logarithmic height: a brief survey
- An almost sure result for path lengths in binary search trees
- scientific article; zbMATH DE number 6683495
- On the internal path length ofd-dimensional quad trees
Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Combinatorial probability (60C05) Paths and cycles (05C38)
Cites Work
- Quicksort
- Title not available (Why is that?)
- Probability Inequalities for Sums of Bounded Random Variables
- Applied Probability and Queues
- Quad trees: A data structure for retrieval by composite keys
- A general limit theorem for recursive algorithms and combinatorial structures
- On the analysis of stochastic divide and conquer algorithms
- Title not available (Why is that?)
- Probability metrics and recursive algorithms
- A limit theorem for “quicksort”
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- Stopped Random Walks
- Some average measures in m-ary search trees
- A limiting distribution for the number of cuts needed to isolate the root of a random recursive tree
- Cutting down recursive trees
- Random cutting and records in deterministic and random trees
- Cutting down random trees
- Large deviations for the weighted height of an extended class of trees
- On Excess Over the Boundary
- A fixed point theorem for distributions
- Some properties of a limiting distribution in Quicksort
- A limiting distribution for quicksort
- Quicksort asymptotics
- Title not available (Why is that?)
- File structures using hashing functions
- Average case analysis of algorithms on sequences. With a foreword by Philippe Flajolet
- Digital trees and memoryless sources: from arithmetics to analysis
- Approximating the limiting quicksort distribution
- Novel characteristics of split trees by use of renewal theory
- Digital Search Trees Again Revisited: The Internal Path Length Perspective
- A probabilistic proof of a weak limit law for the number of cuts needed to isolate the root of a random recursive tree
- Total Path Length for Random Recursive Trees
- Limiting Distributions for Path Lengths in Recursive Trees
- m‐ary Search trees when m ≥ 27: A strong asymptotics for the space requirements
- On the asymptotic internal path length and the asymptotic Wiener index of random Split trees
- A probabilistic analysis of some tree algorithms
- On The variance of the extremal path length in a symmetric digital trie
- Analysis of the space of search trees under the random insertion algorithm
- Dynamic tree algorithms
- Title not available (Why is that?)
- A weakly 1-stable distribution for the number of random records and cuttings in split trees
- Random records and cuttings in binary search trees
- Universal Limit Laws for Depths in Random Trees
- On the internal path length ofd-dimensional quad trees
- Title not available (Why is that?)
- Concentration of Size and Path Length of Tries
- Some Combinatorial Properties of Certain Trees With Applications to Searching and Sorting
- The height of increasing trees
- The height of increasing trees
- Weighted height of random trees
Cited In (18)
- Permutations in binary trees and split trees
- Voronoi cells in random split trees
- Random recursive trees and preferential attachment trees are random split trees
- Properties of Lucas trees
- The \(k\)-cut model in deterministic and random trees
- The asymptotic distribution of cluster sizes for supercritical percolation on random split trees
- On densities for solutions to stochastic fixed point equations
- Inversions in split trees and conditional Galton-Watson trees
- Inversions in split trees and conditional Galton-Watson trees
- The fluctuations of the giant cluster for percolation on random split trees
- A weakly 1-stable distribution for the number of random records and cuttings in split trees
- The path length of the Bernoulli splitting algorithm
- Split trees -- a unifying model for many important random trees of logarithmic height: a brief survey
- Dependence and phase changes in random \(m\)-ary search trees
- Renewal theory in the analysis of tries and strings
- On martingale tail sums for the path length in random trees
- An almost sure result for path lengths in binary search trees
- Tree-length equals branch-length
Uses Software
This page was built for publication: The total path length of split trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q691101)
