西西软件下载最安全的下载网站、值得信赖的软件下载站!

首页编程开发其它知识 → 字典树Trie和三叉搜索树Ternary Tree的学习总结

字典树Trie和三叉搜索树Ternary Tree的学习总结

相关软件相关文章发表评论 来源:西西整理时间:2012/12/31 2:39:04字体大小:A-A+

作者:西西点击:0次评论:0次标签:

  • 类型:源码相关大小:510KB语言:中文 评分:6.0
  • 标签:
立即下载

Trie树,又称字典树,单词查找树或者前缀树,是一种用于快速检索的多叉树结构,如英文字母的字典树是一个26叉树,数字的字典树是一个10叉树。

三叉搜索树是一种特殊的Trie树的数据结构,它是数字搜索树和二叉搜索树的混合体。它既有数字搜索树效率优点,又有二叉搜索树空间优点。

在接下来的博文中,我们将介绍Trie树和三叉搜索树的定义,实现和优缺点。

Trie树的定义

Trie树与二叉搜索树不同,键不是直接保存在节点中,而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀(prefix),也就是这个节点对应的字符串,而根节点对应空字符串。一般情况下,不是所有的节点都有对应的值,只有叶子节点和部分内部节点所对应的键才有相关的值。

Trie树可以利用字符串的公共前缀来节约存储空间,如下图所示,该Trie树用11个节点保存了8个字符串tea,ted,ten,to,A,i,in,inn。

图1Trie树

我们注意到Trie树中,字符串tea,ted和ten的相同的前缀(prefix)为“te”,如果我们要存储的字符串大部分都具有相同的前缀(prefix),那么该Trie树结构可以节省大量内存空间,因为Trie树中每个单词都是通过character by character方法进行存储,所以具有相同前缀单词是共享前缀节点的。

当然,如果Trie树中存在大量字符串,并且这些字符串基本上没有公共前缀,那么相应的Trie树将非常消耗内存空间,Trie的缺点是空指针耗费内存空间。

Trie树的基本性质可以归纳为:

(1)根节点不包含字符,除根节点外的每个节点只包含一个字符。

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

(3)每个节点的所有子节点包含的字符串不相同。

    相关评论

    阅读本文后您有什么感想? 已有人给出评价!

    • 8 喜欢喜欢
    • 3 顶
    • 1 难过难过
    • 5 囧
    • 3 围观围观
    • 2 无聊无聊

    热门评论

    最新评论

    发表评论 查看所有评论(0)

    昵称:
    表情: 高兴 可 汗 我不要 害羞 好 下下下 送花 屎 亲亲
    字数: 0/500 (您的评论需要经过审核才能显示)
    推荐文章

    没有数据