看图轻松理解数据结构与算法系列(Trie树)

作者:超人汪小建(seaboat)

出处:https://blog.csdn.net/wangyangzhizhou/column/info/25184/2


Trie树

Trie树,是一种搜索树,也称字典树或单词查找树,此外也称前缀树,因为某节点的后代存在共同的前缀。它的key都为字符串,能做到高效查询和插入,时间复杂度为O(k),k为字符串长度,缺点是如果大量字符串没有共同前缀时很耗内存。它的核心思想就是减少没必要的字符比较,使查询高效率,即用空间换时间,再利用共同前缀来提高查询效率。

Trie树特点

  • 根节点不包含字符,其他节点每个节点只包含一个字符。
  • 从根节点到某一节点经过路径的字符连起来即为该节点对应的字符串。
  • 每个节点的所有子节点字符都不相同。

image

插入操作

对he、him、his、she、her、hers六个字符串进行插入,开始插入he字符串,插入第一个字符是h,此时树为空,所以先创建空的根节点,

image

接着从根节点开始,不存在h子节点,于是创建子节点h,

image

在h节点的基础上继续插入第二个字符e,

image

h节点不存在e子节点,创建子节点e,并将该节点标记为单词标志,完成he字符串插入。

image

接着插入him字符串,从根节点开始,发现h子节点已有,

image

移到h子节点,

image

继续处理第二个字符i,h节点不存在i子节点,于是创建i子节点,

image

处理第三个字符m,i节点不存在子节点m,于是创建m子节点,并将该节点标记为单词标志,完成him插入。

image

接着插入his字符串,从根节点开始,发现h子节点已有,

image

移到h子节点,

image

继续处理第二个字符i,h节点已存在i子节点,于是移到i节点,

image

处理第三个字符s,i节点不存在子节点s,于是创建s子节点,并将该节点标记为单词标志,完成his插入。

image

继续插入she字符串,从根节点开始,首先处理第一个字符s,发现s子节点不存在,于是创建s节点,

image

接着处理第二个字符h,s节点不存在h子节点,创建h节点,

image

继续处理第三个字符e,h节点不存在e子节点,创建e节点,并将该节点标记为单词标志,至此完成she字符串插入。

image

类似地,将her、hers字符串插入到树中,最终为:

image

查询操作

查找hi字符串,从根节点开始,

image

根节点存在h子节点,移动到h节点,

image

继续找i子节点,存在,但i并没有单词标志,所以hi字符串不存在。

image

查找his字符串,从根节点开始,

image

根节点存在h子节点,移动到h节点,

image

h节点存在i子节点,移动到i节点,

image

继续找s子节点,存在,而且s节点为单词标志,找到his字符串。

image

而如果查找hist字符串,则最后的t找不到,所以不存在该字符串。

删除操作

情况一

删除she字符串,从根节点开始查找第一个字符s,

image

找到s子节点,下移到s节点,继续查找字符h,

image

找到h子节点,下移到h节点,继续查找字符e,

image

找到e节点,已经找到she字符串,将e节点的单词标志去掉,

image

此时发现e节点为叶子节点,将其删除,

image

删除后发现h节点为叶子节点,且其不是单词标志,将其删除,

image

删除后发现s节点为叶子节点,且其不是单词标志,将其删除,完成she字符串删除操作。

image

情况二

删除her字符串,从根节点开始查找第一个字符h,

image

找到h子节点,下移到h节点,继续查找字符e,

image

找到e子节点,下移到e节点,继续查找字符r,

image

找到r子节点,此时完成整个字符串查找,因为不是叶子节点,只需将其单词标志去掉即可。

image

情况三

删除his,从根节点开始查找第一个字符h,

image

找到h子节点,下移到h节点,继续查找字符i,

image

找到i子节点,下移到i节点,继续查找字符s,

image

找到s子节点,此时完成整个字符串查找,

image

删除后发现s节点为叶子节点,将其删除,

image

删除后发现i节点为非叶子节点,停止删除,完成his字符串删除操作。

赞(1) 打赏

如未加特殊说明,此网站文章均为原创,转载必须注明出处。Java 技术驿站 » 看图轻松理解数据结构与算法系列(Trie树)
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

关注【Java 技术驿站】公众号,每天早上 8:10 为你推送一篇技术文章

扫描二维码关注我!


关注【Java 技术驿站】公众号 回复 “VIP”,获取 VIP 地址永久关闭弹出窗口

免费获取资源

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