README.md

Trie Data Structure

It is a symbol table specialized to string keys.

The goal is to device a data structure that is Faster than hashing and More flexible than BSTs.

Challenge - Efficient Performance for String keys

R-Way Trie

• Store characters in nodes (not keys)
• Each node has R children for each possible character.
• Store values in nodes corresponding to last characters in keys.

Trie Performance

• Search Hit

  Need to examine all L characters for equality

• Search Miss

  • could have mis-match on first character
  • Typical case: examine only a few characters (sublinear)

• Space

  • Space is a downside. R null links at each leaf.
  • (but sublinear space possible if many short strings share common prefixes)

  •   public class TrieNode {
          private static final int R = 256;   // extended ascii
    
          Object value;
          TrieNode[] next = new TrieNode[R];
      }
    

• *Bottom Line: Fast search hit and even faster search miss, but wastes space.

Popular Interview Question

• Design a data structure to perform efficient spell checking

Sol. Build a 26-way trie (key = word, value = bit)

Deletion in R-Way Trie

To delete a key-value pair:

• Find a node corresponding to the key and set the value to null
• If that node has all null links, remove that node (and recur).

TrieST.java

/*
    - Neither keys nor characters are explicitly stored
    - Characters are implicitly defined by link index
    - Each node has an array of links and a value

 */

import java.util.Objects;

public class TrieST<Value> {
    private static final int R = 256;   // extended ASCII
    
    private static class TrieNode {
        Object value;
        TrieNode[] next = new TrieNode[R];
    }

    private TrieNode root = new TrieNode();

    public void put(String key, Value value) {
        root = put(root, key, value, 0);
    }

    private TrieNode put(TrieNode x, String key, Value value, int d) {
        if (x == null) x = new TrieNode();

        if (d == key.length()) {
            x.value = value;
            return x;
        }

        char c = key.charAt(d);
        x.next[c] = put(x.next[c], key, value, d + 1);
        return x;
    }

    public boolean contains(String key) {
        return get(key) != null;
    }

    public Value get(String key) {
        TrieNode x = get(root, key, 0);
        if (Objects.isNull(x)) return null;
        return (Value) x.value;
    }

    private TrieNode get(TrieNode x, String key, int d) {
        if (x == null) return null;
        if (d == key.length()) return x;
        char c = key.charAt(d);

        return get(x.next[c], key, d + 1);
    }

    public void delete(String key) {
        delete(root, key, 0);
    }

    private void delete(TrieNode x, String key, int d) {
        if (x == null) return;
        if (d == key.length()) {
            x.value = null;
            deleteLink(x);
            return;
        }
        char c = key.charAt(d);
        delete(x.next[c], key, d+1);
    }

    private void deleteLink(TrieNode x) {
        int nullCount = 0;
        for (TrieNode i : x.next)
            if (i == null) nullCount++;

        if (nullCount == x.next.length)
            x.next = null;
    }
}