5.2. Implementation

This section describes how to implement a trie.

Trie Node

Let us define a class, TrieNode:

public class TrieNode<T> {
    private final Map<Character, TrieNode<T>> children;
    private TrieNode<T> parent;
    private boolean end_state;
    private char key;
    private T value;

    public TrieNode(TrieNode<T> parent, char key) {
        children = new HashMap<>();
        setEndState(false);
        setParent(parent);
        setKey(key);
        setValue(null);
    }
}

• L1: the generic type T represents the type of value in L6.

• L2: Map is used to store the children.

• L4: true if this node represents the last character of a certain word; otherwise, false.

• L9: HashMap gives the $O(1)$ complexity for searching a key.

What other types of maps are implemented in Java?

Let us define getter methods:

public TrieNode<T> getParent() { return parent; }

public char getKey() { return key; }

public T getValue() { return value; }

public TrieNode<T> getChild(char key) { return children.get(key); }

/** @return the map whose keys and values are children's characters and nodes. */
public Map<Character, TrieNode<T>> getChildrenMap() {
    return children;
}

• L10: returns the map consisting of children's characters as keys and their nodes as values.

Is there any risk of returning this.children in L11?

Let us then define setter methods:

public void setParent(TrieNode<T> node) { parent = node; }

public void setKey(char key) { this.key = key; }

public void setEndState(boolean endState) { end_state = endState; }

public T setValue(T value) {
    T tmp = this.value;
    this.value = value;
    return tmp;
}

public TrieNode<T> addChild(char key) {
    TrieNode<T> child = getChild(key);

    if (child == null) {
        child = new TrieNode<>(this, key);
        children.put(key, child);
    }

    return child;
}

public TrieNode<T> removeChild(char key) {
    return children.remove(key);
}

• L7: returns the previously assigned value of this node.

• L13: returns the child with the specific key if exists; otherwise, a new child with the key.

What does the removeChild() method return if key does not exist in this node?

Finally, let us define checker methods:

public boolean isEndState() { return end_state; }

public boolean hasValue() { return value != null; }

public boolean hasChildren() { return !children.isEmpty(); }

• L1: returns true if this node represents the last character of a certain word; false.

Trie

Let us create the class, Trie:

public class Trie<T> {
    private final TrieNode<T> root;

    public Trie() {
        root = new TrieNode<>(null, (char)0);
    }

    public TrieNode<T> getRoot() { return root; }
}

• L1: defines a generic type T that can be any type.

• L5: initializes the root with the null character.

Let us define the find() method that takes a specific key in string and returns the node corresponding the last character of the key:

/** @return the node with the specific key if exists; otherwise, {@code null}. */
public TrieNode<T> find(String key) {
    TrieNode<T> node = root;

    for (char c : key.toCharArray()) {
        node = node.getChild(c);
        if (node == null) return null;
    }

    return node;
}

• L5: iterates through every character in the string.

• L6: finds the node whose key is the current character.

• L7: the child does not exist, implying that key is not introduced in this trie.

Given the find() method, let us define the get() method that takes a string key and returns the value of the node corresponding to the key in this trie:

public T get(String key) {
    TrieNode<T> node = find(key);
    return (node != null && node.isEndState()) ? node.getValue() : null;
}

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

• L3: checks if both the key exists and the key is a word.

We then define the put() method that inserts a key-value pair to the trie:

public T put(String key, T value) {
    TrieNode<T> node = root;

    for (char c : key.toCharArray())
        node = node.addChild(c);

    node.setEndState(true);
    return node.setValue(value);
}

• L4-5: iterates through all characters in the key and adds children as necessary.

• L7: sets the end state of the node corresponding the last character to true.

• L8: returns the value of the previously key if exists; otherwise, null.

What does node.addChild(c) return if the child with the key c already exists?

The following demonstrates how the put() method works:

Finally, let us define the remove() method that removes all appropriate nodes corresponding to the key:

public boolean remove(String key) {
    TrieNode<T> node = find(key);

    if (node == null || !node.isEndState())
        return false;

    if (node.hasChildren()) {
        node.setEndState(false);
        return true;
    }

    TrieNode<T> parent = node.getParent();

    while (parent != null) {
        parent.removeChild(node.getKey());

        if (parent.hasChildren() || parent.isEndState())
            break;
        else {
            node = parent;
            parent = parent.getParent();
        }
    }

    return true;
}

• L2: retrieves the node corresponding to the last character in the key.

• L4: returns false the key does not exist or the key is not a word.

• L7-10: if the retrieved node has children, sets its end-state to false and returns true.

• L12-23: removes ancestors who have descendants only related to this key.

The following demonstrates how the remove() method works: