The n-ary-tree package implements an automatically rebalancing B-tree which supports n >= 5 items in any mixture of types per node. By storing multiple items per node, per-item memory overhead is decreased and searches are potentially made more efficient. This is done by increasing the distance traversed over the search space with each step since the number of nodes discarded is multiplied by the number of items per node. Duplicate items are allowed and items are always maintained in sort order. The user must supply a sort function, a key calculation function and optionally, an equality test function. By allowing the user to define the characteristics of the key values, the N-ARY tree allows the user to implement ordering in a convienent & hopefully efficient manner.
The automatic rebalance algorithm can be enabled/disabled or reconfigured at any time after the tree is created.
Besides the expected create and insert/delete/find operations, the package implements a mapping function as well as get first/last and next/previous operations for ordered, per item traversal of the tree. This means it is possible to search for an item and in sort order, navigate from it to other items in the tree.
If the optional equality test function is omitted, searches cannot be definite and will either produce the item with keyval just prior to the test key or the item referred to by the test key. Therefore it is possible to find either where an item is or where it should be in the tree. The equality test function can be supplied or removed from the tree at any time.
Like most any B-tree, the N-ARY tree implementation is subject to various well known issues given pathological insert/delete sequences. The rebalance algorithm is admittedly simplistic, however given an opportunity to work, it should provide some compensation for poor update key distributions.
Documentation;
See the source code... ;) The following are links to the current source.
nary-tree.lisp
nary-tree-test.lisp
Status;
Nominally working. It passes the test suites in the demo code distributed with the package. I have not thoroughly examined the effects of the rebalancing algorithm, however it seems to be working with trivial examples.
Portability;
The N-ARY tree package is intended to be portable to any reasonably compliant Common Lisp implementation. I wrote it on Xanalys LispWorks, and have tested it there and on Clisp.
Future Work;
- Optimization and tweaks for compilers.
- More sophisticated rebalancing algorithms.
- Rebalance thrashing detection & mitigation.
- Additional utility functions to make adjusting the rebalance
parameters
easier than manipulating slots in the root datastructure.
- Dynamically size the node arrays/automatically adjust rebalance
parameters.
- Add instrumentation to help monitor tree balance.
- Improve the documentation...
Distribution;
The following releases are available via http download;
initial release, 2/2003
narytree-0.1.tar.gz
3/2/2003 - improved docs, search vector enhancements
narytree-0.2.tar.gz
7/5/2003 - improved docs
narytree-0.3.tar.gz
11/30/2003 - fixes to support cmucl & a couple other problems,
new tree pop function, new insert before/after without known key
narytree-0.4.tar.gz
Installation;
No particular procedures are required, extract the files into a convienent directory and load/compile them as you choose. The only file required for operation is nary-tree.lisp.
Contact;
Please contact me at gmlathe@comcast.net, I'll be happy to answer whatever questions I can, and welcome bugreports, suggestions and patches.
Legalese;
The Common Lisp N-ARY Tree package is (C)opyright 2003, Greg Menke
Released under Version 2 of the GNU GPL. Please see http://www.gnu.org/licenses/gpl.html or www.gnu.org for more information.
;;; eof