On the internal path length ofd-dimensional quad trees

DOI<25::AID-RSA2>3.0.CO;2-R 10.1002/(SICI)1098-2418(199908)15:1<25::AID-RSA2>3.0.CO;2-RzbMath0927.68030OpenAlexW2027482003MaRDI QIDQ4262416

Ralph Neininger, Ludger Rüschendorf

Publication date: 29 November 1999

Full work available at URL: https://doi.org/10.1002/(sici)1098-2418(199908)15:1<25::aid-rsa2>3.0.co;2-r

zbMATH Keywords

search treesquad tree

Mathematics Subject Classification ID

Searching and sorting (68P10)

Related Items (18)

Limit laws for partial match queries in quadtrees ⋮ Inversions in split trees and conditional Galton--Watson trees ⋮ Thin tails of fixed points of the nonhomogeneous smoothing transform ⋮ On densities for solutions to stochastic fixed point equations ⋮ A general limit theorem for recursive algorithms and combinatorial structures ⋮ A weakly 1-stable distribution for the number of random records and cuttings in split trees ⋮ Unnamed Item ⋮ The total path length of 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 ⋮ D?E?K=(1000)8 ⋮ Phase changes in randomm-ary search trees and generalized quicksort ⋮ On a multivariate contraction method for random recursive structures with applications to Quicksort ⋮ 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 ⋮ Limit Theorems for Depths and Distances in Weighted Random B-Ary Recursive Trees ⋮ On binary search tree recursions with monomials as toll functions

Cites Work

• Unnamed Item
• On the average internal path length of m-ary search trees
• Branching processes in the analysis of the heights of trees
• A fixed point theorem for distributions
• Analytic variations on quadtrees
• Quad trees: A data structure for retrieval by composite keys
• An Analysis of Randomd-Dimensional Quad Trees
• The Monge–Kantorovich Mass Transference Problem and Its Stochastic Applications
• A limiting distribution for quicksort
• A note on the height of binary search trees
• Universal Limit Laws for Depths in Random Trees
• Hypergeometrics and the cost structure of quadtrees
• A limit theorem for “quicksort”

This page was built for publication: On the internal path length ofd-dimensional quad trees