# 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.

#### See Also

> SplaySetFn, SplayMapFn

#### 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 ]

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