The avl-tree Reference Manual

This is the avl-tree Reference Manual, version 0.1.0, generated automatically by Declt version 4.0 beta 2 "William Riker" on Sun Sep 15 03:22:18 2024 GMT+0.

Table of Contents


1 Introduction


2 Systems

The main system appears first, followed by any subsystem dependency.


2.1 avl-tree

An implementation of the AVL tree data structure.

Author

Michael Fiano <>

Home Page

https://git.mfiano.net/mfiano/avl-tree

License

MIT

Version

0.1.0

Dependency

mfiano-utils (system).

Source

avl-tree.asd.

Child Components

3 Files

Files are sorted by type and then listed depth-first from the systems components trees.


3.1 Lisp


3.1.1 avl-tree/avl-tree.asd

Source

avl-tree.asd.

Parent Component

avl-tree (system).

ASDF Systems

avl-tree.


3.1.2 avl-tree/package.lisp

Source

avl-tree.asd.

Parent Component

avl-tree (system).

Packages

avl-tree.


3.1.3 avl-tree/avl-tree.lisp

Dependency

package.lisp (file).

Source

avl-tree.asd.

Parent Component

avl-tree (system).

Public Interface
Internals

4 Packages

Packages are listed by definition order.


4.1 avl-tree

Source

package.lisp.

Use List

common-lisp.

Public Interface
Internals

5 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.


5.1 Public Interface


5.1.1 Ordinary functions

Function: clear (tree)
Package

avl-tree.

Source

avl-tree.lisp.

Function: copy (tree &key key sort)
Package

avl-tree.

Source

avl-tree.lisp.

Function: delete (tree item)
Package

avl-tree.

Source

avl-tree.lisp.

Function: find (tree item)
Package

avl-tree.

Source

avl-tree.lisp.

Function: insert (tree item)
Package

avl-tree.

Source

avl-tree.lisp.

Function: make-tree (&key item-type key sort hash-test)
Package

avl-tree.

Source

avl-tree.lisp.

Function: valid-p (tree)
Package

avl-tree.

Source

avl-tree.lisp.

Function: walk (tree func)
Package

avl-tree.

Source

avl-tree.lisp.


5.1.2 Standalone methods

Method: print-object ((tree tree) stream)
Source

avl-tree.lisp.

Method: print-object ((node node) stream)
Source

avl-tree.lisp.


5.1.3 Structures

Structure: node
Package

avl-tree.

Source

avl-tree.lisp.

Direct superclasses

structure-object.

Direct methods

print-object.

Direct slots
Slot: tree
Readers

node-tree.

Writers

(setf node-tree).

Slot: key
Readers

node-key.

Writers

(setf node-key).

Slot: data
Readers

node-data.

Writers

(setf node-data).

Slot: parent
Readers

node-parent.

Writers

(setf node-parent).

Slot: left
Readers

node-left.

Writers

(setf node-left).

Slot: right
Readers

node-right.

Writers

(setf node-right).

Slot: height
Type

fixnum

Initform

0

Readers

node-height.

Writers

(setf node-height).

Slot: balance-factor
Type

fixnum

Initform

0

Readers

node-balance-factor.

Writers

(setf node-balance-factor).

Structure: tree
Package

avl-tree.

Source

avl-tree.lisp.

Direct superclasses

structure-object.

Direct methods

print-object.

Direct slots
Slot: sentinel
Readers

tree-sentinel.

Writers

(setf tree-sentinel).

Slot: root
Readers

tree-root.

Writers

(setf tree-root).

Slot: item-type
Readers

tree-item-type.

Writers

(setf tree-item-type).

Slot: key
Type

function

Initform

(function identity)

Readers

tree-key.

Writers

(setf tree-key).

Slot: sorter
Type

function

Initform

(function <)

Readers

tree-sorter.

Writers

(setf tree-sorter).

Slot: hash-test
Type

function

Initform

(function eql)

Readers

tree-hash-test.

Writers

(setf tree-hash-test).


