The total path length of split trees
From MaRDI portal
Publication:691101
DOI10.1214/11-AAP812zbMath1254.05037arXiv1102.2541OpenAlexW3104565967MaRDI QIDQ691101
Cecilia Holmgren, Nicolas Broutin
Publication date: 29 November 2012
Published in: The Annals of Applied Probability (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1102.2541
Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Combinatorial probability (60C05) Data structures (68P05)
Related Items
Inversions in split trees and conditional Galton--Watson trees ⋮ The asymptotic distribution of cluster sizes for supercritical percolation on random split trees ⋮ On densities for solutions to stochastic fixed point equations ⋮ The \(k\)-cut model in deterministic and random trees ⋮ A weakly 1-stable distribution for the number of random records and cuttings in split trees ⋮ Embedding small digraphs and permutations in binary trees and split trees ⋮ The fluctuations of the giant cluster for percolation on random split trees ⋮ Dependence and phase changes in random m‐ary search trees ⋮ On martingale tail sums for the path length in random trees ⋮ Random Recursive Trees and Preferential Attachment Trees are Random Split Trees ⋮ Inversions in Split Trees and Conditional Galton–Watson Trees ⋮ Split trees -- a unifying model for many important random trees of logarithmic height: a brief survey ⋮ Renewal theory in the analysis of tries and strings
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Novel characteristics of split trees by use of renewal theory
- On the asymptotic internal path length and the asymptotic Wiener index of random Split trees
- Large deviations for the weighted height of an extended class of trees
- Weighted height of random trees
- Some average measures in m-ary search trees
- A fixed point theorem for distributions
- On The variance of the extremal path length in a symmetric digital trie
- 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
- Cutting down recursive trees
- Some properties of a limiting distribution in Quicksort
- Dynamic 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 probabilistic analysis of some tree algorithms
- Approximating the limiting Quicksort distribution
- A weakly 1-stable distribution for the number of random records and cuttings in split trees
- Random Records and Cuttings in Binary Search Trees
- Limiting Distributions for Path Lengths in Recursive Trees
- Random cutting and records in deterministic and random trees
- Stopped Random Walks
- A limiting distribution for the number of cuts needed to isolate the root of a random recursive tree
- A limiting distribution for quicksort
- Analysis of the space of search trees under the random insertion algorithm
- Universal Limit Laws for Depths in Random Trees
- On the internal path length ofd-dimensional quad trees
- Digital Search Trees Again Revisited: The Internal Path Length Perspective
- m‐ary Search trees when m ≥ 27: A strong asymptotics for the space requirements
- Concentration of Size and Path Length of Tries
- Applied Probability and Queues
- Total Path Length for Random Recursive Trees
- Quicksort asymptotics
- Probability metrics and recursive algorithms
- Probability Inequalities for Sums of Bounded Random Variables
- Cutting down random trees
- On Excess Over the Boundary
- File structures using hashing functions
- Some Combinatorial Properties of Certain Trees With Applications to Searching and Sorting
- A limit theorem for “quicksort”
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- The height of increasing trees
- The height of increasing trees
- Quicksort
