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 ... endmodule type Data = sig ... endmodule type Reduction_operation = sig ... endtype ('k, 'd, 'a) reduction_operation =
(module Reduction_operation
with type accum = 'a
and type data = 'd
and type key = 'k)module type S = sig ... endmodule type Splay_tree = sig ... end