6、字典树(trie树)

　　(图f)

　　字典树是一种以树形结构保存大量字符串。以便于字符串的统计和查找，经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来节约存储空间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。具有以下特点(图f)：

　　(1)根节点为空;

　　(2)除根节点外，每个节点包含一个字符;

　　(3)从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。

　　(4)每个字符串在建立字典树的过程中都要加上一个区分的结束符，避免某个短字符串正好是某个长字符串的前缀而淹没。

　　7、后缀树

　　后缀树则是一个字符串的所有后缀组成的字典树。具体内容再前几章已讲过。

添加您的专属公考咨询师

扫码免费领取专属学习礼包

领取资料 咨询优惠