L1: the generic type T represents the type of value in L6.
L2: is used to store the children.
L4: true if this node represents the last character of a certain word; otherwise, false.
L9: gives the complexity for searching a key.
What other types of maps are implemented in Java?
Let us define getter methods:
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:
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:
L1: returns true if this node represents the last character of a certain word; false.
Trie
Let us create the class, :
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:
L5: iterates through every character in the string.
L6: finds the node whose key is the current character.
L7
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:
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:
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.
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:
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.
The following demonstrates how the remove() method works:
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);
}
}
: the child does not exist, implying that
key
is not introduced in this trie.
L8: returns the value of the previously key if exists; otherwise, null.
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.
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;
}
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);
}
public boolean isEndState() { return end_state; }
public boolean hasValue() { return value != null; }
public boolean hasChildren() { return !children.isEmpty(); }
public class Trie<T> {
private final TrieNode<T> root;
public Trie() {
root = new TrieNode<>(null, (char)0);
}
public TrieNode<T> getRoot() { return root; }
}
/** @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;
}
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;
}
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);
}