Loading...
Loading...

Go to the content (press return)

Randomized binary search trees

Author
Martinez, C.; Roura, S.
Type of activity
Report
Date
1997-01
Repository
http://hdl.handle.net/2117/83474 Open in new window
Abstract
In this paper we present randomized algorithms over binary search trees such that: a) the insertion of a set of keys, in any fixed order, into an initially empty tree always produces a random binary search tree; b) the deletion of any key from a random binary search tree results in a random binary search tree; c) the random choices made by the algorithms are based upon the sizes of the subtrees of the tree; this implies that we can support accesses by rank without additional storage requirements...
Citation
Martinez, C., Roura, S. "Randomized binary search trees". 1997.
Keywords
BST, Binary search trees, Randomized algorithms
Group of research
ALBCOM - Algorithms, Computational Biology, Complexity and Formal Methods

Participants

Attachments