#
Trie Node

/*************************************************************************** * 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; } }