The avl-tree Reference Manual

Table of Contents

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.

1 Introduction

avl-tree

An implementation of the AVL tree data structure.

License

Copyright © Michael Fiano mail@michaelfiano.com.

Licensed under the MIT License.

2 Systems

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

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

• alexandria
• golden-utils

Source

avl-tree.asd (file)

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.

3.1 Lisp

3.1.1 avl-tree.asd

Location

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

Systems

avl-tree (system)

3.1.2 avl-tree/package.lisp

Parent

avl-tree (system)

Location

package.lisp

Packages

avl-tree

3.1.3 avl-tree/avl-tree.lisp

Dependency

package.lisp (file)

Parent

avl-tree (system)

Location

avl-tree.lisp

Exported Definitions

• delete (function)
• find (function)
• insert (function)
• make-tree (function)
• node (structure)
• tree (structure)
• valid-p (function)
• walk (function)

Internal Definitions

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

4 Packages

Packages are listed by definition order.

4.1 avl-tree

Source

package.lisp (file)

Use List

common-lisp

Exported Definitions

• delete (function)
• find (function)
• insert (function)
• make-tree (function)
• node (structure)
• tree (structure)
• valid-p (function)
• walk (function)

Internal Definitions

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

5 Definitions

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

5.1 Exported definitions

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)

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)

5.2 Internal definitions

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)

Appendix A Indexes

A.1 Concepts

A.2 Functions

A.3 Variables

A.4 Data types