On the internal path length ofd-dimensional quad trees

DOI10.1002/(SICI)1098-2418(199908)15:1%3C25::AID-RSA2%3E3.0.CO;2-RMaRDI QIDQ4262416zbMATH OpenOpenAlexFDO

Authors 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%3C25::aid-rsa2%3E3.0.co;2-r

zbMATH Keywords

quad treesearch trees

Mathematics Subject Classification ID

Searching and sorting (68P10)

Recommendations

• An Analysis of Randomd-Dimensional Quad Trees
• The total path length of split trees
• Limit laws for partial match queries in quadtrees
• Phase changes in random point quadtrees
• Limiting Distributions for Path Lengths in Recursive Trees

Cites work

• A fixed point theorem for distributions
• A limit theorem for “quicksort”
• A limiting distribution for quicksort
• A note on the height of binary search trees
• An Analysis of Randomd-Dimensional Quad Trees
• Analytic variations on quadtrees
• Branching processes in the analysis of the heights of trees
• scientific article; zbMATH DE number 53861 (Why is no real title available?)
• Hypergeometrics and the cost structure of quadtrees
• On the average internal path length of m-ary search trees
• Quad trees: A data structure for retrieval by composite keys
• The Monge–Kantorovich Mass Transference Problem and Its Stochastic Applications
• Universal Limit Laws for Depths in Random Trees

Cited in

(22)

• A general limit theorem for recursive algorithms and combinatorial structures
• On binary search tree recursions with monomials as toll functions
• Limit laws for partial match queries in quadtrees
• Split trees -- a unifying model for many important random trees of logarithmic height: a brief survey
• Thin tails of fixed points of the nonhomogeneous smoothing transform
• D E K=(100)_8
• Phase changes in random m-ary search trees and generalized quicksort
• On a multivariate contraction method for random recursive structures with applications to quicksort
• A weakly 1-stable distribution for the number of random records and cuttings in split trees
• Limit theorems for depths and distances in weighted random b-ary recursive trees
• An Analysis of Randomd-Dimensional Quad Trees
• scientific article; zbMATH DE number 1545682 (Why is no real title available?)
• Inversions in split trees and conditional Galton-Watson trees
• The fluctuations of the giant cluster for percolation on random split trees
• Inversions in split trees and conditional Galton-Watson trees
• On densities for solutions to stochastic fixed point equations
• Dependence and phase changes in random m-ary search trees
• On martingale tail sums for the path length in random trees
• On the asymptotic internal path length and the asymptotic Wiener index of random Split trees
• Combinatorial differential operators in: Faà di Bruno formula, enumeration of ballot paths, enriched rooted trees and increasing rooted trees
• The total path length of split trees
• Support, absolute continuity and harmonic moments of fixed points of the multivariate smoothing transform

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4262416)