数据结构-字典树

简介

什么是字典树

字典树，Tire树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。他的优点是：以空间换时间，利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

核心思想

空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

三个基本特性

1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
3. 每个节点的所有子节点包含的字符都不相同。

使用范围

1. 词频统计。
2. 前缀匹配。