# Description

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

# License

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

# API

## Values

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*`

should be a function to use instead of `identity`

to make a copy of a value.

`*bst-equal-p-function*`

should be a function to use instead of `=`

to check if two values of a tree are equal.

`*bst-lesser-p-function*`

should be a function to use instead ot `<`

to check if a value of a tree is lesser than another.

`(bst-copy value) => value`

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

if defined or `identity`

otherwise.

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

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

if defined or `=`

otherwise.

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

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

if defined or `<`

otherwise.

## Trees

`+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). `bst-add!`

is the destructive version of `bst-add`

(it can destroy the *tree* passed as argument and take parts of it to build the result, and it inserts the *value* as is instead of inserting a copy of it).

`(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*. `bst-remove!`

is the destructive version of `bst-remove`

.

```
(bst-balance tree) => tree
(bst-balance! tree) => tree
```

Balance a *tree* to make searches more efficient. `bst-balance!`

is the destructive version of `bst-balance`

.

`(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-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).

# Examples

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
```

# Tests

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

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

- Author
- Guillaume LE VAILLANT
- License
- GPL-3