5.2 Internals


5.2.1 Ordinary functions

Function: %make-node (&key tree key data parent left right height balance-factor)
Package

avl-tree.

Source

avl-tree.lisp.

Function: %make-tree (&key sentinel root item-type key sorter hash-test)
Package

avl-tree.

Source

avl-tree.lisp.

Function: delete-rebalance (new-root direction)
Package

avl-tree.

Source

avl-tree.lisp.

Function: insert-rebalance (new)
Package

avl-tree.

Source

avl-tree.lisp.

Function: make-node (tree item)
Package

avl-tree.

Source

avl-tree.lisp.

Function: min (node)
Package

avl-tree.

Source

avl-tree.lisp.

Reader: node-balance-factor (instance)
Writer: (setf node-balance-factor) (instance)
Package

avl-tree.

Source

avl-tree.lisp.

Target Slot

balance-factor.

Reader: node-data (instance)
Writer: (setf node-data) (instance)
Package

avl-tree.

Source

avl-tree.lisp.

Target Slot

data.

Reader: node-height (instance)
Writer: (setf node-height) (instance)
Package

avl-tree.

Source

avl-tree.lisp.

Target Slot

height.

Reader: node-key (instance)
Writer: (setf node-key) (instance)
Package

avl-tree.

Source

avl-tree.lisp.

Target Slot

key.

Reader: node-left (instance)
Writer: (setf node-left) (instance)
Package

avl-tree.

Source

avl-tree.lisp.

Target Slot

left.

Function: node-p (node)
Package

avl-tree.

Source

avl-tree.lisp.

Reader: node-parent (instance)
Writer: (setf node-parent) (instance)
Package

avl-tree.

Source

avl-tree.lisp.

Target Slot

parent.

Reader: node-right (instance)
Writer: (setf node-right) (instance)
Package

avl-tree.

Source

avl-tree.lisp.

Target Slot

right.

Reader: node-tree (instance)
Writer: (setf node-tree) (instance)
Package

avl-tree.

Source

avl-tree.lisp.

Target Slot

tree.

Function: rotate/left (node)
Package

avl-tree.

Source

avl-tree.lisp.

Function: rotate/left-right (node)
Package

avl-tree.

Source

avl-tree.lisp.

Function: rotate/right (node)
Package

avl-tree.

Source

avl-tree.lisp.

Function: rotate/right-left (node)
Package

avl-tree.

Source

avl-tree.lisp.

Function: transplant (node1 node2)
Package

avl-tree.

Source

avl-tree.lisp.

Reader: tree-hash-test (instance)
Writer: (setf tree-hash-test) (instance)
Package

avl-tree.

Source

avl-tree.lisp.

Target Slot

hash-test.

Reader: tree-item-type (instance)
Writer: (setf tree-item-type) (instance)
Package

avl-tree.

Source

avl-tree.lisp.

Target Slot

item-type.

Reader: tree-key (instance)
Writer: (setf tree-key) (instance)
Package

avl-tree.

Source

avl-tree.lisp.

Target Slot

key.

Reader: tree-root (instance)
Writer: (setf tree-root) (instance)
Package

avl-tree.

Source

avl-tree.lisp.

Target Slot

root.

Reader: tree-sentinel (instance)
Writer: (setf tree-sentinel) (instance)
Package

avl-tree.

Source

avl-tree.lisp.

Target Slot

sentinel.

Reader: tree-sorter (instance)
Writer: (setf tree-sorter) (instance)
Package

avl-tree.

Source

avl-tree.lisp.

Target Slot

sorter.


Appendix A Indexes


A.1 Concepts


A.2 Functions

