Splay trees are binary search trees that are balanced based on
recently accessed elements. They provide amortized O(log n)
performance for tree operations (
remove), and O(n)
amortized time for set operations. Splay trees do not maintain
any invariant information and are therefore very memory efficient.
To achieve their amortized bounds, splay trees re-balance
themselves on every tree access (e.g.,
always leaves the most recently accessed element at the root of
the tree. Therefore repeated access to recent elements can be
very efficient. However, this also means that tree operations may
take O(n) for degenerate cases.
with type ('a,'b) result = 'a * 'b PolySet.t
Reins.SplaySet.MonoSetfunctor except it is parameterized by a module that also supports the