## bst

2022-11-07

Binary search tree

# 1Description

**BST** is a Common Lisp library for working with binary search trees that
can contain any kind of values.

# 2License

**BST** is released under the GPL-3 license. See the LICENSE file for details.

# 3API

## 3.1Values

By default, the library is set to work with trees containing numbers.

To work with another type of values, the parameters
`*bst-copy-function*`

, `*bst-equal-p-function*`

and
`*bst-lesser-p-function*`

must be set or bound.

`*bst-copy-function*`

must be a function used to make a copy of a value
(`identity`

by default).

`*bst-equal-p-function*`

must be a function used to check if two values of
a tree are equal (`=`

by default).

`*bst-lesser-p-function*`

must be a function used to check if a value of a tree
is lesser than another (`<`

by default).

`(bst-copy value) => value`

Make a copy of *value* using `*bst-copy-function*`

.

`(bst-equal-p value1 value2) => boolean`

Check if *value1* and *value2* are equal using `*bst-equal-p-function*`

.

`(bst-lesser-p value1 value2) => boolean`

Check if *value1* is lesser than *value2* using `*bst-lesser-p-function*`

.

## 3.2Trees

`+bst-empty+`

`+bst-empty+`

represents the empty tree.

`(bst-empty-p tree) => boolean`

Check wether a *tree* is empty or not.

```
(bst-add tree value) => tree
(bst-add! tree value) => tree
```

Insert a *value* in a *tree*. If the *value* is already in the *tree*, the
insertion has no effect (duplicates are discarded). The tree returned by
`bst-add`

will share as much of its structure as possible with the *tree*
passed in argument to reduce memory allocations. `bst-add!`

is the destructive
version of `bst-add`

(it can modify parts of the *tree* passed as argument in
place to build the returned tree).

`(bst-from-values values) => tree`

Build a tree containing the *values* passed as argument. *values* must
be a sequence. `bst-from-values`

uses `bst-add!`

to build the tree.

`(bst-from-sorted-values values) => tree`

Build a balanced tree containing the *values* passed as argument.
*values* must be a vector. `bst-from-sorted-values`

uses `bst-add!`

to
build the tree. `(bst-from-sorted-values values)`

is equivalent to
`(bst-balance! (bst-from-values values))`

, but more efficient.

```
(bst-remove tree value) => tree
(bst-remove! tree value) => tree
```

Remove a *value* from a *tree*. The tree returned by `bst-remove`

will share as
much of its structure as possible with the *tree* passed in argument to reduce
memory allocations. `bst-remove!`

is the destructive version of `bst-remove`

(it can modify parts of the *tree* passed as argument in place to build the
returned tree).

`(bst-balance tree) => tree`

Balance a *tree* to make searches more efficient.

`(bst-search tree value) => value, value-p`

Search a *value* in a *tree*. The first returned value is *value* if
it was found in the *tree* and `nil`

otherwise. The second returned
value is `t`

if the value was found and `nil`

otherwise.

```
(bst-max-value tree) => value, value-p
(bst-min-value tree) => value, value-p
```

Search the maximum or minimum value in a *tree*. The first returned
value is the found maximum or minimum, or `nil`

it the *tree* is
empty. The second returned value is `nil`

if the *tree* is empty
and `t`

otherwise.

`(bst-search-max-value-below tree value) => value, value-p`

Search the maximum value in a *tree* that is lesser than a given *value*. If
such a value is found, the function returns it and `t`

. Otherwise the function
returns `nil`

and `nil`

.

`(bst-search-min-value-above tree value) => value, value-p`

Search the minimum value in a *tree* that is greater than a given *value*. If
such a value is found, the function returns it and `t`

. Otherwise the function
returns `nil`

and `nil`

.

`(bst-count tree) => integer`

Return the number of values in a *tree*.

```
(bst-max-depth tree) => integer
(bst-min-depth tree) => integer
```

Return the maximum or minimum depth of leaf nodes in a *tree*.

`(bst-tree-copy tree) => tree`

Make a copy of a *tree*.

`(bst-tree-equal-p tree1 tree2) => boolean`

Check if two trees have the same structure (nodes and edges).

`(bst-values tree) => vector`

Return a *vector* containing the sorted values of a *tree*.

`(bst-values-equal-p tree1 tree2) => boolean`

Check if two trees contain the same values (even if they have different structures).

`(bst-map tree function) => nil`

Apply a *function* to each value in a *tree* in ascending order.
Note that the results of applying the *function* to the values are not
collected. If you need to keep them, your *function* must take care of that.

# 4Examples

Tree using integer values:

```
(defvar tree (bst:bst-from-values '(1 2 3 4)))
(setf tree (bst:bst-add tree 5))
(setf tree (bst:bst-remove tree 3))
(bst:bst-search tree 2)
2
T
(bst:bst-search tree 3)
NIL
NIL
```

Tree using string values:

```
(let* ((bst:*bst-copy-function* #'copy-seq)
(bst:*bst-equal-p-function* #'string=)
(bst:*bst-lesser-p-function* #'string<)
(tree (bst:bst-balance (bst:bst-from-values '("one" "two" "three")))))
(bst:bst-count tree))
3
```

# 5Tests

The tests require the **FiveAM** package. They can be run with:

`(asdf:test-system "bst")`