Java Crit-bit Trees

Question

Is there a built-in data structure in Java to represent a Crit-bit tree? Or any libraries available that might provide this functionality? I would also accept brief code as an answer, if one can be implemented in a simplistic brief way.

Answer 1

Did you try the radixtree java project?

You might find in it the structure you are looking for, like the:

• RadixTree class

(extract):

/**
 * This interface represent the operation of a radix tree. A radix tree,
 * Patricia trie/tree, or crit bit tree is a specialized set data structure
 * based on the trie that is used to store a set of strings. In contrast with a
 * regular trie, the edges of a Patricia trie are labelled with sequences of
 * characters rather than with single characters. These can be strings of
 * characters, bit strings such as integers or IP addresses, or generally
 * arbitrary sequences of objects in lexicographical order. Sometimes the names
 * radix tree and crit bit tree are only applied to trees storing integers and
 * Patricia trie is retained for more general inputs, but the structure works
 * the same way in all cases.
 * 
 * @author Tahseen Ur Rehman 
 * email: tahseen.ur.rehman {at.spam.me.not} gmail.com
 */
public interface RadixTree<T> {
    /**
     * Insert a new string key and its value to the tree.
     * 
     * @param key
     *            The string key of the object
     * @param value
     *            The value that need to be stored corresponding to the given
     *            key.
     * @throws DuplicateKeyException
     */
    public void insert(String key, T value) throws DuplicateKeyException;

• RadixTreeNode class

(extract):

/**
 * Represents a node of a Radix tree {@link RadixTreeImpl}
 * 
 * @author Tahseen Ur Rehman
 * @email tahseen.ur.rehman {at.spam.me.not} gmail.com
 * @param <T>
 */
class RadixTreeNode<T> {
    private String key;

    private List<RadixTreeNode<T>> childern;

    private boolean real;

    private T value;

    /**
     * intailize the fields with default values to avoid null reference checks
     * all over the places
     */
        public RadixTreeNode() {
        key = "";
        childern = new ArrayList<RadixTreeNode<T>>();
        real = false;
    }

Answer 2

Another option is rkapsi's patricia-trie, or if you're looking for something a little less complicated that you can hack on yourself, you can try his simple-patricia-trie.

I've also got a functional-critbit implementation available that's focused on space-efficiency (though its performance is fine, as well). It comes in both mutable and immutable flavors.