原理：（from wiki）
In computer science, a trie, or prefix tree, is an ordered tree data structure that is used to store an 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.
Values are normally not associated with every node, only with leaves and some inner nodes that correspond to keys of interest. (consider a dictionary)
Looking up keys is faster. Looking up a key of length m takes worst case O(m) time. BST takes O(m log n) time.
- Tries facilitate longest-prefix matching.
Tries facilitate longest-prefix matching, but hashing does not, as a consequence of the above.
1. A common application of a trie is storing a dictionary, such as one found on a mobile telephone.
2. Tries are also well suited for implementing approximate matching algorithms.
3. Lexicographic sorting of a set of keys can be accomplished with a simple trie-based algorithm as follows. (e.g. radix sort using trie)
4. A trie forms the fundamental data structure of Burstsort, currently (2007) the fastest known, memory/cache-based, string sorting algorithm.[6]
实现实例：
#!/usr/bin/python
print '================ A Trie Demo =============='
class Node:
def __init__(self):
self.value = None
self.children = {} # children is of type {char, Node}
class Trie:
def __init__(self):
self.root = Node()
def insert(self, key): # key is of type string
# key should be a low-case string, this must be checked here!
node = self.root
for char in key:
if char not in node.children:
child = Node()
node.children[char] = child
node = child
else:
node = node.children[char]
node.value = key
def search(self, key):
node = self.root
for char in key:
if char not in node.children:
return None
else:
node = node.children[char]
return node.value
def display_node(self, node):
if (node.value != None):
print node.value
for char in 'abcdefghijklmnopqrstuvwxyz':
if char in node.children:
self.display_node(node.children[char])
return
def display(self):
self.display_node(self.root)
trie = Trie()
trie.insert('hello')
trie.insert('nice')
trie.insert('to')
trie.insert('meet')
trie.insert('you')
trie.display()
print
print trie.search('hello')
print trie.search('HELLO')
print
print '================= END ====================='
示例结果：
root@localhost :/home/James/mypro/Python# ./trie.py
================ A Trie Demo ==============
hello
meet
nice
to
you
hello
None
================= END =====================
root@localhost :/home/James/mypro/Python#
