There are a couple of places in which Tagz, where I needed efficient prefix matching. The most obvious way to do this is to use a Trie or a Ternary Search Tree. So, I ended up implementing both in Python. I’ve had this stuff lying around in my mercurial repo for Tagz for quite some time now. I just thought of releasing it today.
Here are two GraphViz graphs visualizing both the structures, generated using the excellent GvGen library.
In the Ternary Search Tree graph, Blue vertices = left, Green vertices = middle, Red vertices = right.
The code can be found here.