The total path length of split trees
From MaRDI portal
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.
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
Cites work
- scientific article; zbMATH DE number 6683545 (Why is no real title available?)
- scientific article; zbMATH DE number 47603 (Why is no real title available?)
- scientific article; zbMATH DE number 3473265 (Why is no real title available?)
- scientific article; zbMATH DE number 1052336 (Why is no real title available?)
- scientific article; zbMATH DE number 3233336 (Why is no real title available?)
- m‐ary Search trees when m ≥ 27: A strong asymptotics for the space requirements
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- A fixed point theorem for distributions
- A general limit theorem for recursive algorithms and combinatorial structures
- A limit theorem for “quicksort”
- A limiting distribution for quicksort
- A limiting distribution for the number of cuts needed to isolate the root of a random recursive tree
- A probabilistic analysis of some tree algorithms
- A probabilistic proof of a weak limit law for the number of cuts needed to isolate the root of a random recursive tree
- A weakly 1-stable distribution for the number of random records and cuttings in split trees
- Analysis of the space of search trees under the random insertion algorithm
- Applied Probability and Queues
- Approximating the limiting quicksort distribution
- Average case analysis of algorithms on sequences. With a foreword by Philippe Flajolet
- Concentration of Size and Path Length of Tries
- Cutting down random trees
- Cutting down recursive trees
- Digital Search Trees Again Revisited: The Internal Path Length Perspective
- Digital trees and memoryless sources: from arithmetics to analysis
- Dynamic tree algorithms
- File structures using hashing functions
- Large deviations for the weighted height of an extended class of trees
- Limiting Distributions for Path Lengths in Recursive Trees
- Novel characteristics of split trees by use of renewal theory
- On Excess Over the Boundary
- On The variance of the extremal path length in a symmetric digital trie
- On the analysis of stochastic divide and conquer algorithms
- On the asymptotic internal path length and the asymptotic Wiener index of random Split trees
- On the internal path length ofd-dimensional quad trees
- Probability Inequalities for Sums of Bounded Random Variables
- Probability metrics and recursive algorithms
- Quad trees: A data structure for retrieval by composite keys
- Quicksort
- Quicksort asymptotics
- Random cutting and records in deterministic and random trees
- Random records and cuttings in binary search trees
- Some Combinatorial Properties of Certain Trees With Applications to Searching and Sorting
- Some average measures in m-ary search trees
- Some properties of a limiting distribution in Quicksort
- Stopped Random Walks
- The height of increasing trees
- The height of increasing trees
- Total Path Length for Random Recursive Trees
- Universal Limit Laws for Depths in Random Trees
- Weighted height of random trees
Cited in
(18)- The asymptotic distribution of cluster sizes for supercritical percolation on random split trees
- On martingale tail sums for the path length in random trees
- 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
- Random recursive trees and preferential attachment trees are random split trees
- Tree-length equals branch-length
- Renewal theory in the analysis of tries and strings
- Split trees -- a unifying model for many important random trees of logarithmic height: a brief survey
- On densities for solutions to stochastic fixed point equations
- Voronoi cells in random split trees
- A weakly 1-stable distribution for the number of random records and cuttings in split trees
- Properties of Lucas trees
- The path length of the Bernoulli splitting algorithm
- Permutations in binary trees and split trees
- The \(k\)-cut model in deterministic and random trees
- Dependence and phase changes in random \(m\)-ary search trees
- An almost sure result for path lengths in binary search trees
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)
