Trie

In computer science, a trie, also called digital tree and sometimes radix tree or prefix tree (as they can be searched by prefixes), is an ordered tree data structure that is used to store a dynamic set or associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated. All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string. Values are normally not associated with every node, only with leaves and some inner nodes that correspond to keys of interest. For the space-optimized presentation of prefix tree, see compact prefix tree.

A common application of a trie is storing a predictive text or autocomplete dictionary, such as found on a mobile telephone. Such applications take advantage of a trie's ability to quickly search for, insert, and delete entries; however, if storing dictionary words is all that is required (i.e., storage of information auxiliary to each word is not required), a minimal deterministic acyclic finite state automaton would use less space than a trie. This is because an acyclic deterministic finite automaton can compress identical branches from the trie which correspond to the same suffixes (or parts) of different words being stored.

Wikipedia

var trie = new Trie(); //an empty trie

Methods

getIterator()

This method returns an iterator for scanning the tree. The iterator is useful in order to get a full decoupling in your classes. This avoid, to the class that uses the iterator, to know what type of data structure stores the data.

var trie = new Trie();
var it = trie.getIterator();
for(it.first(); !it.isDone(); it.next()) {
  var item = it.getItem();
  //do something
}

The iterator starts from the top of the tree.

Complexity: O(1)

insert(string, item)

This method insert the string and the relative item in the trie. If the path to reach the relative string don't exists then it will be created.

var trie = new Trie();
trie.insert("Blue", 0); //trie contains {"Blue", 0}
trie.insert("Boing", 0); //trie contains {"Blue", 0}, {"Boing", 0}
trie.insert("Abba", 0); //trie contains {"Abba", 0}, {"Blue", 0}, {"Boing", 0}

Complexity: O(m) where m is the average length of the strings in the trie.

suggest(string)

This method suggest the possible endings of the string. It returns the array of strings that conclude the string. It is empty if no ending is found.

var trie = new Trie();
trie.insert("Blue"); //trie contains "Blue"
trie.insert("Boing"); //trie contains "Blue", "Boing"
trie.insert("Abba"); //trie contains "Abba", "Blue", "Boing"
trie.suggest("B"); //["Blue", "Boing"]
trie.suggest("Ab"); //["Abba"]
trie.suggest("R"); //[]
trie.suggest(""); //["Abba", "Blue", "Boing"]

Complexity: O(m) where m is the number of possible endings of the strings.