The red-black-tree Reference Manual

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

The red-black-tree Reference Manual

This is the red-black-tree Reference Manual, version 0.1.0, generated automatically by Declt version 4.0 beta 2 "William Riker" on Mon Aug 15 05:45:43 2022 GMT+0.

Table of Contents


1 Introduction

red-black-tree

An implementation of the red-black tree data structure.

Install

(ql:quickload :red-black-tree)

License

Copyright © 2018-2022 Michael Fiano mail@mfiano.net

Licensed under the MIT License.


2 Systems

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


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

2.1 red-black-tree

An implementation of the red-black search tree data structure.

Author

Michael Fiano <mail@mfiano.net>

Home Page

https://git.mfiano.net/mfiano/red-black-tree

License

MIT

Version

0.1.0

Dependency

mfiano-utils (system).

Source

red-black-tree.asd.

Child Components

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   [Contents][Index]

3.1.1 red-black-tree/red-black-tree.asd

Source

red-black-tree.asd.

Parent Component

red-black-tree (system).

ASDF Systems

red-black-tree.


3.1.2 red-black-tree/package.lisp

Source

red-black-tree.asd.

Parent Component

red-black-tree (system).

Packages

red-black-tree.


3.1.3 red-black-tree/red-black-tree.lisp

Dependency

package.lisp (file).

Source

red-black-tree.asd.

Parent Component

red-black-tree (system).

Public Interface
Internals

4 Packages

Packages are listed by definition order.


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

4.1 red-black-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.


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

5.1 Public Interface


5.1.1 Ordinary functions

Function: delete (tree item)
Package

red-black-tree.

Source

red-black-tree.lisp.

Function: delete-node (tree node)
Package

red-black-tree.

Source

red-black-tree.lisp.

Function: find (tree item)
Package

red-black-tree.

Source

red-black-tree.lisp.

Function: insert (tree item)
Package

red-black-tree.

Source

red-black-tree.lisp.

Function: make-tree (&key key-func sort-func)
Package

red-black-tree.

Source

red-black-tree.lisp.

Function: max (node)
Package

red-black-tree.

Source

red-black-tree.lisp.

Function: min (node)
Package

red-black-tree.

Source

red-black-tree.lisp.

Function: next (node)
Package

red-black-tree.

Source

red-black-tree.lisp.

Function: previous (node)
Package

red-black-tree.

Source

red-black-tree.lisp.

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

red-black-tree.

Source

red-black-tree.lisp.

Target Slot

tree.

Function: valid-p (tree)
Package

red-black-tree.

Source

red-black-tree.lisp.

Function: walk (tree func &key order)
Package

red-black-tree.

Source

red-black-tree.lisp.


5.1.2 Standalone methods

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

red-black-tree.lisp.

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

red-black-tree.lisp.


5.1.3 Structures

Structure: node
Package

red-black-tree.

Source

red-black-tree.lisp.

Direct superclasses

structure-object.

Direct methods

print-object.

Direct slots
Slot: tree
Type

(or red-black-tree:tree null)

Readers

tree.

Writers

(setf tree).

Slot: parent
Type

(or red-black-tree:node null)

Readers

parent.

Writers

(setf parent).

Slot: left
Type

(or red-black-tree:node null)

Readers

left.

Writers

(setf left).

Slot: right
Type

(or red-black-tree:node null)

Readers

right.

Writers

(setf right).

Slot: color
Type

(member :red :black)

Initform

:black

Readers

color.

Writers

(setf color).

Slot: key
Readers

key.

Writers

(setf key).

Slot: value
Readers

value.

Writers

(setf value).

Structure: tree
Package

red-black-tree.

Source

red-black-tree.lisp.

Direct superclasses

structure-object.

Direct methods

print-object.

Direct slots
Slot: sentinel
Type

(or red-black-tree:node null)

Readers

sentinel.

Writers

(setf sentinel).

Slot: root
Type

(or red-black-tree:node null)

Readers

root.

Writers

(setf root).

Slot: key-func
Type

function

Initform

(function identity)

Readers

key-func.

Writers

(setf key-func).

Slot: sort-func
Type

function

Initform

(function <)

Readers

sort-func.

Writers

(setf sort-func).


5.2 Internals


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

5.2.1 Ordinary functions

Function: %make-node (&key tree parent left right color key value)
Package

red-black-tree.

Source

red-black-tree.lisp.

Function: %make-tree (&key sentinel root key-func sort-func)
Package

red-black-tree.

Source

red-black-tree.lisp.

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

red-black-tree.

Source

