Jesper Louis Andersen
jlouis at mongers.org
Fri Aug 19 04:49:16 EDT 2005
Adrian Hey wrote:
> I'm not entirly clear about the difference between "tries", "compact tries"
> (depends what you call compact AFAICS) and "PATRICIA tries", and is a PATRICIA
> trie the same thing as a "PATRICIA tree"?
A trie and a PATRICIA tree is not the same thing. A PATRICIA tree is
also known as a Radix tree, which discloses the way it works a lot more
since it basicly stores bitstrings but skips over places where the
strings are common. Knuth, ''The art of computer programming'' Volume 3
has a little 1.5 page treatise on PATRICIA trees and does also refer to
I guess the trie/tree confusion can be neglected and taken as being
A good way of looking at tries is due to Chris Okasaki, I think. He
views them as a (SML-) functor from finite maps to finite maps turning a
FiniteMap Char a into FiniteMap [Char] a. ''Purely functional data
structures'' is the book.
More information about the Libraries