样本树特征、插入查询和删除操作等算法图

样本树

样本树是搜索树，也称为字典树或词搜索树。它也称为前缀树，因为节点的后代有一些共同点。字首。它的key都是字符串，可以实现高效的查询和插入。时间复杂度为 O(k)，其中 k 是字符串的长度。缺点是如果大量字符串没有公共前缀，它会使用大量内存。其核心思想是减少不必要的字符比较，让查询更加高效，即以空间换时间，然后使用公共前缀来提高查询效率。

尝试树函数

• 根节点不包含任何字符，其他节点仅包含一个字符。
• 从根节点到特定节点的路径上的字符通过该节点对应的字符串连接起来。
• 每个节点中的所有子节点符号都不同。

插入操作

插入六根弦he,him,his,she,her,hers。开始粘贴字符串。第一个插入的字符是h，此时树是空的，所以先创建它。空根节点，

则从根节点开始，没有h子节点，所以创建了子节点h，

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

h节点没有存在 e 子节点 ，创建子节点 e 并将该节点标记为单词标签，完成 he 串插入。

然后放入him字符串，从根节点开始，发现h子节点已经存在，

移动到h子节点，

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

处理第三个字符m，第i个节点没有子节点m，则创建m个子节点，将节点标记为单词标记，完成他的插入。

然后放入他的字符串，从根节点开始，发现h子节点已经存在，

移动到h子节点，

继续处理第二个字符i，h节点已经有i子节点，然后移动到i节点，

处理第三个字符s，i节点没有子节点s，所以创建s子节点，并将该节点标记为单词标记，完成插入。

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

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

继续处理第三个字符e，h节点不存在e子节点，创建e节点，并将该节点标记为单词标签，从而完成严格插入。

同样的方式将her和她的字符串插入到树中，最终的结果是：

查询操作

找到hi字符串，从根节点开始，根节点child节点，移动到h节点，

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

找到他的字符串，从根节点开始，

根节点有h个子节点，移动到h节点，

h节点有i个子节点，移动到i节点，❀e查找s 子节点 Node 存在，并且 s 节点是一个单词标签，找到他的字符串。

如果搜索历史字符串，找不到最后一个t，因此该字符串不存在。

删除操作

情况一

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

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

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

找到 e 节点。找到母线。删除 e 节点的单词标签。

此时发现e节点是叶子节点。删除它，

删除后发现h节点是叶子节点，而且不是单词标签，删除它，

删除后发现s节点是叶子节点，且不是单词标签，将其删除，完成字符串删除操作。 ？ ，向下移动到e节点，继续查找字符r，

找到r子节点，则结束整个字符串查找。因为它不是叶子节点，所以去掉它的word标签即可。 ？移动到i节点，继续查找字符s，

找到s子节点。至此，整个字符串查找就完成了。

删除后发现s节点是叶子节点，所以将其删除。

删除后，i节点已经找到了。如果是非叶子节点，则停止删除，完成他的字符串删除操作。

作者：超人王小健
链接：https://juejin.im/post/5ba198ba5188255c7c6555c9
来源：掘金❙版权属于❙。商业转载请联系作者获取授权。非商业转载请注明出处。