JulyRina's blog
welcome to July Rina's blog
posts - 22,comments - 1,trackbacks - 0
字典树是一种树形数据结构,他有如下特点:
    每个节点都有固定个数的指向儿子节点的指针,她的儿子某一个节点(如果存在的话)包含的信息就是该节点的下一个字符。
    根节点不包含字符,除根节点外每一个节点都只包含一个字符; 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串; 每个节点的所有子节点包含的字符都不相同。
例:作为一个简单的演示,这里我们稍微忽略一些细节。下面的这棵树就是一个简单的字典树的例子:

如图所示,如果我们按行存储这些数据:
apple
append
and
antiy
banana
band
我们需要5+6+3+5+6+4=29 B 的空间。
但是字典树只需要20 B 的空间。
这在数据量更大的时候能起到更好的效果。

字典树能够线性时间范围内实现数据的增删改查。
posted on 2015-03-09 18:55 JulyRina 阅读(313) 评论(0)  编辑 收藏 引用 所属分类: 算法专题

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理