# Depth of a random binary search tree with concurrent insertions

James Aspnes and Eric Ruppert.
Depth of a random binary search tree with concurrent insertions.
*Distributed Computing - 30th International Symposium, {DISC} 2016, Paris, France, September 27–29, 2016. Proceedings*, September 2016, pp. 371–384.

## Abstract

Shuffle a deck of $n$ cards numbered $1$ through $n$. Deal out the
first *c* cards into a hand. A player then repeatedly chooses
one of the cards from the hand, inserts it into a binary search tree, and then
adds the next card from deck to the hand (if the deck is
empty). When the player finally runs out of cards, how deep can the
search tree be?

This problem is motivated by concurrent insertions by $c$ processes
of random keys into a binary search tree, where the order of insertions is
controlled by an adversary that can delay individual processes.
We show that an adversary that uses any strategy based on comparing
keys cannot obtain an expected average depth greater than *O(c + log n)*.
However, the adversary can obtain an expected tree height of *Ω(c log
(n/c))*, using a simple strategy of always playing the largest available
card.

- DISC 2016 proceedings version:
**PDF**.

## BibTeX

Download@inproceedings{AspnesR2016,
author = {James Aspnes and
Eric Ruppert},
editor = {Cyril Gavoille and
David Ilcinkas},
title = {Depth of a Random Binary Search Tree with Concurrent Insertions},
booktitle = {Distributed Computing - 30th International Symposium, {DISC} 2016,
Paris, France, September 27--29, 2016. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {9888},
pages = {371--384},
publisher = {Springer},
year = {2016},
url = {http://dx.doi.org/10.1007/978-3-662-53426-7_27},
doi = {10.1007/978-3-662-53426-7_27},
timestamp = {Mon, 05 Sep 2016 12:49:45 +0200},
biburl = {http://dblp.dagstuhl.de/rec/bib/conf/wdag/AspnesR16},
bibsource = {dblp computer science bibliography, http://dblp.org}
}

Consolidated BibTeX file

Return to James Aspnes's publications

Return to James Aspnes's home page