Skip to content
This repository

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP

Implementation of red-black trees in Common Lisp, including a persistent red-black tree that uses an append-only strategy for recording changes in a text file

branch: master

Fetching latest commit…

Octocat-spinner-32-eaf2f5

Cannot retrieve the latest commit at this time

Octocat-spinner-32 LICENSE
Octocat-spinner-32 README
Octocat-spinner-32 array.lisp
Octocat-spinner-32 base.lisp
Octocat-spinner-32 hh-redblack.asd
Octocat-spinner-32 memory.lisp
Octocat-spinner-32 package.lisp
Octocat-spinner-32 persistent.lisp
Octocat-spinner-32 tests.lisp
Octocat-spinner-32 text.lisp
README
hh-redblack

This package is a Common Lisp implemention of red-black trees (http://en.wikipedia.org/wiki/Red-black_tree)
using the algorithms described in Introduction to Algorithms, by Thomas H. Cormen, Charles E. Leiserson, 
Ronald L. Rivest, and Clifford Stein.

In addition to a straight-forward in-memory implementation of red-black trees, an implementation of a persistent
tree is also included.  The persistent implementation uses a text file for storage (for human readability), and
uses an append-only strategy for updating that text file.  A footer always appears at the end of the file (actually, 
a footer and a backup copy of the footer), containing information about where the root of the tree is located
and other relevant housekeeping details.  A small header appears at the beginning of the file containing
a version number for the tree's storage format.  Under correct behavior, at no time is any byte of the file
written more than once.

Contact phil@haphazardhouse.net for any questions, comments, feedback, or contributions, and keep an eye on
http://haphazardhouse.net/projects/hh-redblack for info and news about hh-redblack.

Thanks!
Something went wrong with that request. Please try again.