The Joint Distribution of Elastic Buckets in Multiway Search Trees

DOI10.1137/S009753979223023XzbMATH Open0820.68037OpenAlexW2018490873MaRDI QIDQ4312422FDOQ4312422

Authors: William Lew, Hosam M. Mahmoud 

Publication date: 27 August 1995

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s009753979223023x

Recommendations

• A multivariate view of random bucket digital search trees
• Analysis of the space of search trees under the random insertion algorithm
• On the joint distribution of the insertion path length and the number of comparisons in search trees
• Dependence and phase changes in random \(m\)-ary search trees
• Phase changes in random \(m\)-ary search trees and generalized quicksort

zbMATH Keywords

multivariate statisticsrandom search trees

Mathematics Subject Classification ID

Trees (05C05) Central limit and other weak theorems (60F05) Data structures (68P05) Searching and sorting (68P10)

Cited In (13)

• Second phase changes in random \(m\)-ary search trees and generalized quicksort: Convergence rates
• On the internal structure of random recursive circuits
• Solutions to complex smoothing equations
• Geometric bucket trees: analysis of linear bucket tree
• A general limit theorem for recursive algorithms and combinatorial structures
• Toward a formal derivation of the expected behavior of prefix B-trees
• Probabilistic analysis of bucket recursive trees
• Functional limit theorems for multitype branching processes and generalized Pólya urns.
• Branches in bucket recursive trees with variable capacities of buckets
• Dependence and phase changes in random \(m\)-ary search trees
• On a multivariate contraction method for random recursive structures with applications to quicksort
• Phase changes in random \(m\)-ary search trees and generalized quicksort
• Refined asymptotics for the number of leaves of random point quadtrees

This page was built for publication: The Joint Distribution of Elastic Buckets in Multiway Search Trees

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