NingG +

数据结构:Trie Tree,字典树、前缀树

0.概要

关于 Trie Tree,深究一下,实现原理等内容。

1.Trie Tree:字典树、前缀树

几个方面:

1.1.是什么?

Trie树,又叫字典树、前缀树(Prefix Tree)、单词查找树 或 键树,是一种多叉树结构。

上图是一棵Trie树,表示了关键字集合{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”} 。

从上图可以归纳出Trie树的基本性质:

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

实际场景中,每个中间节点,会设置「一个标记」,用于标识当前节点是否构成一个单词关键词)。

1.2.有什么用?

字典树,作为数据结构,有什么用?本质是:查询效率,或者说「时间复杂度」。

Trie树:

优点

缺点

具体的应用场景:

1.3.如何构建 Trie 树?

参考:

2.参考资料

同类文章:

微信搜索: 公众号 ningg ,即可联系我

Top