Randomised Binary Search Trees (Q7361412)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
AFP entry Randomised_BSTs
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Randomised Binary Search Trees |
AFP entry Randomised_BSTs |
Statements
19 October 2018
0 references
Manuel Eberl
0 references
Randomised Binary Search Trees (English)
0 references
This work is a formalisation of the Randomised Binary Search Trees introduced by Martínez and Roura, including definitions and correctness proofs. Like randomised treaps, they are a probabilistic data structure that behaves exactly as if elements were inserted into a non-balancing BST in random order. However, unlike treaps, they only use discrete probability distributions, but their use of randomness is more complicated.
0 references
