Tries

Introduction

In a trie, the keys are more or less encoded in paths from the root node.

For example, this tree encodes {car, card, carry, cart, cat, cel, celery, close, closely, closet, clue}:

trie.png

Implementation

When implementing a set, store a boolean value in each node: true if the node is "final", false otherwise.

public class TrieNode {
    private char character;
    private boolean last;
    private Set<TrieNode children;
    ...
}

When implementing a dictionary, store the corresponding value in final nodes, and null in non-final nodes.

public class TrieNode {
    private char character;
    private String definition;
    private Set<TrieNode children;
    ...
}

In general, we need not restrict ourselves to strings for keys and values:

public class TrieNode<C, D> {
    private C character;
    private D definition;
    private Set<TrieNode<C, D>> children;
    ...
}

Though in this case, keys would be some sort of C array, so using it with string keys might be a tad messy.

Exercise: Write a Dictionary interface and an implementation using a trie.

Uses

Tries can be used for spell checkers.

Exercise: Implement a spell checker with a trie.

Variations

You can save memory by turning the underlying tree into a graph:

trie_dag.png

Exercise: How does this representation complicate insertion into and deletion from a trie?

If the alphabet is super-restricted, then the characters of the key string can be implicit labels on the edges and the nodes can store the values (use null where a node would be non-final, of course). Here's Morse Code, left child is dot, right is dash:

morsecode.png