Trie树特点、插入查询删除操作等算法图解

Trie树

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

Trie树特点

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

插入操作

对he、him、his、she、her、hers六个字符串进行插入，开始插入he字符串，插入第一个字符是h，此时树为空，所以先创建空的根节点，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5110.html

接着从根节点开始，不存在h子节点，于是创建子节点h，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5110.html

在h节点的基础上继续插入第二个字符e，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5110.html

h节点不存在e子节点，创建子节点e，并将该节点标记为单词标志，完成he字符串插入。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5110.html

接着插入him字符串，从根节点开始，发现h子节点已有，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5110.html

移到h子节点，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5110.html

继续处理第二个字符i，h节点不存在i子节点，于是创建i子节点，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5110.html

处理第三个字符m，i节点不存在子节点m，于是创建m子节点，并将该节点标记为单词标志，完成him插入。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5110.html

接着插入his字符串，从根节点开始，发现h子节点已有，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5110.html

移到h子节点，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5110.html

继续处理第二个字符i，h节点已存在i子节点，于是移到i节点，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5110.html

处理第三个字符s，i节点不存在子节点s，于是创建s子节点，并将该节点标记为单词标志，完成his插入。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5110.html

继续插入she字符串，从根节点开始，首先处理第一个字符s，发现s子节点不存在，于是创建s节点，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5110.html

接着处理第二个字符h，s节点不存在h子节点，创建h节点，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5110.html

继续处理第三个字符e，h节点不存在e子节点，创建e节点，并将该节点标记为单词标志，至此完成she字符串插入。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5110.html

类似地，将her、hers字符串插入到树中，最终为：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5110.html

查询操作

查找hi字符串，从根节点开始，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5110.html

根节点存在h子节点，移动到h节点，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5110.html

继续找i子节点，存在，但i并没有单词标志，所以hi字符串不存在。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5110.html

查找his字符串，从根节点开始，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5110.html

根节点存在h子节点，移动到h节点，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5110.html

h节点存在i子节点，移动到i节点，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5110.html

继续找s子节点，存在，而且s节点为单词标志，找到his字符串。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5110.html

而如果查找hist字符串，则最后的t找不到，所以不存在该字符串。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5110.html

删除操作

情况一

删除she字符串，从根节点开始查找第一个字符s，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5110.html

找到s子节点，下移到s节点，继续查找字符h，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5110.html

找到h子节点，下移到h节点，继续查找字符e，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5110.html

找到e节点，已经找到she字符串，将e节点的单词标志去掉，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5110.html

此时发现e节点为叶子节点，将其删除，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5110.html

删除后发现h节点为叶子节点，且其不是单词标志，将其删除，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5110.html

删除后发现s节点为叶子节点，且其不是单词标志，将其删除，完成she字符串删除操作。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5110.html

情况二

删除her字符串，从根节点开始查找第一个字符h，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5110.html

找到h子节点，下移到h节点，继续查找字符e，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5110.html

找到e子节点，下移到e节点，继续查找字符r，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5110.html

找到r子节点，此时完成整个字符串查找，因为不是叶子节点，只需将其单词标志去掉即可。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5110.html

情况三

删除his，从根节点开始查找第一个字符h，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5110.html

找到h子节点，下移到h节点，继续查找字符i，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5110.html

找到i子节点，下移到i节点，继续查找字符s，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5110.html

找到s子节点，此时完成整个字符串查找，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5110.html

删除后发现s节点为叶子节点，将其删除，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5110.html

删除后发现i节点为非叶子节点，停止删除，完成his字符串删除操作。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/5110.html