Trie Tree(字典树/前缀树/单词查找树)

2020-01-16 本文已影响0人 myFamily329

自动补全、拼写检查、最长前缀匹配、单词游戏

Trie树是一个有根的树，其结点具有以下字段【每个节点都至少包含两个属性】：

children：数组或集合，罗列出每个分支当中包含的所有字符。最多有R个指向子结点的连接，其中每个链接对应字母表数据集中的一个字母。本文中假定 R，R 为 26，小写拉丁字母的数量。
isEnd: 布尔字段，用于指定结点对应键的结尾还是键前缀
根节点为空的，除了根节点，其他所有节点都有可能为单词的结尾，叶子节点一定为单词结尾。

哈希表可以在O(1)时间内寻找键值，但是无法高效完成：

Trie树优于哈希表的另一个理由：随着哈希表大小的增加，会出现大量冲突，可能最会的时间复杂度为O(n), 其中n为插入表中键值的个数。同时，Trie树在存储多个相同前缀的键时可以使用较少空间。此时Trie树只需O(m), 其中m为键长。

从根节点开始搜索它对应的第一个键字符的链接，存在两种情况：

重复上述步骤，直到达到最后一个键字符，然后将当前结点标记为结束字符，算法完成。

每个键在Trie中表示为从根内部节点到叶子结点的路径。用第一个键字符从根开始，检查当前结点与键字符对应的链接，存在两种情况：

存在链接。我们移动到该链接后面路径中的下一个节点，并继续搜索下一个键字符。
不存在链接。若已无剩余键字符，且当前结点标记为 isEnd，则返回 true。否则有两种可能，均返回 false :
1). 还有键字符剩余，但无法跟随 Trie 树的键路径，找不到键。
2). 没有键字符剩余，但当前结点没有标记为 isEnd。也就是说，待查找键只是Trie树中另一个键的前缀。

时间复杂度 : O(m)。算法的每一步均搜索下一个键字符。最坏的情况下需要 m 次操作。
空间复杂度 : O(1)