Jump to:   %   (  
C   D   F   I   M   N   P   R   T   V   W  
Index Entry  Section

%
%make-node: Private ordinary functions
%make-tree: Private ordinary functions

(
(setf node-balance-factor): Private ordinary functions
(setf node-data): Private ordinary functions
(setf node-height): Private ordinary functions
(setf node-key): Private ordinary functions
(setf node-left): Private ordinary functions
(setf node-parent): Private ordinary functions
(setf node-right): Private ordinary functions
(setf node-tree): Private ordinary functions
(setf tree-hash-test): Private ordinary functions
(setf tree-item-type): Private ordinary functions
(setf tree-key): Private ordinary functions
(setf tree-root): Private ordinary functions
(setf tree-sentinel): Private ordinary functions
(setf tree-sorter): Private ordinary functions

C
clear: Public ordinary functions
copy: Public ordinary functions

D
delete: Public ordinary functions
delete-rebalance: Private ordinary functions

F
find: Public ordinary functions
Function, %make-node: Private ordinary functions
Function, %make-tree: Private ordinary functions
Function, (setf node-balance-factor): Private ordinary functions
Function, (setf node-data): Private ordinary functions
Function, (setf node-height): Private ordinary functions
Function, (setf node-key): Private ordinary functions
Function, (setf node-left): Private ordinary functions
Function, (setf node-parent): Private ordinary functions
Function, (setf node-right): Private ordinary functions
Function, (setf node-tree): Private ordinary functions
Function, (setf tree-hash-test): Private ordinary functions
Function, (setf tree-item-type): Private ordinary functions
Function, (setf tree-key): Private ordinary functions
Function, (setf tree-root): Private ordinary functions
Function, (setf tree-sentinel): Private ordinary functions
Function, (setf tree-sorter): Private ordinary functions
Function, clear: Public ordinary functions
Function, copy: Public ordinary functions
Function, delete: Public ordinary functions
Function, delete-rebalance: Private ordinary functions
Function, find: Public ordinary functions
Function, insert: Public ordinary functions
Function, insert-rebalance: Private ordinary functions
Function, make-node: Private ordinary functions
Function, make-tree: Public ordinary functions
Function, min: Private ordinary functions
Function, node-balance-factor: Private ordinary functions
Function, node-data: Private ordinary functions
Function, node-height: Private ordinary functions
Function, node-key: Private ordinary functions
Function, node-left: Private ordinary functions
Function, node-p: Private ordinary functions
Function, node-parent: Private ordinary functions
Function, node-right: Private ordinary functions
Function, node-tree: Private ordinary functions
Function, rotate/left: Private ordinary functions
Function, rotate/left-right: Private ordinary functions
Function, rotate/right: Private ordinary functions
Function, rotate/right-left: Private ordinary functions
Function, transplant: Private ordinary functions
Function, tree-hash-test: Private ordinary functions
Function, tree-item-type: Private ordinary functions
Function, tree-key: Private ordinary functions
Function, tree-root: Private ordinary functions
Function, tree-sentinel: Private ordinary functions
Function, tree-sorter: Private ordinary functions
Function, valid-p: Public ordinary functions
Function, walk: Public ordinary functions

I
insert: Public ordinary functions
insert-rebalance: Private ordinary functions

M
make-node: Private ordinary functions
make-tree: Public ordinary functions
Method, print-object: Public standalone methods
Method, print-object: Public standalone methods
min: Private ordinary functions

N
node-balance-factor: Private ordinary functions
node-data: Private ordinary functions
node-height: Private ordinary functions
node-key: Private ordinary functions
node-left: Private ordinary functions
node-p: Private ordinary functions
node-parent: Private ordinary functions
node-right: Private ordinary functions
node-tree: Private ordinary functions

P
print-object: Public standalone methods
print-object: Public standalone methods

R
rotate/left: Private ordinary functions
rotate/left-right: Private ordinary functions
rotate/right: Private ordinary functions
rotate/right-left: Private ordinary functions

T
transplant: Private ordinary functions
tree-hash-test: Private ordinary functions
tree-item-type: Private ordinary functions
tree-key: Private ordinary functions
tree-root: Private ordinary functions
tree-sentinel: Private ordinary functions
tree-sorter: Private ordinary functions

V
valid-p: Public ordinary functions

W
walk: Public ordinary functions