File Treap.h

↰ Parent directory (ADS/tree)

The treap of Seidel and Aragon, beyond the book: a binary search tree on the keys that is also a heap on random priorities given to the keys when they are inserted, so that its shape is that of a binary search tree built by inserting the keys in a random order, whatever the order of the operations; the expected depth of a node is :math:` O( log n ) , and an insertion or a removal takes :math: O( log n ) ` expected time and makes fewer than 2 rotations on average.

Definition (ADS/tree/Treap.h)

Detailed Description

An insertion puts the key in a leaf and rotates it up while its priority beats its parent’s, a removal rotates the key down until it is a leaf. It is a DICTIONARY [see File ADT.h]; the priorities come from SplitMix64 [see File RandomHashing.h], seeded, so that a run is reproducible.

The contracts [see File Contract.h]: insert() ensures that the key is there and remove() that it is not; the invariant is the order of the keys and the heap order of the priorities, an O( n ) check at the level 3. The operations are defined in Treap.tpp.

  1. Seidel, C. R. Aragon, Randomized search trees, Algorithmica 16(4-5), 464-497, 1996, doi:10.1007/BF01940876

    1. Steele, D. Lea, C. H. Flood, Fast splittable pseudorandom number generators, Proceedings of OOPSLA 2014, 453-472, 2014, doi:10.1145/2660193.2660195 (SplitMix64)

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes