Binary Search Tree
Switch branches/tags
Nothing to show
Clone or download

README.org

BST

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-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-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:oos 'test-op 'bst)