An Improved Bound for Random Binary Search Trees with Concurrent Insertions

DOI10.4230/LIPICS.STACS.2018.37zbMath1487.68084OpenAlexW2793330855MaRDI QIDQ3304136

George Giakkoupis, Philipp Woelfel

Publication date: 5 August 2020

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

zbMATH Keywords

bufferaverage depthrandom binary search treeconcurrent data structures

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Depth of a random binary search tree with concurrent insertions
• Negative association of random variables, with applications
• Smoothed analysis of binary search trees
• Trees, Forests and Rearranging
• On the efficiency of a new method of dictionary construction
• The height of a random binary search tree
• A note on the height of binary search trees
• Concentration of Measure for the Analysis of Randomized Algorithms

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