Trie (Part 1)

Trie is one of my favourite data structures because its easy understand application of Trie and easy to implement as well. In case you don't know Trie comes from the word Retrieval because Trie can retrieve several words given prefix of the word. One most common usage of Trie that comes in mind quickly is auto completion of word while typing in smartphone soft keyboard. Other possible applications of Trie are spell checking keeping full dictionary in a Trie, IP lookup in router etc.

Trie Basic Operations:
Operation Complexity
insertKey() O(length of key)
searchKey() O(length of key)
removeKey() O(length of key * alphabet size)
Implementation:

Trie can insert key of any length but with a fixed amount of symbols. Number of symbols are usually denoted by alphabet size. As you can notice above figure a node could have maximum alphabet size number of child nodes. Thus alphabet size should be constant in implementation. Node of a basic Trie has 3 properties.

  1. Reference to parent
  2. Reference to all children
  3. Boolean flag that indicates a complete key/word
class TrieNode {
    TrieNode parent;
    TrieNode childs[];
    boolean isLeaf;

    public TrieNode() {
        childs = new TrieNode[MTrie.ALPHABET_SIZE];
    }

    public TrieNode(boolean isLeaf) {
        childs = new TrieNode[MTrie.ALPHABET_SIZE];
        this.isLeaf = isLeaf;
    }
}

Insert Operation:

While inserting new key into Trie basically new nodes will be created. Notice root node don't contain any symbol/letter of alphabet. Inserting key/word there will create 5 nodes. Thus length of key is the complexity of this operation.

// Complexity: O(length of key)
public boolean insertKey(String key) {
    int keyLength = key.length();
    TrieNode node = root;

    for(int i=0; i < keyLength; i++) {
        int value = charValue(key.charAt(i));
        if(null == node.childs[value]) node.childs[value] = new TrieNode();
        node.childs[value].parent = node;
        node = node.childs[value];
    }

    node.isLeaf = true;
    return true;
}

Search Operation:

Searching a key is as easy as inserting key and that's why same complexity.

// Complexity: O(length of key)
public boolean searchKey(String key) {
    int keyLength = key.length();
    TrieNode node = root;

    for(int i=0; i < keyLength; i++) {
        int value = charValue(key.charAt(i));
        if(null == node.childs[value]) return false;
        node = node.childs[value];
    }

    return node.isLeaf;
}

Remove Operation:

  1. First step of removing a key from Trie is to traverse into the key node in which isLeaf = true.
  2. Second step is checking children existance of the key node. If any child exists you can't remove the node rather mark it as isLeaf = false.
  3. In case there is no child exists go to up using parent reference until the current node has any child.

In case the figure illustrated above, first traverse to the node e (at bottom), then go up until current node is h.

// Complexity: O(length of key * alphabet size)
public boolean removeKey(String key) {
    int keyLength = key.length();
    TrieNode node = root;

    for(int i=0; i < keyLength; i++) {
        int value = charValue(key.charAt(i));
        if(null == node.childs[value]) return false;
        node = node.childs[value];
    }

    // If the given key isn't a key
    if(!node.isLeaf) return false;

    // if key node has any other child mark isLeaf == false and return
    if(childCount(node) > 0) {
        node.isLeaf = false;
        return true;
    }

    // Going bottom to top checking is current node has any child.
    // If no child exist current node should be null
    for(int i = keyLength-1; i >= 0; i--) {
        if(childCount(node) > 0) break;
        TrieNode parent = node.parent;
        parent.childs[charValue(key.charAt(i))] = null;
        node = parent;
    }
    return true;
}

Full Code: Trie_Demo.java

Blog Comments powered by Disqus.

Next Post Previous Post