Class Red-Black-Tree

Part of:

package metabang.cl-containers, class binary-search-tree

Default initargs

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

Direct Superclass

binary-search-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
insert-item

Adds item to the container

make-node-for-container
rb-delete-fixup

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-item-if
delete-list

Deletes each item in the list from the container.

delete-node
element-position

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

empty!

Removes all items from the container and returns nil.

empty-p

Returns t if there are no items in the container.

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.

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...

first-element
first-node
height
inorder-walk
inorder-walk-nodes
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.

item-at

Returns the item specified by the indexes.

iteratable-p

Returns true if thing knows how to iterate-nodes.

iterate-elements
iterate-nodes

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

last-element
nth-element

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

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
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.

rotate-left
rotate-right
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*
setffirst-element
setflast-element
size

Returns the number of items currently in the container.

some-element-p
some-item-p

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

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...

unique-elements
unique-nodes
update-element