The trees vocabulary is a library for unbalanced binary search trees. A tree is not intended to be used directly in most situations but rather as a base class for new trees, because performance can degrade to linear time storage/retrieval by the number of keys. These binary search trees conform to the assoc protocol.

Constructing trees:

<tree> ( -- tree )

>tree ( assoc -- tree )

TREE{

Operations on trees:

height ( tree -- n )

first-entry ( tree -- pair/f )

first-key ( tree -- key/f )

last-entry ( tree -- pair/f )

last-key ( tree -- key/f )

Range operations on trees:

headtree>alist[) ( to-key tree -- alist )

headtree>alist[] ( to-key tree -- alist )

tailtree>alist(] ( from-key tree -- alist )

tailtree>alist[] ( from-key tree -- alist )

subtree>alist() ( from-key to-key tree -- alist )

subtree>alist(] ( from-key to-key tree -- alist )

subtree>alist[) ( from-key to-key tree -- alist )

subtree>alist[] ( from-key to-key tree -- alist )

Navigation operations on trees:

lower-key ( key tree -- key/f )

lower-entry ( key tree -- pair/f )

higher-key ( key tree -- key/f )

higher-entry ( key tree -- pair/f )

floor-key ( key tree -- key/f )

floor-entry ( key tree -- pair/f )

ceiling-key ( key tree -- key/f )

ceiling-entry ( key tree -- pair/f )

Pop/Slurp operations on trees:

pop-tree-left ( tree -- node/f )

pop-tree-right ( tree -- node/f )

slurp-tree-left ( tree quot: ( ... entry -- ... ) -- ... )

slurp-tree-right ( tree quot: ( ... entry -- ... ) -- ... )