The binary-search-tree Reference Manual

This is the binary-search-tree Reference Manual, version 0.1.0, generated automatically by Declt version 4.0 beta 2 "William Riker" on Tue Nov 15 04:17:47 2022 GMT+0.

1 Introduction

binary-search-tree

An implementation of the binary search tree data structure.

Install

(ql:quickload :binary-search-tree)

License

Licensed under the MIT License.

2 Systems

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

binary-search-tree

2.1 `binary-search-tree`

An implementation of the binary search tree data structure.

Author

Michael Fiano <mail@mfiano.net>

Home Page

https://git.mfiano.net/mfiano/binary-search-tree

License

MIT

Version

0.1.0

Dependency

mfiano-utils (system).

Source

binary-search-tree.asd.

Child Components

package.lisp (file).
binary-search-tree.lisp (file).

3 Files

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

Lisp

3.1 Lisp

binary-search-tree/binary-search-tree.asd
binary-search-tree/package.lisp
binary-search-tree/binary-search-tree.lisp

3.1.1 `binary-search-tree/binary-search-tree.asd`

Source: binary-search-tree.asd.
Parent Component: binary-search-tree (system).
ASDF Systems: binary-search-tree.

3.1.2 `binary-search-tree/package.lisp`

Source: binary-search-tree.asd.
Parent Component: binary-search-tree (system).
Packages: binary-search-tree.

3.1.3 `binary-search-tree/binary-search-tree.lisp`

Dependency

package.lisp (file).

Source

binary-search-tree.asd.

Parent Component

binary-search-tree (system).

Public Interface

delete (function).
find (function).
insert (function).
make-tree (function).
max (function).
min (function).
next (function).
node (structure).
previous (function).
print-object (method).
print-object (method).
tree (structure).
valid-p (function).
walk (function).

Internals

%make-node (function).
%make-tree (function).
%walk/in-order (function).
%walk/post-order (function).
%walk/pre-order (function).
make-node (function).
node-data (reader).
(setf node-data) (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).
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.

binary-search-tree

4.1 `binary-search-tree`

Source

package.lisp.

Use List

common-lisp.

Public Interface

delete (function).
find (function).
insert (function).
make-tree (function).
max (function).
min (function).
next (function).
node (structure).
previous (function).
tree (structure).
valid-p (function).
walk (function).

Internals

%make-node (function).
%make-tree (function).
%walk/in-order (function).
%walk/post-order (function).
%walk/pre-order (function).
make-node (function).
node-data (reader).
(setf node-data) (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).
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.1 Ordinary functions

Function: delete (tree item) ¶

Package: binary-search-tree.
Source: binary-search-tree.lisp.

Function: find (tree item) ¶

Package: binary-search-tree.
Source: binary-search-tree.lisp.

Function: insert (tree item) ¶

Package: binary-search-tree.
Source: binary-search-tree.lisp.

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

Package: binary-search-tree.
Source: binary-search-tree.lisp.

Function: max (node) ¶

Package: binary-search-tree.
Source: binary-search-tree.lisp.

Function: min (node) ¶

Package: binary-search-tree.
Source: binary-search-tree.lisp.

Function: next (node) ¶

Package: binary-search-tree.
Source: binary-search-tree.lisp.

Function: previous (node) ¶

Package: binary-search-tree.
Source: binary-search-tree.lisp.

Function: valid-p (tree) ¶

Package: binary-search-tree.
Source: binary-search-tree.lisp.

Function: walk (tree func &key order) ¶

Package: binary-search-tree.
Source: binary-search-tree.lisp.

5.1.2 Standalone methods

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

Source: binary-search-tree.lisp.

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

Source: binary-search-tree.lisp.

5.1.3 Structures

Structure: node ¶

Package

binary-search-tree.

Source

binary-search-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).

Structure: tree ¶

Package

binary-search-tree.

Source

binary-search-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) ¶

Package: binary-search-tree.
Source: binary-search-tree.lisp.

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

Package: binary-search-tree.
Source: binary-search-tree.lisp.

Function: %walk/in-order (node func) ¶

Package: binary-search-tree.
Source: binary-search-tree.lisp.

Function: %walk/post-order (node func) ¶

Package: binary-search-tree.
Source: binary-search-tree.lisp.

Function: %walk/pre-order (node func) ¶

Package: binary-search-tree.
Source: binary-search-tree.lisp.

Function: make-node (tree item) ¶

Package: binary-search-tree.
Source: binary-search-tree.lisp.

Reader: node-data (instance) ¶

Writer: (setf node-data) (instance) ¶

Package: binary-search-tree.
Source: binary-search-tree.lisp.
Target Slot: data.

Reader: node-key (instance) ¶

Writer: (setf node-key) (instance) ¶

Package: binary-search-tree.
Source: binary-search-tree.lisp.
Target Slot: key.

Reader: node-left (instance) ¶

Writer: (setf node-left) (instance) ¶

