TRIE is an interesting data-structure used mainly for manipulating with Words in a language. This word is got from the word retrieve.
TRIE (pronounced as ‘try‘) has a wide variety of applications in
A TRIE tree would typically look like the following
In this section we shall see how the insert() method on the TRIE data structure works. We shall take a specific case and analyze it with pictorial representation.
Before we begin, assume we already have an existing TRIE as shown below.
Consider the following TRIE as usual.
Now that we‘ve seen the basic operations on how to work with a TRIE,
we shall now see the space and time complexities in order to get a real feel of how good a TRIE data structure is. Lets take the two important operations INSERT and SEARCH to measure the complexity.
INSERT operation first. Lets always take into account the worst case timing first and later convince ourselves of the practical timings. For every Node in the TRIE
we had something called as Collection where the Collection can be either a Set or a List. If we choose Set, the order of whatever operation we perform over that will be in O(1) time, whereas if we use a LinkedList the number of comparisons at worst
will be 26 (the number of alphabets). So for moving from one node to another, there will be at least 26 comparisons will be required at each step.
Having these in mind, for inserting a word of length ‘k‘ we need (k * 26) comparisons. By Applying the Big O notation it becomes O(k) which will be again O(1). Thus
insert operations are performed in constant time irrespective of the length of the input string (this might look lik an understatement, but if we make the length of the input string a worst case maximum, this sentence holds true).
Same holds true for the search operation as well. The search operation exactly performs the way the insert does and its order is O(k*26) = O(1)
public class Trie {
private TrieNode root; // Root node in trie
/**
* Constructor for Trie class
*/
public Trie(){
root = new TrieNode((char) 0);
}
/**
* A method to insert a word into the trie
* @param word The word to be inserted
*/
public void insert(String word){
TrieNode cur = root;
for(int i=0; i<word.length(); i++){
Map<Character, TrieNode> children = cur.getChildren();
char c = word.charAt(i);
if(children.containsKey(c)){ // If the character is in trie, continue searching
cur = children.get(c);
}else{ // Otherwise, create a new trie node
TrieNode newNode = new TrieNode(c);
children.put(c, newNode);
cur = newNode;
}
}
cur.setEnd(true); // Markup for the end of word
}
/**
* A method used to determine if a word is stored in trie or not
* @param word The word to be checked
* @return True if the word is stored in trie, false otherwise
*/
public boolean contains(String word){
TrieNode cur = root;
for(int i=0; i<word.length(); i++){
char c = word.charAt(i);
if(!cur.children.containsKey(c)){ // Some letter is not in trie, return false
return false;
}
cur = cur.children.get(c);
}
return cur.isEnd; // When reaches the end of word, return value is based on if the markup is set or not
}
/**
* Inner class for Trie Node
* @author Bin Feng
*
*/
class TrieNode{
private char letter; // Letter associate with the node
private Map<Character, TrieNode> children; // Children of current node
private boolean isEnd; // Markup for end of word
/**
* Constructor for TrieNode class
* @param letter The letter associate with node
*/
public TrieNode(char letter) {
this.letter = letter;
children = new HashMap<Character, Trie.TrieNode>();
isEnd = false;
}
/**
* Getters and Setters
*/
public char getLetter() {
return letter;
}
public void setLetter(char letter) {
this.letter = letter;
}
public Map<Character, TrieNode> getChildren() {
return children;
}
public void setChildren(Map<Character, TrieNode> children) {
this.children = children;
}
public boolean isEnd() {
return isEnd;
}
public void setEnd(boolean isEnd) {
this.isEnd = isEnd;
}
}
}
http://www.technicalypto.com/2010/04/trie-in-java.html
原文：http://blog.csdn.net/fightforyourdream/article/details/18332799