The avl-tree Reference Manual

Table of Contents

Next: , Previous: , Up: (dir)   [Contents][Index]

The avl-tree Reference Manual

This is the avl-tree Reference Manual, generated automatically by Declt version 3.0 "Montgomery Scott" on Tue Apr 28 10:33:39 2020 GMT+0.


Next: , Previous: , Up: Top   [Contents][Index]

1 Introduction

avl-tree

An implementation of the AVL tree data structure.

License

Copyright © Michael Fiano mail@michaelfiano.com.

Licensed under the MIT License.


Next: , Previous: , Up: Top   [Contents][Index]

2 Systems

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


Previous: , Up: Systems   [Contents][Index]

2.1 avl-tree

Maintainer

Michael Fiano <mail@michaelfiano.com>

Author

Michael Fiano <mail@michaelfiano.com>

Home Page

https://www.michaelfiano.com/projects/avl-tree

Source Control

(:git "https://github.com/mfiano/avl-tree.git")

Bug Tracker

https://github.com/mfiano/avl-tree/issues

License

MIT

Description

An implementation of the AVL tree data structure.

Dependencies
Source

avl-tree.asd (file)

Components

Next: , Previous: , Up: Top   [Contents][Index]

3 Files

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


Previous: , Up: Files   [Contents][Index]

3.1 Lisp


Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.1 avl-tree.asd

Location

/home/quickref/quicklisp/dists/quicklisp/software/avl-tree-20200427-git/avl-tree.asd

Systems

avl-tree (system)


Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.2 avl-tree/package.lisp

Parent

avl-tree (system)

Location

package.lisp

Packages

avl-tree


Previous: , Up: Lisp files   [Contents][Index]

3.1.3 avl-tree/avl-tree.lisp

Dependency

package.lisp (file)

Parent

avl-tree (system)

Location

avl-tree.lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Top   [Contents][Index]

4 Packages

Packages are listed by definition order.


Previous: , Up: Packages   [Contents][Index]

4.1 avl-tree

Source

package.lisp (file)

Use List

common-lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Top   [Contents][Index]

5 Definitions

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


Next: , Previous: , Up: Definitions   [Contents][Index]

5.1 Exported definitions


Next: , Previous: , Up: Exported definitions   [Contents][Index]

5.1.1 Functions

Function: delete TREE ITEM
Package

avl-tree

Source

avl-tree.lisp (file)

Function: find TREE ITEM
Package

avl-tree

Source

avl-tree.lisp (file)

Function: insert TREE ITEM
Package

avl-tree

Source

avl-tree.lisp (file)

Function: make-tree &key ITEM-TYPE KEY SORT HASH-TEST
Package

avl-tree

Source

avl-tree.lisp (file)

Function: valid-p TREE
Package

avl-tree

Source

avl-tree.lisp (file)

Function: walk TREE FUNC
Package

avl-tree

Source

avl-tree.lisp (file)


Previous: , Up: Exported definitions   [Contents][Index]

5.1.2 Structures

Structure: node ()
Package

avl-tree

Source

avl-tree.lisp (file)

Direct superclasses

structure-object (structure)

Direct methods

print-object (method)

Direct slots
Slot: tree
Readers

node-tree (function)

Writers

(setf node-tree) (function)

Slot: key
Readers

node-key (function)

Writers

(setf node-key) (function)

Slot: data
Readers

node-data (function)

Writers

(setf node-data) (function)

Slot: parent
Readers

node-parent (function)

Writers

(setf node-parent) (function)

Slot: left
Readers

node-left (function)

Writers

(setf node-left) (function)

Slot: right
Readers

node-right (function)

Writers

(setf node-right) (function)

Slot: height
Type

fixnum

Initform

0

Readers

node-height (function)

Writers

(setf node-height) (function)

Slot: balance-factor
Type

fixnum

Initform

0

Readers

node-balance-factor (function)

Writers

(setf node-balance-factor) (function)

Structure: tree ()
Package

avl-tree

Source

avl-tree.lisp (file)

Direct superclasses

structure-object (structure)

Direct methods

print-object (method)

Direct slots
Slot: sentinel
Readers

tree-sentinel (function)

Writers

(setf tree-sentinel) (function)

Slot: root
Readers

tree-root (function)

Writers

(setf tree-root) (function)

Slot: item-type
Readers

tree-item-type (function)

Writers

(setf tree-item-type) (function)

Slot: key
Type

function

Initform

(function identity)

Readers

tree-key (function)

Writers

(setf tree-key) (function)

Slot: sorter
Type

function

Initform

(function <)

Readers

tree-sorter (function)

Writers

(setf tree-sorter) (function)

Slot: hash-test
Type

function

Initform

(function eql)

Readers

tree-hash-test (function)

Writers

(setf tree-hash-test) (function)


Previous: , Up: Definitions   [Contents][Index]

5.2 Internal definitions


Previous: , Up: Internal definitions   [Contents][Index]

5.2.1 Functions

Function: %make-node &key (TREE TREE) (KEY KEY) (DATA DATA) (PARENT PARENT) (LEFT LEFT) (RIGHT RIGHT) (HEIGHT HEIGHT) (BALANCE-FACTOR BALANCE-FACTOR)
Package

avl-tree

Source

avl-tree.lisp (file)