Package: binary-search-tree.
Source: binary-search-tree.lisp.
Target Slot: left.

Function: node-p (node) ¶

Package: binary-search-tree.
Source: binary-search-tree.lisp.

Reader: node-parent (instance) ¶

Writer: (setf node-parent) (instance) ¶

Package: binary-search-tree.
Source: binary-search-tree.lisp.
Target Slot: parent.

Reader: node-right (instance) ¶

Writer: (setf node-right) (instance) ¶

Package: binary-search-tree.
Source: binary-search-tree.lisp.
Target Slot: right.

Reader: node-tree (instance) ¶

Writer: (setf node-tree) (instance) ¶

Package: binary-search-tree.
Source: binary-search-tree.lisp.
Target Slot: tree.

Function: transplant (node1 node2) ¶

Package: binary-search-tree.
Source: binary-search-tree.lisp.

Reader: tree-hash-test (instance) ¶

Writer: (setf tree-hash-test) (instance) ¶

Package: binary-search-tree.
Source: binary-search-tree.lisp.
Target Slot: hash-test.

Reader: tree-item-type (instance) ¶

Writer: (setf tree-item-type) (instance) ¶

Package: binary-search-tree.
Source: binary-search-tree.lisp.
Target Slot: item-type.

Reader: tree-key (instance) ¶

Writer: (setf tree-key) (instance) ¶

Package: binary-search-tree.
Source: binary-search-tree.lisp.
Target Slot: key.

Reader: tree-root (instance) ¶

Writer: (setf tree-root) (instance) ¶

Package: binary-search-tree.
Source: binary-search-tree.lisp.
Target Slot: root.

Reader: tree-sentinel (instance) ¶

Writer: (setf tree-sentinel) (instance) ¶

Package: binary-search-tree.
Source: binary-search-tree.lisp.
Target Slot: sentinel.

Reader: tree-sorter (instance) ¶

Writer: (setf tree-sorter) (instance) ¶

Package: binary-search-tree.
Source: binary-search-tree.lisp.
Target Slot: sorter.

Appendix A Indexes

Concepts
Functions
Variables
Data types

A.1 Concepts

A.2 Functions

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

	Index Entry	Section

%
	`%make-node`:	Private ordinary functions
	`%make-tree`:	Private ordinary functions
	`%walk/in-order`:	Private ordinary functions
	`%walk/post-order`:	Private ordinary functions
	`%walk/pre-order`:	Private ordinary functions

(
	`(setf node-data)`:	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

D
	`delete`:	Public ordinary functions

F
	`find`:	Public ordinary functions
	`Function, %make-node`:	Private ordinary functions
	`Function, %make-tree`:	Private ordinary functions
	`Function, %walk/in-order`:	Private ordinary functions
	`Function, %walk/post-order`:	Private ordinary functions
	`Function, %walk/pre-order`:	Private ordinary functions
	`Function, (setf node-data)`:	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, delete`:	Public ordinary functions
	`Function, find`:	Public ordinary functions
	`Function, insert`:	Public ordinary functions
	`Function, make-node`:	Private ordinary functions
	`Function, make-tree`:	Public ordinary functions
	`Function, max`:	Public ordinary functions
	`Function, min`:	Public ordinary functions
	`Function, next`:	Public ordinary functions
	`Function, node-data`:	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, previous`:	Public 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

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

N
	`next`:	Public ordinary functions
	`node-data`:	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
	`previous`:	Public ordinary functions
	`print-object`:	Public standalone methods
	`print-object`:	Public standalone methods

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:	% ( D F I M N P T V W

A.3 Variables

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

	Index Entry	Section

D
	`data`:	Public structures

H
	`hash-test`:	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, data`:	Public structures
	`Slot, hash-test`:	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:	D H I K L P R S T

A.4 Data types

Jump to:	B F N P S T

	Index Entry	Section

B
	`binary-search-tree`:	The binary-search-tree system
	`binary-search-tree`:	The binary-search-tree package
	`binary-search-tree.asd`:	The binary-search-tree/binary-search-tree․asd file
	`binary-search-tree.lisp`:	The binary-search-tree/binary-search-tree․lisp file

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

N
	`node`:	Public structures

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

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

T
	`tree`:	Public structures

Jump to:	B F N P S T

The binary-search-tree Reference Manual

The binary-search-tree Reference Manual

Table of Contents

1 Introduction

binary-search-tree

Install

License

2 Systems

2.1 binary-search-tree

3 Files

3.1 Lisp

3.1.1 binary-search-tree/binary-search-tree.asd

3.1.2 binary-search-tree/package.lisp

3.1.3 binary-search-tree/binary-search-tree.lisp

4 Packages

4.1 binary-search-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 `binary-search-tree`

3.1.1 `binary-search-tree/binary-search-tree.asd`

3.1.2 `binary-search-tree/package.lisp`

3.1.3 `binary-search-tree/binary-search-tree.lisp`

4.1 `binary-search-tree`