<INTERFACE> The <CD/SplayTree/ structure <SEEALSO> <FCTREF/SplaySetFn/ <FCTREF/SplayMapFn/ </SEEALSO> <PP> The <STRREF NOLINK/SplayTree/ structure provides the datatype and two basic functions necessary for applicative Sleator-Tarjan splay trees. <SPEC> <DATATYPE><TYPARAM>'a<ID>splay <CONS>SplayObj<TY>{value : 'a, right : 'a splay, left : 'a splay} <CONS>SplayNil </DATATYPE> <SPEC> <VAL>splay<TY>(('a -> order) * 'a splay) -> (order * 'a splay) <COMMENT> <PROTOTY> splay (<ARG/cmp/, <ARG/tree/) </PROTOTY> returns <CD/(<ARG/r/, Usually, <ARG/cmp/ will compare its argument against some fixed value. For example, if <CD/cmpfn : 'a * 'a -> order/ defines an order relation on the type cmpfn(v,u)/ to the <CD/splay/ function. <SPEC> <VAL>join<TY>('a splay * 'a splay) -> 'a splay <COMMENT> <PROTOTY> join (<ARG/sp/, <ARG/sp2/) </PROTOTY> returns a new splay tree joining <ARG/sp/ and <ARG/sp2/. <PP> Not only is the data structure concrete, but the <CD/splay/ function takes a comparison function as an argument, allowing the semantics of the splay tree to be changed on the fly. It is assumed that this structure will only be used within another structure that will guarantee the consistency of the trees. </INTERFACE>