This is the trees Reference Manual, version 0.11, generated automatically by Declt version 4.0 beta 2 "William Riker" on Mon Feb 26 18:06:31 2024 GMT+0.
The main system appears first, followed by any subsystem dependency.
treesA library for binary trees in normal and balanced flavors
Nathan Froyd <froydnj@gmail.com>
Nathan Froyd <froydnj@gmail.com>
BSD style
0.11
package.lisp (file).
generics.lisp (file).
types.lisp (file).
print.lisp (file).
binary-trees.lisp (file).
red-black-trees.lisp (file).
avl-trees.lisp (file).
aa-trees.lisp (file).
iterator.lisp (file).
utils.lisp (file).
license (file).
readme (file).
news (file).
todo (file).
Files are sorted by type and then listed depth-first from the systems components trees.
trees/trees.asdtrees/package.lisptrees/generics.lisptrees/types.lisptrees/print.lisptrees/binary-trees.lisptrees/red-black-trees.lisptrees/avl-trees.lisptrees/aa-trees.lisptrees/iterator.lisptrees/utils.lisptrees/generics.lisppackage.lisp (file).
trees (system).
make-binary-tree (function).
*binary-tree-info* (special variable).
trees/types.lisppackage.lisp (file).
trees (system).
binary-tree (structure).
size (reader).
(setf size) (writer).
%make-binary-tree (function).
+avl-equal+ (constant).
+avl-falls-left+ (constant).
+avl-falls-right+ (constant).
+avl-leans-left+ (constant).
+avl-leans-right+ (constant).
aa-tree-node (structure).
aa-tree-node-p (function).
avl-tree-node (structure).
avl-tree-node-p (function).
balance-info (reader).
(setf balance-info) (writer).
binary-tree-p (function).
color (reader).
(setf color) (writer).
datum (reader).
(setf datum) (writer).
key (reader).
left (reader).
(setf left) (writer).
level (reader).
(setf level) (writer).
make-aa-node (function).
make-avl-node (function).
make-red-black-node (function).
make-tree-node (function).
modcount (reader).
(setf modcount) (writer).
nodegen (reader).
pred (reader).
rank (reader).
(setf rank) (writer).
rebalance/delete (reader).
rebalance/insert (reader).
red-black-color (type).
red-black-tree-node (structure).
red-black-tree-node-p (function).
right (reader).
(setf right) (writer).
root (reader).
(setf root) (writer).
test (reader).
tree-node (structure).
tree-node-p (function).
trees/print.lispgenerics.lisp (file).
types.lisp (file).
trees (system).
pprint-tree (function).
print-object (method).
print-object (method).
print-object (method).
print-object (method).
indent-to-level (function).
trees/binary-trees.lispgenerics.lisp (file).
types.lisp (file).
trees (system).
delete (function).
emptyp (function).
find (function).
insert (function).
lower-bound (function).
maximum (function).
minimum (function).
select (function).
upper-bound (function).
delete-node (function).
find-insertion-point (function).
find-node-with-key (function).
insert-child-for-stack-entry (function).
lower-bound-node (function).
lower-bound-node-with-path (function).
maximum-node (function).
minimum-node (function).
rotate-left (function).
rotate-right (function).
select-node (function).
select-node-with-path (function).
set-root-or-entry-child (function).
update-ranks (function).
upper-bound-node (function).
upper-bound-node-with-path (function).
trees/red-black-trees.lisptypes.lisp (file).
binary-trees.lisp (file).
trees (system).
blacken (function).
blackp (function).
red-black-rebalance/delete (function).
red-black-rebalance/insert (function).
redden (function).
redp (function).
trees/avl-trees.lisptypes.lisp (file).
binary-trees.lisp (file).
trees (system).
avl-rebalance/delete (function).
avl-rebalance/insert (function).
update-balance-factors (function).
trees/aa-trees.lisptypes.lisp (file).
binary-trees.lisp (file).
trees (system).
aa-rebalance/delete (function).
aa-rebalance/insert (function).
level* (function).
skew (function).
split (function).
trees/iterator.lisptypes.lisp (file).
binary-trees.lisp (file).
trees (system).
extreme-node-with-path (function).
make-iterator (function).
trees/utils.lispbinary-trees.lisp (file).
trees (system).
for-each (function).
reverse-tree-for-each (function).
tree-for-each (function).
Packages are listed by definition order.
binary-treestrees
common-lisp.
binary-tree (structure).
delete (function).
dotree (macro).
emptyp (function).
find (function).
insert (function).
lower-bound (function).
make-binary-tree (function).
maximum (function).
minimum (function).
position (function).
pprint-tree (function).
reduce (function).
select (function).
size (reader).
(setf size) (writer).
upper-bound (function).
%make-binary-tree (function).
*binary-tree-info* (special variable).
+avl-equal+ (constant).
+avl-falls-left+ (constant).
+avl-falls-right+ (constant).
+avl-leans-left+ (constant).
+avl-leans-right+ (constant).
aa-rebalance/delete (function).
aa-rebalance/insert (function).
aa-tree-node (structure).
aa-tree-node-p (function).
avl-rebalance/delete (function).
avl-rebalance/insert (function).
avl-tree-node (structure).
avl-tree-node-p (function).
balance-info (reader).
(setf balance-info) (writer).
binary-tree-p (function).
blacken (function).
blackp (function).
color (reader).
(setf color) (writer).
datum (reader).
(setf datum) (writer).
delete-node (function).
extreme-node-with-path (function).
find-insertion-point (function).
find-node-with-key (function).
for-each (function).
indent-to-level (function).
insert-child-for-stack-entry (function).
key (reader).
left (reader).
(setf left) (writer).
level (reader).
(setf level) (writer).
level* (function).
lower-bound-node (function).
lower-bound-node-with-path (function).
make-aa-node (function).
make-avl-node (function).
make-iterator (function).
make-red-black-node (function).
make-tree-node (function).
maximum-node (function).
minimum-node (function).
modcount (reader).
(setf modcount) (writer).
nodegen (reader).
pred (reader).
rank (reader).
(setf rank) (writer).
rebalance/delete (reader).
rebalance/insert (reader).
red-black-color (type).
red-black-rebalance/delete (function).
red-black-rebalance/insert (function).
red-black-tree-node (structure).
red-black-tree-node-p (function).
redden (function).
redp (function).
reverse-tree-for-each (function).
right (reader).
(setf right) (writer).
root (reader).
(setf root) (writer).
rotate-left (function).
rotate-right (function).
select-node (function).
select-node-with-path (function).
set-root-or-entry-child (function).
skew (function).
split (function).
test (reader).
tree-for-each (function).
tree-node (structure).
tree-node-p (function).
update-balance-factors (function).
update-ranks (function).
upper-bound-node (function).
upper-bound-node-with-path (function).
Definitions are sorted by export status, category, package, and then by lexicographic order.
Attempt to remove the item with KEY from TREE.
Returns the item and T as multiple values on success, NIL and NIL on
failure.
Find the item in TREE whose key is KEY and returns the associated item and T as multiple values, or returns NIL and NIL if no such item exists.
Attempt to insert ITEM into TREE. ITEM must be of a suitable type for TREE’s key function, and the key returned from calling said function must be of a suitable type for TREE’s comparison and equality functions. Returns two values; the first is the key of ITEM and the second indicates whether ITEM was inserted or not.
Return the item in TREE possessing a key which is equal to or less than KEY. Returns NIL if there is no such item.
Create a binary tree based on TYPE. Current acceptable values for TYPE are:
:NORMAL - a normal binary tree, with no rebalancing
:RED-BLACK - a red-black tree
:AVL - an AVL tree
:AA - an AA tree.
PRED specifies the ordering relation. KEY specifies how to access the data for comparison. TEST is optional and, if given, specifies how to compare two keys for equality.
Return the item with the maximum key in TREE. It is an error to ask for the maximum item of an empty tree.
Return the item with the minimum key in TREE. It is an error to ask for the minimum item of an empty tree.
Return the Kth item (zero-based) in TREE.
Return the item in TREE possessing a key which is equal to or greater than KEY. Returns NIL if there is no such item.
red-black-tree-node) stream) ¶avl-tree-node) stream) ¶aa-tree-node) stream) ¶structure-object.
function
(error "missing arg")
test.
This slot is read-only.
function
(error "missing arg")
key.
This slot is read-only.
function
(error "missing arg")
pred.
This slot is read-only.
fixnum
0
function
(error "missing arg")
This slot is read-only.
(or null function)
This slot is read-only.
(or null function)
This slot is read-only.
Find the node in TREE with key KEY. Might return the null node if no such node can be found.
Return the node in TREE possessing a key which is equal to or less than KEY.
Return the node in TREE possessing a key which is equal to or greater than KEY.
fixnum
1
(integer -2 2)
0
binary-trees::red-black-color
:red
structure-object.
(or null binary-trees::tree-node)
| Jump to: | %
(
A B C D E F I K L M N P R S T U |
|---|
| Jump to: | %
(
A B C D E F I K L M N P R S T U |
|---|
| Jump to: | *
+
B C D K L M N P R S T |
|---|
| Jump to: | *
+
B C D K L M N P R S T |
|---|
| Jump to: | A B F G I L N P R S T U |
|---|
| Jump to: | A B F G I L N P R S T U |
|---|