Randomised Binary Search Trees

Manuel Eberl 🌐

October 19, 2018

This is a development version of this entry. It might change over time and is not stable. Please refer to release versions for citations.

Abstract

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.

License

BSD License

Topics

Session Randomised_BSTs