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
module type S = sig ... end
module type Splay_tree = sig ... end