BST is a Common Lisp library for working with binary search trees that can contain any kind of values.
BST is released under the GPL-3 license. See the LICENSE file for details.
By default, the library is set to work with trees containing numbers.
To work with another type of values, the parameters
*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
(bst-equal-p value1 value2) => boolean
Check if value1 and value2 are equal using
*bst-equal-p-function* if defined or
(bst-lesser-p value1 value2) => boolean
Check if value1 is lesser than value2 using
*bst-lesser-p-function* if defined or
+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-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-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-balance tree) => tree (bst-balance! tree) => tree
Balance a tree to make searches more efficient.
bst-balance! is the destructive version of
(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
(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
(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).
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
The tests require the FiveAM package. They can be run with:
- Guillaume LE VAILLANT