SML/NJ Library Manual

The SplayTree structure


signature SPLAY_TREE
structure SplayTree : SPLAY_TREE

The SplayTree structure provides the datatype and two basic functions necessary for applicative Sleator-Tarjan splay trees.


datatype 'a splay
  = SplayObj of {value : 'a, right : 'a splay, left : 'a splay}
  | SplayNil
val splay : (('a -> order) * 'a splay) -> (order * 'a splay)
val join : ('a splay * 'a splay) -> 'a splay


datatype 'a splay

splay (cmp, tree)
returns (r,tree'), where tree' is tree adjusted using the comparison function cmp. In addtion, if tree' = SplayObj{value,...}, then r equal cmp value. tree' = SplayNil if and only if tree = SplayNil, in which case r is unspecified.

Usually, cmp will compare its argument against some fixed value. For example, if cmpfn : 'a * 'a -> order defines an order relation on the type 'a and we wish to search for a value u, we can pass the function fn v => cmpfn(v,u) to the splay function.

join (sp, sp2)
returns a new splay tree joining sp and sp2.

See Also

SplaySetFn, SplayMapFn


Not only is the data structure concrete, but the 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.

[ Top | Parent | Contents | Index | Root ]

Last Modified June 5, 1998
Comments to John Reppy
Copyright © 1998 Bell Labs, Lucent Technologies