Anzeige
Erschienen in:
2016 | OriginalPaper | Buchkapitel
Depth of a Random Binary Search Tree with Concurrent Insertions
verfasst von : James Aspnes, Eric Ruppert
Erschienen in: Distributed Computing
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 \(\varOmega (c \log (n/c))\), using a simple strategy of always playing the largest available card.