41.2.5 Searching in binary trees

The following syntactic bindings are exported by the library (vicare containers binary-search-trees). The bindings whose name is prefixed with $ are unsafe operations: they do not validate their arguments before accessing them.

Function: binary-tree-root node

Function: $binary-tree-root node

Find the root of a binary tree. The argument node must be:

• #f to represent an empty tree; in this case the return value is #f.
• An instance of <binary-node>; in this case the return value is an instance of <binary-node>.

Function: binary-tree-minimum root

Function: binary-tree-minimum root empty-tree-handler

Function: $binary-tree-minimum root empty-tree-handler

Search and return the minimum node in the tree starting from root; the minimum node is the leftmost from root.

The argument root must be #f, to represent an empty tree, or an instance of <binary-node>.

The optional argument empty-tree-handler must be a thunk. If root is #f and empty-tree-handler is not used: the return value is #f. If root is #f and empty-tree-handler is used: the return value is the return value of empty-tree-handler.

Function: binary-tree-maximum root

Function: binary-tree-maximum root empty-tree-handler

Function: $binary-tree-maximum root empty-tree-handler

Search and return the maximum node in the tree starting from root; the maximum node is the rightmost from root.

The argument root must be #f, to represent an empty tree, or an instance of <binary-node>.

The optional argument empty-tree-handler must be a thunk. If root is #f and empty-tree-handler is not used: the return value is #f. If root is #f and empty-tree-handler is used: the return value is the return value of empty-tree-handler.

Function: binary-tree-find root compare

Function: binary-tree-find root compare empty-tree-handler

Function: $binary-tree-find root compare empty-tree-handler

Search and return a node in the tree starting from root based on its sort key.

The argument root must be #f, to represent an empty tree, or an instance of <binary-node>.

The argument compare must be a procedure accepting an instance of <binary-node> as single argument; it must return a single value:

0

If the argument node satisfies the search criterion.

-1

If the argument node has sort key less than the sort key of the target node.

+1

If the argument node has sort key greater than, or equal to, the sort key of the target node.

The optional argument empty-tree-handler must be a thunk. If the target node is not found and empty-tree-handler is not used: the return value is #f. If the target node it not found and empty-tree-handler is used: the return value is the return value of empty-tree-handler.

Function: binary-tree-deepest-left-leaf root

Function: $binary-tree-deepest-left-leaf root

Find the deepest leaf in the left subtrees starting from root. The argument root must be #f to represent an empty tree or an instance of <binary-node>.

As example, given the tree:

5-------10----12
|        |     |
1--3--4  7--9 11
   |     |  |
   2     6  8

starting from ‘5’ the selected node is ‘2’, starting from ‘10’ the selected node is ‘6’.

Function: binary-tree-deepest-right-leaf root

Function: $binary-tree-deepest-right-leaf root

Find the deepest leaf in the right subtrees starting from root. The argument root must be #f to represent an empty tree or an instance of <binary-node>.

As example, given the tree:

5-------10----12
|        |     |
1--3--4  7--9 11
   |     |  |
   2     6  8

starting from ‘5’ the selected node is ‘11’, starting from ‘1’ the selected node is ‘4’.