Vladimir Sedach

Have Emacs - Will Hack

August 8, 2007

Radix trees for Common Lisp

Topic: Lisp

At the beginning of the year I wanted to do some toy coding to break out of a Lisp dry spell (the unfortunate result of too much schoolwork). Having recently found out about Radix trees (also known as Patricia trees), I decided to write an implementation for Common Lisp.

The code is available under the BSD license: radix-tree.lisp. This implementation works for any subtype of sequence. I have not implemented a version for integers, so you will have to use bit-vectors if you want to index things by binary keys.