File: radix-tree.el.html
There are many different options for how to represent radix trees
in Elisp. Here I chose a very simple one. A radix-tree can be either:
- a node, of the form ((PREFIX . PTREE) . RTREE) where PREFIX is a string
meaning that everything that starts with PREFIX is in PTREE,
and everything else in RTREE. It also has the property that
everything that starts with the first letter of PREFIX but not with
that whole PREFIX is not in RTREE (i.e. is not in the tree at all).
- anything else is taken as the value to associate with the empty string.
So every node is basically an (improper) alist where each mapping applies
to a different leading letter.
The main downside of this representation is that the lookup operation is slower because each level of the tree is an alist rather than some kind of array, so every level's lookup is O(N) rather than O(1). We could easily solve this by using char-tables instead of alists, but that would make every level take up a lot more memory, and it would make the resulting data structure harder to read (by a human) when printed out.
Defined variables (1)
radix-tree-empty | The empty radix-tree. |
Defined functions (14)
radix-tree--insert | (TREE KEY VAL I) |
radix-tree--lookup | (TREE STRING I) |
radix-tree--prefixes | (TREE STRING I PREFIXES) |
radix-tree--remove | (TREE KEY I) |
radix-tree--subtree | (TREE STRING I) |
radix-tree-count | (TREE) |
radix-tree-from-map | (MAP) |
radix-tree-insert | (TREE KEY VAL) |
radix-tree-iter-mappings | (TREE FUN &optional PREFIX) |
radix-tree-iter-subtrees | (TREE FUN) |
radix-tree-leaf--pcase-macroexpander | (VPAT) |
radix-tree-lookup | (TREE KEY) |
radix-tree-prefixes | (TREE STRING) |
radix-tree-subtree | (TREE STRING) |