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