A splay tree implementation

Splay trees are binary search trees that move recently accessed nodes closer to the root for easier access. They have amortized O(log n)-time access for a large enough sequence of primitive operations.

As a heuristic, a splay tree may outperform other trees such as red-black trees when recently accessed items are more likely to be accessed in the near future.

The amortized complexity analysis only applies if t is used as a linear type, i.e. each t returned by access operations is used for the next operation, instead of being discarded (similar to Fqueue). If, instead, it is used as a persistent data structure, most primitive operations have O(n) complexity.

module type Key = sig ... end
module type Data = sig ... end
module type Reduction_operation = sig ... end
type ('k, 'd, 'a) reduction_operation = (module Reduction_operation with type accum = 'a and type data = 'd and type key = 'k)
module type S = sig ... end
module type Splay_tree = sig ... end