Trie字典树
一、字典树
字典树——Trie树,又称为前缀树(Prefix Tree)、单词查找树或键树,是一种多叉树结构。
上图是一棵__Trie__树,表示了关键字集合{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”} 。从上图可以归纳出Trie树的基本性质:
-
根节点不包含字符,除根节点外的每一个子节点都包含一个字符。
-
从根节点到某一个节点,路径上经过的字符连接起来,为该节点对应的字符串。
-
每个节点的所有子节点包含的字符互不相同。
- 通常在实现的时候,会在结点结构中设置一个标志,用来标记该节点处是否构成一个单词(关键字)。
- 可以看出,Trie树的关键字一般都是字符串,而且Trie树把每个关键字保存在一条路径上,而不是一个节点中。另外,有两个公共前缀的关键字,在Trie树种前缀部分的路径相同。所以Trie又称为前缀树。