A surprising amount of path recognizers are O(n). Paths/routes are a great fit for radix trees, since there's typically repetitions, like /projects, /projects/1, and /projects/1/todos. The performance is O(log n).
This is one of the reasons for why I call it a "bastardized radix tree" in the README :)
The routes are stored as "nodes". There's a root node. It has a hash map of child nodes, by name. It also has a list of "parameterized" nodes. When a node gets a path segment, it will first look in its hash map. If nothing is there, it'll call the parameterized nodes in sequence. Typically there's just one parameterized node.
The root node will have a single item in its hash map, "projects". No items in the parameterized node.
The node for "projects" will have to items in its hash map, "new" and "special". It will have a single item in it's parameterized node, for :project-id.
I updated the README just now with a slightly more detailed explanation :)
I built one for Java: https://github.com/augustl/path-travel-agent