red-black-tree.lisp.

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

red-black-tree.

Source

red-black-tree.lisp.

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

red-black-tree.

Source

red-black-tree.lisp.

Reader: color (instance)
Writer: (setf color) (instance)
Package

red-black-tree.

Source

red-black-tree.lisp.

Target Slot

color.

Function: delete/fixup (tree node)
Package

red-black-tree.

Source

red-black-tree.lisp.

Function: insert-fixup (tree node)
Package

red-black-tree.

Source

red-black-tree.lisp.

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

red-black-tree.

Source

red-black-tree.lisp.

Target Slot

key.

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

red-black-tree.

Source

red-black-tree.lisp.

Target Slot

key-func.

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

red-black-tree.

Source

red-black-tree.lisp.

Target Slot

left.

Function: make-node (tree item)
Package

red-black-tree.

Source

red-black-tree.lisp.

Function: node-p (node)
Package

red-black-tree.

Source

red-black-tree.lisp.

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

red-black-tree.

Source

red-black-tree.lisp.

Target Slot

parent.

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

red-black-tree.

Source

red-black-tree.lisp.

Target Slot

right.

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

red-black-tree.

Source

red-black-tree.lisp.

Target Slot

root.

Function: rotate/left (tree node)
Package

red-black-tree.

Source

red-black-tree.lisp.

Function: rotate/right (tree node)
Package

red-black-tree.

Source

red-black-tree.lisp.

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

red-black-tree.

Source

red-black-tree.lisp.

Target Slot

sentinel.

Reader: sort-func (instance)
Writer: (setf sort-func) (instance)
Package

red-black-tree.

Source

red-black-tree.lisp.

Target Slot

sort-func.

Function: transplant (tree u v)
Package

red-black-tree.

Source

red-black-tree.lisp.

Reader: value (instance)
Writer: (setf value) (instance)
Package

red-black-tree.

Source

red-black-tree.lisp.

Target Slot

value.


Appendix A Indexes


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

A.1 Concepts


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

A.2 Functions

Jump to:   %   (  
C   D   F   I   K   L   M   N   P   R   S   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 color): Private ordinary functions
(setf key): Private ordinary functions
(setf key-func): Private ordinary functions
(setf left): Private ordinary functions
(setf parent): Private ordinary functions
(setf right): Private ordinary functions
(setf root): Private ordinary functions
(setf sentinel): Private ordinary functions
(setf sort-func): Private ordinary functions
(setf tree): Public ordinary functions
(setf value): Private ordinary functions

C
color: Private ordinary functions

D
delete: Public ordinary functions
delete-node: Public ordinary functions
delete/fixup: Private 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 color): Private ordinary functions
Function, (setf key): Private ordinary functions
Function, (setf key-func): Private ordinary functions
Function, (setf left): Private ordinary functions
Function, (setf parent): Private ordinary functions
Function, (setf right): Private ordinary functions
Function, (setf root): Private ordinary functions
Function, (setf sentinel): Private ordinary functions
Function, (setf sort-func): Private ordinary functions
Function, (setf tree): Public ordinary functions
Function, (setf value): Private ordinary functions
Function, color: Private ordinary functions
Function, delete: Public ordinary functions
Function, delete-node: Public ordinary functions
Function, delete/fixup: Private ordinary functions
Function, find: Public ordinary functions
Function, insert: Public ordinary functions
Function, insert-fixup: Private ordinary functions
Function, key: Private ordinary functions
Function, key-func: Private ordinary functions
Function, left: Private 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-p: Private ordinary functions
Function, parent: Private ordinary functions
Function, previous: Public ordinary functions
Function, right: Private ordinary functions
Function, root: Private ordinary functions
Function, rotate/left: Private ordinary functions
Function, rotate/right: Private ordinary functions
Function, sentinel: Private ordinary functions
Function, sort-func: Private ordinary functions
Function, transplant: Private ordinary functions
Function, tree: Public ordinary functions
Function, valid-p: Public ordinary functions
Function, value: Private ordinary functions
Function, walk: Public ordinary functions

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

K
key: Private ordinary functions
key-func: Private ordinary functions

L
left: Private 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-p: Private ordinary functions

P
parent: Private ordinary functions
previous: Public ordinary functions
print-object: Public standalone methods
print-object: Public standalone methods

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

S
sentinel: Private ordinary functions
sort-func: Private ordinary functions

T
transplant: Private ordinary functions
tree: Public ordinary functions

V
valid-p: Public ordinary functions
value: Private ordinary functions

W
walk: Public ordinary functions

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