Loading...
Loading...

Go to the content (press return)

Randomization of search trees by subtree size

Author
Martinez, C.; Roura, S.
Type of activity
Report
Date
1996-01
Code
LSI-95-51-R
Repository
http://hdl.handle.net/2117/97227 Open in new window
Abstract
In this paper we present probabilistic algorithms over random binary search trees such that: a) the insertion of a set of keys in any fixed order into an initially empty tree produces always a random tree; b) the deletion of any key of a random tree results in a random tree; c) the random choices made by the algorithms are based upon the sizes of the subtrees of the random tree, an information that can be used for rank searches, for instance; and d) the cost, measured as the number of visited no...
Citation
Martinez, C., Roura, S. "Randomization of search trees by subtree size". 1996.
Keywords
Probabilistic algorithms, Random binary search trees, Randomization
Group of research
ALBCOM - Algorithms, Computational Biology, Complexity and Formal Methods

Participants

Attachments