Trie

Trie, or prefix tree, is a search tree that stores associative arrays or dynamically resizable collections per node. From every regular node one can search a value by key (key defines position of node with corresponding value in collection). Nodes on every path starting from level 0 (direct children of root) share the common prefix. Path from level 0 to terminal node represents a complete word (for example, ‘MAP’).

One can search a word in trie in O(M) time, where M is length of word to be searched. In case of word miss, search will terminate on some node along the path and return faster than in O(M) (depends on concrete structure of trie). Insertions and deletions will perform at worst in O(M).
trie2
Java

Time complexity: O(M) for search, insert and delete, M – length of word

Space complexity: O(N*26) -> O(N), per every node we store constant number of references to child nodes, bounded by size of alphabet


class TrieNode {

        public static final int R = 26;//size of alphabet

        private TrieNode[] next = new TrieNode[R];

        private boolean isTerminal;

        // Initialize your data structure here.
        public TrieNode() {

        }
        public void setTerminal(){
            this.isTerminal = true;
        }

        public boolean isTerminal(){
            return isTerminal;
        }

        public TrieNode setNext(int c){
            int k = c - 'a';
            if (next[k] != null){
                return next[k];
            } else {
                TrieNode newNode = new TrieNode();
                next[k] = newNode;
                return newNode;
            }
        }

        public TrieNode getNext(char c){            
            return next[c - 'a'];
        }
}

public class Trie {
        private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // Inserts a word into the trie.
    public void insert(String word) {
        TrieNode curr = root;
        for (Character c : word.toCharArray()){
            curr = curr.setNext(c);
        }
        curr.setTerminal();
    }

    // Returns if the word is in the trie.
    public boolean search(String word) {
        TrieNode curr = root;
        for (Character c : word.toCharArray()){
            curr = curr.getNext(c);
            if (curr == null){
                return false;
            }
        }
        return curr.isTerminal();
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
        TrieNode curr = root;
        for (Character c : prefix.toCharArray()){
            curr = curr.getNext(c);
            if (curr == null){
                return false;
            }
        }
        return true;
    }
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s