Class Binary-Search-Tree

Part of:

package metabang.cl-containers, class splay-tree, class red-black-tree, class concrete-container, class initial-contents-mixin, class findable-container-mixin, class iteratable-container-mixin, class sorted-container-mixin, class container-uses-nodes-mixin, class rooted-tree-container

Default initargs

:key → #:test → #
:sorter → #

Direct Superclass

concrete-container

Inherited by all container classes that can/should
be instantiated using make-container.

container-uses-nodes-mixin
findable-container-mixin
initial-contents-mixin
iteratable-container-mixin
rooted-tree-container

Base class of all trees with roots.

sorted-container-mixin

Direct Subclass

red-black-tree
splay-tree

Slot

keyInitform:(quote identity), Initargs::key; Reader:key.
rootInitargs::root; Accessors:root.
sorterInitform:(function <), Initargs::sorter; Accessors:sorter.
testInitform:(function equal), Initargs::test.
tree-sizeInitform:0, Initargs::tree-size; Accessors:tree-size.

Direct Method

delete-item
delete-item-if
delete-node
empty!

Removes all items from the container and returns nil.

empty-p

Returns t if there are no items in the container.

find-item

Find item in container using the container's test
method for comparisons. The test method must ta...

find-node

Find node containing thing in container using the container's test
method for comparisons. The te...

find-successor-item
find-successor-node
first-element
first-node
height
inorder-walk
inorder-walk-nodes
insert-item

Adds item to the container

item-at

Returns the item specified by the indexes.

iterate-nodes

Applies function to each node in the container. If the container doesn't have nodes, then this is...

last-element
last-node
make-node-for-container
postorder-walk
postorder-walk-nodes
predecessor

Return the item that comes before item in the container. Only makes sense for sorted containers...

preorder-walk
preorder-walk-nodes
rotate-left
rotate-right
setffirst-element
setflast-element
size

Returns the number of items currently in the container.

splay-tree-rotate

rotate the node (and maybe the parent) until the node is
the root of the tree

splay-tree-splay

Preform the splay operation on the tree about this node
rotating the node until it becomes the ro...

successor

Return the item that comes after item in the container. Only makes sense for sorted containers. R...

update-element

Other Method

%operate-after-finding
add-initial-contents
best-item

Returns the item in items with the 'best' value of function where
'best' is determined by test. Y...

collect-elements

Returns a possibly filtered and possibly transformed list of the elements in a container. If the ...

collect-elements-stably
collect-nodes

Returns a possibly filtered and possibly transformed list
of the nodes in a container. If the con...

count-elements
count-elements-if
count-items
delete-element
delete-list

Deletes each item in the list from the container.

element-position

Returns the position of element in container using test and
key to match. Key defaults to identit...

every-element-p
every-item-p

Returns true if every item in the container satisfies the
predicate. Predicate should be a funct...

find-element

For now, compare find-item.

insert-initial-contents-p

Returns true if this container type should rely on the default behavior of basic-initial-contents...

insert-list

Adds each item in the list to the container in an
upspecified order.

insert-new-item

Adds item to the container unless it is already there

insert-sequence

Adds each item in the sequence to the container in an
upspecified order.

iteratable-p

Returns true if thing knows how to iterate-nodes.

iterate-elements
nth-element

Returns the nth element in the container's 'natural' order.

print-container

Prints the contents of container (using PRINT). Returns the container.

reduce-container
reduce-elements
reduce-nodes
remove-items-if

Removes items from a container that satisfy the test. The
container is returned.

reverse-container

Destructively alters the elements/nodes of an ordered container so that they are reversed.

search-for-element
search-for-item

Hunt for the item in the container. Key and Test
are as in member.

search-for-match

Hunt for an item in the container that satisfies
the predicate. Key is as in count-if.

search-for-matching-node
search-for-node
search-for-node*
some-element-p
some-item-p

Returns the first item in the container for which predicate
holds. Predicate should be a function...

unique-elements
unique-nodes