An Improved Bound for Random Binary Search Trees with Concurrent Insertions

DOI10.4230/LIPICS.STACS.2018.37zbMATH Open1487.68084OpenAlexW2793330855MaRDI QIDQ3304136FDOQ3304136

Authors: George Giakkoupis, Philipp Woelfel 

Publication date: 5 August 2020

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

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

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)

Cites Work

• Negative association of random variables, with applications
• A note on the height of binary search trees
• Concentration of Measure for the Analysis of Randomized Algorithms
• Title not available (Why is that?)
• Smoothed analysis of binary search trees
• The height of a random binary search tree
• Trees, Forests and Rearranging
• On the efficiency of a new method of dictionary construction
• Depth of a random binary search tree with concurrent insertions

Cited In (1)

• 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)