/***************************************************************************
* Author: Isai Damier
* Title: Trie.java
* Project: geekviewpoint
* Package: datastructure
*
* Description:
* A trie is a tree data-structure that stores words by compressing common
* prefixes. To illustrate, following is a word list and its resulting trie.
*
* WORDS: rat, rats, rattle, rate, rates, rating, can, cane,
* canny, cant, cans, cat, cats, cattle, cattles.
*
* TRIE:
* ___________|____________
* | |
* r c
* a ________a___________
* t~ | |
* ____|_____ n~ t~
* | | | | _____|_____ _______|______
* s~ t e~ i | | | | | t
* l s~ n e~ n t~ s~ s~ l
* e~ g~ y~ e~
* s~
*
* Each ~ in the figure indicates where a prefix is a word.
*
* Generally, a trie has all the benefits of a hash table without
* any of the disadvantages.
*
* --------------------------------------------------------------
* | HASH TABLE | TRIE | explanations
* --------------------------------------------------------------
* Memory | O(n) | < O(n) | trie uses prefix compression.
* | | | Hence it does not store each
* | | | word explicitly
* ----------------------------------------------------------------
* Search | O(1) | O(1) | trie is technically faster.
* | | pseudo- | Given a word, computing a
* | | constant | hash takes at least as long
* | | | as traversing a trie. Plus,
* | | | trie has no collision.
* ----------------------------------------------------------------
*
* Tries are particularly superior to hash tables when it comes to solving
* problems such as word puzzles like boggle. In such puzzles the objective
* is to find how many words in a given list are valid. So if for example
* at a particular instance in boggle you have a list of one billion words
* all starting with zh-, whereas the dictionary has no words starting with
* zh-; then: if the dictionary is a hash table, you must compute the entire
* hashcode for each word and do one billion look-ups; if on the other hand
* the dictionary is a trie, you only do the equivalent of partially
* computing one hashcode! That's a saving of over one billion fold!
*
* This implementations of trie uses an array to store the children
* nodes, where the numerical value of each char serves as index.
**************************************************************************/
/********************************************************************
* Author: Isai Damier
* Title: TrieNode
* Project: geekviewpoint
* Package: algorithms.trie
*
* Description:
* This is a very simple node class for the Trie data structure. An array
* is used to hold the references/pointers to the children/next nodes.
* The numerical value of each char serves as index. The array could be
*
* TrieNode[] next = new TrieNode[256];//256 or 26 or etc.
*
* Different implementation of the TrieNode presents different conveniences
* and restrictions. For instance, using an array as opposed to a hashmap
* for storing the pointers to the next nodes means not having access to
* a cheap isEmpty() function. Hence we must declare and track our own
* nextIsEmpty variable.
*
* Map<Character,TrieNode> next = new HashMap<>();//map alternative
*******************************************************************/
package algorithms.trie;
public class TrieNode {
public char value;
boolean word = false;
TrieNode[] next = new TrieNode[256];
private int nextLength = 0;
public TrieNode(char c) {
value = c;
}
void setChild(char c, TrieNode node){
next[c]=node;
nextLength++;
}
void clearNext() {
next = new TrieNode[256];
nextLength = 0;
}
boolean nextIsEmpty(){
return nextLength == 0;
}
int nextSize(){
return nextLength;
}
}
