字典树是一种树形数据结构,他有如下特点:
每个节点都有固定个数的指向儿子节点的指针,她的儿子某一个节点(如果存在的话)包含的信息就是该节点的下一个字符。
根节点不包含字符,除根节点外每一个节点都只包含一个字符; 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串; 每个节点的所有子节点包含的字符都不相同。
例:作为一个简单的演示,这里我们稍微忽略一些细节。下面的这棵树就是一个简单的
字典树的例子:
如图所示,如果我们按行存储这些数据:
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) 编辑 收藏 引用 所属分类:
算法专题