Trie树，也叫字典树、前缀树。可用于”predictive text”和”autocompletion”。亦可用于统计词频（边插入Trie树边更新或加入词频）。

在计算机科学中。trie，又称前缀树或字典树。是一种有序树，用于保存关联数组，当中的键一般是字符串。与二叉查找树不同。键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的全部子孙都有同样的前缀，也就是这个节点相应的字符串，而根节点相应空字符串。

普通情况下，不是全部的节点都有相应的值，仅仅有叶子节点和部分内部节点所相应的键才有相关的值。

參考资料：http://zh.wikipedia.org/wiki/Trie

#!/usr/bin/python
# -*- coding:utf-8 -*-
# * trie, prefix tree, can be used as a dict
# * author: yangxudongsuda@gmail.com
import sys
reload(sys)
sys.setdefaultencoding("utf-8")

# Singleton sentinel - works with pickling
class NULL(object):
  pass

class Node:
  def __init__(self, value = http://www.mamicode.com/NULL):>
执行结果：
None
empty list
sm
happy 站台
happy 站台
sm
None
sm 广场 -->  4
4
None
1
2
default
soho 尚都
3
90
no prefix
(‘soho \xe5\xb0\x9a\xe9\x83\xbd‘, 3)
============== keys =================
prefix "sm":  sm | sm 新生活 广场 | sm 城市广场 | sm 广场 | sm 购物 广场 | sm 国际 | sm 国际 广场
============== items =================
prefix "sm":  [(‘sm‘, None), (‘sm \xe6\x96\xb0\xe7\x94\x9f\xe6\xb4\xbb \xe5\xb9\xbf\xe5\x9c\xba‘, 5), (‘sm \xe5\x9f\x8e\xe5\xb8\x82\xe5\xb9\xbf\xe5\x9c\xba‘, 3), (‘sm \xe5\xb9\xbf\xe5\x9c\xba‘, 4), (‘sm \xe8\xb4\xad\xe7\x89\xa9 \xe5\xb9\xbf\xe5\x9c\xba‘, 6), (‘sm \xe5\x9b\xbd\xe9\x99\x85‘, 22), (‘sm \xe5\x9b\xbd\xe9\x99\x85 \xe5\xb9\xbf\xe5\x9c\xba‘, 2)]
================= delete =====================
True
None
True
None
False
False
====== no item matches any prefix of given key ========
Traceback (most recent call last):
  File "./word_based_trie.py", line 225, in <module>
    print trie.longest_prefix_value(‘happy‘)
  File "./word_based_trie.py", line 128, in longest_prefix_value
    raise Exception("no item matches any prefix of the given key!")
Exception: no item matches any prefix of the given key!