Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。小写英文字母或大写英文字母的字典数是一个26叉树。Trie树的根结点是不保存数据的，所有的数据都保存在它的孩子节点中。

    字符串go, golang, php, python, perl，它这棵Trie树可如下图所示构造：
    image.png

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

    基本性质

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

    code

    1. package main
    3. import "fmt"
    5. type Trie struct {
    6.     // 自身节点 与 若干个子节点
    7.     Children map[byte]*Trie
    8.     // 标识节点是否是一个单词最后的一个字符
    9.     IsWord bool
    10. }
    12. func NewTrie() *Trie {
    13.     return &Trie{}
    14. }
    16. func (t *Trie) Add(word string) {
    17.     cur := t
    18.     // 遍历 word的每一个字符
    19.     for _, c := range []byte(word) {
    20.         if cur.Children == nil {
    21.             cur.Children = make(map[byte]*Trie)
    22.         }
    23.         // 查找子节点中是否包含当前字符
    24.         // 如果不包含, 添加一下
    25.         if _, ok := cur.Children[c]; !ok {
    26.             cur.Children[c] = NewTrie()
    27.         }
    28.         // cur 指向子节点
    29.         cur = cur.Children[c]
    30.     }
    31.     // 将最后一个节点字符的 尾设置为 true
    32.     cur.IsWord = true
    33. }
    35. func (t *Trie) Search(word string) bool {
    36.     cur := t
    37.     // 遍历 word的每一个字符
    38.     for _, c := range []byte(word) {
    39.         // 查找子节点中是否包含当前字符
    40.         if _, ok := cur.Children[c]; !ok {
    41.             return false
    42.         }
    43.         // cur 指向下一个子节点
    44.         cur = cur.Children[c]
    45.     }
    46.     // 判断最后一个单词是否是 单词末尾 cur.isWord == true,
    47.     // 直接缩写为 cur.isWord
    48.     return cur.IsWord
    49. }
    51. func (t *Trie) StartsWith(prefix string) bool {
    52.     cur := t
    53.     // 遍历 word的每一个字符
    54.     for _, c := range []byte(prefix) {
    55.         // 查找子节点中是否包含当前字符
    56.         if _, ok := cur.Children[c]; !ok {
    57.             return false
    58.         }
    59.         // cur 指向下一个子节点
    60.         cur = cur.Children[c]
    61.     }
    63.     return true
    64. }
    66. func main() {
    67.     // 创建字典树
    68.     t := NewTrie()
    69.     t.Add("door")
    70.     // 测试
    71.     fmt.Println(t.Search("dog"))
    72.     fmt.Println(t.Search("door"))
    73.     fmt.Println(t.StartsWith("do"))
    74. }