Common Lisp Package: BINARY-TREES

README:

FUNCTION

Public

DELETE (KEY TREE)

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 (KEY TREE)

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.

INSERT (ITEM TREE)

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.

LOWER-BOUND (KEY TREE)

Return the item in TREE possessing a key which is equal to or less than KEY. Returns NIL if there is no such item.

MAKE-BINARY-TREE (TYPE PRED &KEY KEY TEST)

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.

MAXIMUM (TREE)

Return the item with the maximum key in TREE. It is an error to ask for the maximum item of an empty tree.

MINIMUM (TREE)

Return the item with the minimum key in TREE. It is an error to ask for the minimum item of an empty tree.

SELECT (TREE K)

Return the Kth item (zero-based) in TREE.

SIZE (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

UPPER-BOUND (KEY 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.

Undocumented

EMPTYP (TREE)

POSITION (KEY TREE &KEY FROM-END)

PPRINT-TREE (TREE &OPTIONAL (STREAM *STANDARD-OUTPUT*))

REDUCE (TREE FUNCTION &KEY KEY (INITIAL-VALUE NIL VALUEP) (FROM-END NIL))

SETFSIZE (NEW-VALUE INSTANCE)

Private

BALANCE-INFO (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

COLOR (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

DATUM (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

FIND-NODE-WITH-KEY (TREE KEY)

Find the node in TREE with key KEY. Might return the null node if no such node can be found.

KEY (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

LEFT (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

LEVEL (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

LOWER-BOUND-NODE (KEY TREE)

Return the node in TREE possessing a key which is equal to or less than KEY.

MODCOUNT (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

NODEGEN (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

PRED (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

RANK (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

REBALANCE/DELETE (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

REBALANCE/INSERT (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

ROOT (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

TEST (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

UPPER-BOUND-NODE (KEY TREE)

Return the node in TREE possessing a key which is equal to or greater than KEY.

Undocumented

%MAKE-BINARY-TREE (PRED KEY TEST NODEGEN REBALANCE/INSERT REBALANCE/DELETE)

AA-REBALANCE/DELETE (TREE NODE REPLACEMENT STACK)

AA-REBALANCE/INSERT (TREE DIRECTION-STACK)

AA-TREE-NODE-P (OBJECT)

AVL-REBALANCE/DELETE (TREE NODE REPLACEMENT STACK)

AVL-REBALANCE/INSERT (TREE DIRECTION-STACK)

AVL-TREE-NODE-P (OBJECT)

SETFBALANCE-INFO (NEW-VALUE INSTANCE)

BINARY-TREE-P (OBJECT)

BLACKEN (NODE)

BLACKP (NODE)

SETFCOLOR (NEW-VALUE INSTANCE)

SETFDATUM (NEW-VALUE INSTANCE)

DELETE-NODE (TREE NODE DIRECTION-STACK)

EXTREME-NODE-WITH-PATH (ROOT DIRECTION &OPTIONAL PATH)

FIND-INSERTION-POINT (TREE ITEM-KEY)

FOR-EACH (FUNC TREE FORWARDP)

INDENT-TO-LEVEL (N &OPTIONAL (STREAM *STANDARD-OUTPUT*))

INSERT-CHILD-FOR-STACK-ENTRY (ENTRY CHILD)

SETFLEFT (NEW-VALUE INSTANCE)

SETFLEVEL (NEW-VALUE INSTANCE)

LEVEL* (X)

LOWER-BOUND-NODE-WITH-PATH (KEY TREE PATHP)

MAKE-AA-NODE (DATUM)

MAKE-AVL-NODE (DATUM)

MAKE-ITERATOR (TREE &KEY FORWARDP (CURRENT NIL CURRENTP) (STACK NIL STACKP))

MAKE-RED-BLACK-NODE (DATUM)

MAKE-TREE-NODE (DATUM)

MAXIMUM-NODE (ROOT)

MINIMUM-NODE (ROOT)

SETFMODCOUNT (NEW-VALUE INSTANCE)

SETFRANK (NEW-VALUE INSTANCE)

RED-BLACK-REBALANCE/DELETE (TREE NODE REPLACEMENT NEW-STACK)

RED-BLACK-REBALANCE/INSERT (TREE DIRECTION-STACK)

RED-BLACK-TREE-NODE-P (OBJECT)

REDDEN (NODE)

REDP (NODE)

REVERSE-TREE-FOR-EACH (FUNC TREE)

SETFRIGHT (NEW-VALUE INSTANCE)

SETFROOT (NEW-VALUE INSTANCE)

ROTATE-LEFT (NODE)

ROTATE-RIGHT (NODE)

SELECT-NODE (TREE K)

SELECT-NODE-WITH-PATH (TREE K PATHP)

SET-ROOT-OR-ENTRY-CHILD (TREE ENTRY CHILD)

SKEW (NODE)

SPLIT (NODE)

TREE-FOR-EACH (FUNC TREE)

TREE-NODE-P (OBJECT)

UPDATE-BALANCE-FACTORS (TREE DIRECTION-STACK)

UPDATE-RANKS (DIRECTION-STACK INSERTEDP)

UPPER-BOUND-NODE-WITH-PATH (KEY TREE PATHP)

MACRO

Public

Undocumented

DOTREE ((OBJ-VAR TREE-VAR &OPTIONAL RETURN-VALUE) &BODY BODY)

VARIABLE

Private

Undocumented

*BINARY-TREE-INFO*

CLASS

Public

Undocumented

BINARY-TREE

Private

Undocumented

AA-TREE-NODE

AVL-TREE-NODE

RED-BLACK-TREE-NODE

TREE-NODE

CONSTANT

Private

Undocumented

+AVL-EQUAL+

+AVL-FALLS-LEFT+

+AVL-FALLS-RIGHT+

+AVL-LEANS-LEFT+

+AVL-LEANS-RIGHT+