Research Findings:
1. 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.
2. 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
3. A trie can be seen as a tree-shaped deterministic finite automaton. Each finite language is generated by a trie automaton, and each trie can be compressed into a deterministic acyclic finite state automaton.
4. while a balanced binary tree has log2(n) depth, the maximum depth of the trie is equal to the maximum length of a word! (Again, wider but shorter.)
Problems:
Word add and search Probem.
Advantages:
1. It can replace HashTable
2. Burstsort
About Data Structure:
1. Trie, a special tree structure, quite different from binary tree.
2. The tree's root is null. Each TrieNode has hashmap, character, and isEnd property.
3. Each node can have many children.
Problems:
211. Add and Search Word - Data structure design
Names:
Trie
Digital Tree
Radix Tree
Prefix Tree
Type:
Bitwise Trie
Terms:
Dynamic Set
Associative Array
Feelings:
1. node is null. When traversing the tree, use the children/map to test if their child is target node.
2. Also need to use isEnd property to test if this is the end of the word.
3. We can also use Backtracking technique to do pattern search.
References:
https://en.wikipedia.org/wiki/Trie
http://www.geeksforgeeks.org/longest-prefix-matching-a-trie-based-solution-in-java/