Function: %make-tree &key (SENTINEL SENTINEL) (ROOT ROOT) (ITEM-TYPE ITEM-TYPE) (KEY KEY) (SORTER SORTER) (HASH-TEST HASH-TEST)
Package

avl-tree

Source

avl-tree.lisp (file)

Function: delete-rebalance NEW-ROOT DIRECTION
Package

avl-tree

Source

avl-tree.lisp (file)

Function: insert-rebalance NEW
Package

avl-tree

Source

avl-tree.lisp (file)

Function: make-node TREE ITEM
Package

avl-tree

Source

avl-tree.lisp (file)

Function: min NODE
Package

avl-tree

Source

avl-tree.lisp (file)

Function: node-balance-factor INSTANCE
Function: (setf node-balance-factor) VALUE INSTANCE
Package

avl-tree

Source

avl-tree.lisp (file)

Function: node-data INSTANCE
Function: (setf node-data) VALUE INSTANCE
Package

avl-tree

Source

avl-tree.lisp (file)

Function: node-height INSTANCE
Function: (setf node-height) VALUE INSTANCE
Package

avl-tree

Source

avl-tree.lisp (file)

Function: node-key INSTANCE
Function: (setf node-key) VALUE INSTANCE
Package

avl-tree

Source

avl-tree.lisp (file)

Function: node-left INSTANCE
Function: (setf node-left) VALUE INSTANCE
Package

avl-tree

Source

avl-tree.lisp (file)

Function: node-p NODE
Package

avl-tree

Source

avl-tree.lisp (file)

Function: node-parent INSTANCE
Function: (setf node-parent) VALUE INSTANCE
Package

avl-tree

Source

avl-tree.lisp (file)

Function: node-right INSTANCE
Function: (setf node-right) VALUE INSTANCE
Package

avl-tree

Source

avl-tree.lisp (file)

Function: node-tree INSTANCE
Function: (setf node-tree) VALUE INSTANCE
Package

avl-tree

Source

avl-tree.lisp (file)

Function: rotate/left NODE
Package

avl-tree

Source

avl-tree.lisp (file)

Function: rotate/left-right NODE
Package

avl-tree

Source

avl-tree.lisp (file)

Function: rotate/right NODE
Package

avl-tree

Source

avl-tree.lisp (file)

Function: rotate/right-left NODE
Package

avl-tree

Source

avl-tree.lisp (file)

Function: transplant NODE1 NODE2
Package

avl-tree

Source

avl-tree.lisp (file)

Function: tree-hash-test INSTANCE
Function: (setf tree-hash-test) VALUE INSTANCE
Package

avl-tree

Source

avl-tree.lisp (file)

Function: tree-item-type INSTANCE
Function: (setf tree-item-type) VALUE INSTANCE
Package

avl-tree

Source

avl-tree.lisp (file)

Function: tree-key INSTANCE
Function: (setf tree-key) VALUE INSTANCE
Package

avl-tree

Source

avl-tree.lisp (file)

Function: tree-root INSTANCE
Function: (setf tree-root) VALUE INSTANCE
Package

avl-tree

Source

avl-tree.lisp (file)

Function: tree-sentinel INSTANCE
Function: (setf tree-sentinel) VALUE INSTANCE
Package

avl-tree

Source

avl-tree.lisp (file)

Function: tree-sorter INSTANCE
Function: (setf tree-sorter) VALUE INSTANCE
Package

avl-tree

Source

avl-tree.lisp (file)


Previous: , Up: Top   [Contents][Index]

Appendix A Indexes


Next: , Previous: , Up: Indexes   [Contents][Index]

A.1 Concepts

Jump to:   A   F   L  
Index Entry  Section

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

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

L
Lisp File, avl-tree.asd: The avl-tree․asd file
Lisp File, avl-tree/avl-tree.lisp: The avl-tree/avl-tree․lisp file
Lisp File, avl-tree/package.lisp: The avl-tree/package․lisp file

Jump to:   A   F   L  

Next: , Previous: , Up: Indexes   [Contents][Index]

A.2 Functions

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

%
%make-node: Internal functions
%make-tree: Internal functions

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

D
delete: Exported functions
delete-rebalance: Internal functions

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

I
insert: Exported functions
insert-rebalance: Internal functions

M
make-node: Internal functions
make-tree: Exported functions
min: Internal functions

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

R
rotate/left: Internal functions
rotate/left-right: Internal functions
rotate/right: Internal functions
rotate/right-left: Internal functions

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

V
valid-p: Exported functions

W
walk: Exported functions

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

Next: , Previous: , Up: Indexes   [Contents][Index]

A.3 Variables

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

B
balance-factor: Exported structures

D
data: Exported structures

H
hash-test: Exported structures
height: Exported structures

I
item-type: Exported structures

K
key: Exported structures
key: Exported structures

L
left: Exported structures

P
parent: Exported structures

R
right: Exported structures
root: Exported structures

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

T
tree: Exported structures

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

Previous: , Up: Indexes   [Contents][Index]

A.4 Data types

Jump to:   A   N   P   S   T  
Index Entry  Section

A
avl-tree: The avl-tree system
avl-tree: The avl-tree package

N
node: Exported structures

P
Package, avl-tree: The avl-tree package

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

T
tree: Exported structures

Jump to:   A   N   P   S   T