SML/NJ Library Manual

The `SplayTree` structure

Synopsis

signature SPLAY_TREE structure SplayTree : SPLAY_TREE

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

Interface

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

Description

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.

Discussion

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 ]