Lecture 37 - 04/21

Tries

Rough Summary of Class So Far

The Trie Structure

Trie Implementation: Array-Trie

public class TrieSet {
// Support characters upto 256
private static final int R = 256;
private class Node {
// Upto R links
boolean exists;
Node[] links;
public Node() {
links = new Node[R];
exists = false;
}
}
private Node root = new Node();
public void put(String key) {
put(root, key, 0);
}
private Node put(Node x, String key, int d) {
if (x == null) {
x = new Node();
}
if (d == key.length()) {
x.exists = true;
return x;
}
char c = key.charAt(d);
x.links[c] = put(x.links[c], key, d + 1);
return x;
}
}

Application: T9 Texting

Trie Optimization