黑马程序员技术交流社区

标题: 【上海校区】看图轻松理解数据结构与算法系列(Trie树) [打印本页]
作者: 不二晨    时间: 2018-9-25 09:48
标题: 【上海校区】看图轻松理解数据结构与算法系列(Trie树)
前言推出一个新系列，《看图轻松理解数据结构和算法》，主要使用图片来描述常见的数据结构和算法，轻松阅读并理解掌握。本系列包括各种堆、各种队列、各种列表、各种树、各种图、各种排序等等几十篇的样子。
Trie树Trie树，是一种搜索树，也称字典树或单词查找树，此外也称前缀树，因为某节点的后代存在共同的前缀。它的key都为字符串，能做到高效查询和插入，时间复杂度为O(k)，k为字符串长度，缺点是如果大量字符串没有共同前缀时很耗内存。它的核心思想就是减少没必要的字符比较，使查询高效率，即用空间换时间，再利用共同前缀来提高查询效率。
Trie树特点

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


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


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


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


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


移到h子节点，


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


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


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


移到h子节点，


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


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


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


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


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


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


查询操作查找hi字符串，从根节点开始，


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


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


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


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


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


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


而如果查找hist字符串，则最后的t找不到，所以不存在该字符串。
删除操作情况一删除she字符串，从根节点开始查找第一个字符s，


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


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


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


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


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


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


情况二删除her字符串，从根节点开始查找第一个字符h，


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


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


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


情况三删除his，从根节点开始查找第一个字符h，


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


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


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


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


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



链接：https://juejin.im/post/5ba198ba5188255c7c6555c9



作者: 不二晨    时间: 2018-10-10 11:29
奈斯



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2