File SplayTree.h

↰ Parent directory (ADS/tree)

The splay tree of Sleator and Tarjan, beyond the book: a binary search tree with no balance information, where each access moves the node accessed to the root by rotations in pairs (zig-zig and zig-zag), which roughly halve the depth of the nodes on its path; any sequence of m operations on n keys takes :math:` O( ( m + n ) log n ) ` time, i.e., :math:` O( log n ) ` amortized each, and the keys accessed often stay near the root (the static optimality and the working set theorems).

Definition (ADS/tree/SplayTree.h)

Detailed Description

The splay is top-down, in one pass from the root that splits the tree into a left and a right part and joins them at the end. It is a DICTIONARY [see File ADT.h]; lookup() also splays, hence it changes the shape of the tree (but not its keys) and is not const.

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

    1. Sleator, R. E. Tarjan, Self-adjusting binary search trees, Journal of the ACM 32(3), 652-686, 1985, doi:10.1145/3828.3835

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes