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 Mon Aug 15 03:14:32 2022 GMT+0.

1 Introduction

avl-tree

An implementation of the AVL tree data structure.

Warning: This hasn't been tested out in the wild yet. If you run into any issues, please let me know and I will do what I can to address them.

Install

(ql:quickload :avl-tree)

License

Licensed under the MIT License.

2 Systems

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

avl-tree

2.1 `avl-tree`

An implementation of the AVL tree data structure.

Author

Michael Fiano <mail@mfiano.net>

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

package.lisp (file).
avl-tree.lisp (file).

3 Files

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

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

clear (function).
copy (function).
delete (function).
find (function).
insert (function).
make-tree (function).
node (structure).
print-object (method).
print-object (method).
tree (structure).
valid-p (function).
walk (function).

Internals

%make-node (function).
%make-tree (function).
delete-rebalance (function).
insert-rebalance (function).
make-node (function).
min (function).
node-balance-factor (reader).
(setf node-balance-factor) (writer).
node-data (reader).
(setf node-data) (writer).
node-height (reader).
(setf node-height) (writer).
node-key (reader).
(setf node-key) (writer).
node-left (reader).
(setf node-left) (writer).
node-p (function).
node-parent (reader).
(setf node-parent) (writer).
node-right (reader).
(setf node-right) (writer).
node-tree (reader).
(setf node-tree) (writer).
rotate/left (function).
rotate/left-right (function).
rotate/right (function).
rotate/right-left (function).
transplant (function).
tree-hash-test (reader).
(setf tree-hash-test) (writer).
tree-item-type (reader).
(setf tree-item-type) (writer).
tree-key (reader).
(setf tree-key) (writer).
tree-root (reader).
(setf tree-root) (writer).
tree-sentinel (reader).
(setf tree-sentinel) (writer).
tree-sorter (reader).
(setf tree-sorter) (writer).

4 Packages

Packages are listed by definition order.

avl-tree

4.1 `avl-tree`

Source

package.lisp.

Use List

common-lisp.

Public Interface

clear (function).
copy (function).
delete (function).
find (function).
insert (function).
make-tree (function).
node (structure).
tree (structure).
valid-p (function).
walk (function).

Internals

%make-node (function).
%make-tree (function).
delete-rebalance (function).
insert-rebalance (function).
make-node (function).
min (function).
node-balance-factor (reader).
(setf node-balance-factor) (writer).
node-data (reader).
(setf node-data) (writer).
node-height (reader).
(setf node-height) (writer).
node-key (reader).
(setf node-key) (writer).
node-left (reader).
(setf node-left) (writer).
node-p (function).
node-parent (reader).
(setf node-parent) (writer).
node-right (reader).
(setf node-right) (writer).
node-tree (reader).
(setf node-tree) (writer).
rotate/left (function).
rotate/left-right (function).
rotate/right (function).
rotate/right-left (function).
transplant (function).
tree-hash-test (reader).
(setf tree-hash-test) (writer).
tree-item-type (reader).
(setf tree-item-type) (writer).
tree-key (reader).
(setf tree-key) (writer).
tree-root (reader).
(setf tree-root) (writer).
tree-sentinel (reader).
(setf tree-sentinel) (writer).
tree-sorter (reader).
(setf tree-sorter) (writer).

5 Definitions

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

Public Interface
Internals

5.1 Public Interface

Ordinary functions
Standalone methods
Structures

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 ((node node) stream) ¶

Source: avl-tree.lisp.

Method: print-object ((tree tree) 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

Ordinary functions

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

Concepts
Functions
Variables
Data types

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

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

A.3 Variables

Jump to:	B D H I K L P R S T

	Index Entry	Section

B
	`balance-factor`:	Public structures

D
	`data`:	Public structures

H
	`hash-test`:	Public structures
	`height`:	Public structures

I
	`item-type`:	Public structures

K
	`key`:	Public structures
	`key`:	Public structures

L
	`left`:	Public structures

P
	`parent`:	Public structures

R
	`right`:	Public structures
	`root`:	Public structures

S
	`sentinel`:	Public structures
	`Slot, balance-factor`:	Public structures
	`Slot, data`:	Public structures
	`Slot, hash-test`:	Public structures
	`Slot, height`:	Public structures
	`Slot, item-type`:	Public structures
	`Slot, key`:	Public structures
	`Slot, key`:	Public structures
	`Slot, left`:	Public structures
	`Slot, parent`:	Public structures
	`Slot, right`:	Public structures
	`Slot, root`:	Public structures
	`Slot, sentinel`:	Public structures
	`Slot, sorter`:	Public structures
	`Slot, tree`:	Public structures
	`sorter`:	Public structures

T
	`tree`:	Public structures

Jump to:	B D H I K L P R S T

A.4 Data types

Jump to:	A F N P S T

	Index Entry	Section

A
	`avl-tree`:	The avl-tree system
	`avl-tree`:	The avl-tree package
	`avl-tree.asd`:	The avl-tree/avl-tree․asd file
	`avl-tree.lisp`:	The avl-tree/avl-tree․lisp file

F
	`File, avl-tree.asd`:	The avl-tree/avl-tree․asd file
	`File, avl-tree.lisp`:	The avl-tree/avl-tree․lisp file
	`File, package.lisp`:	The avl-tree/package․lisp file

N
	`node`:	Public structures

P
	`Package, avl-tree`:	The avl-tree package
	`package.lisp`:	The avl-tree/package․lisp file

S
	`Structure, node`:	Public structures
	`Structure, tree`:	Public structures
	`System, avl-tree`:	The avl-tree system

T
	`tree`:	Public structures

Jump to:	A F N P S T

The avl-tree Reference Manual

The avl-tree Reference Manual

Table of Contents

1 Introduction

avl-tree

Install

License

2 Systems

2.1 avl-tree

3 Files

3.1 Lisp

3.1.1 avl-tree/avl-tree.asd

3.1.2 avl-tree/package.lisp

3.1.3 avl-tree/avl-tree.lisp

4 Packages

4.1 avl-tree

5 Definitions

5.1 Public Interface

5.1.1 Ordinary functions

5.1.2 Standalone methods

5.1.3 Structures

5.2 Internals

5.2.1 Ordinary functions

Appendix A Indexes

A.1 Concepts

A.2 Functions

A.3 Variables

A.4 Data types

2.1 `avl-tree`

3.1.1 `avl-tree/avl-tree.asd`

3.1.2 `avl-tree/package.lisp`

3.1.3 `avl-tree/avl-tree.lisp`

4.1 `avl-tree`