BST

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")