An Improved Bound for Random Binary Search Trees with Concurrent Insertions

DOI10.4230/LIPICS.STACS.2018.37MaRDI QIDQ3304136zbMATH OpenOpenAlexFDO

Authors George Giakkoupis, Philipp Woelfel

Publication date 5 August 2020

Full work available at URL https://hal.inria.fr/hal-01942160

zbMATH Keywords

average depthrandom binary search treebufferconcurrent data structures

Mathematics Subject Classification ID

Data structures (68P05) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• Depth of a random binary search tree with concurrent insertions
• Almost sure asymptotics for the random binary search tree
• Expected behaviour of \(B^+\)-trees under random insertions
• On the subtrees of random binary search trees
• On the Generation of Random Binary Search Trees
• A note on the Horton-Strahler number for random binary search trees
• On the concentration of the height of binary search trees
• New lower bounds on the cost of binary search trees
• Searches on a Binary Tree with Random Edge-Weights
• Constant bounds on the moments of the height of binary search trees

Cites work

• scientific article; zbMATH DE number 53861 (Why is no real title available?)
• A note on the height of binary search trees
• Concentration of Measure for the Analysis of Randomized Algorithms
• Depth of a random binary search tree with concurrent insertions
• Negative association of random variables, with applications
• On the efficiency of a new method of dictionary construction
• Smoothed analysis of binary search trees
• The height of a random binary search tree
• Trees, Forests and Rearranging

Cited in

(2)

• Depth of a random binary search tree with concurrent insertions
• On the joint distribution of the insertion path length and the number of comparisons in search trees

This page was built for publication: An Improved Bound for Random Binary Search Trees with Concurrent Insertions

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