基数树的数据结构和算法图

基数树

基数树，即基数树，也称为压缩前缀树，是一种提供存储键和查找的数据结构。与Trie不同的是，它对Trie树进行空间优化，只有一个子节点的中心节点会被压缩。而且，Radix树的插入、查询、删除操作的时间复杂度都是O(k)。

基数树特征

• 一般由根节点、中心节点和叶节点组成。
• 每个节点可以包含一个或多个字符。
• 树叶节点的数量就是数据条目的数量。
• 从根节点到给定节点的路径上的字符将连接到与该节点对应的字符串。
• 每个节点的所有子节点字符串都不相同。

插入操作

插入七弦romane、罗马努斯、罗穆卢斯、鲁本斯、鲁伯、鲁比孔、rubicundus。开始插入romane。这时候，树上是空的。直接创建“romane”节点，并添加该节点的结束标签设置为true，romane插入完成。

然后插入罗马努斯。此时根节点不再为空，所以我们从根节点开始逐个字符进行比较。我们发现两者的前缀“roman”是相同的。我们需要先将原来的“romane”节点进行拆分，创建一个新的公共节点。 “roman”节点前缀，

则将原来的“romane”节点设置为“e”，“e”是“romane”中去除公共前缀“roman”后剩余的字符，并指向新的公共前缀节点。对于子节点“e”，子节点索引为“e”。

然后继续新建一个“us”节点，“us”就是去掉公共前缀“roman”后剩下的字符“romanus”，

最后将公共前缀“roman”节点指向子节点“us”，索引为“u”，“us”节点结束标签设置为true。

将romulus放下，从根节点开始逐个字符进行比较。发现两者的前缀“rom”是相同的。需要将原来的“roman”节点进行拆分，并在第一个节点创建一个新的公共前缀“rom”，

然后将原来的“roman”节点设置为“an”，“an”是“roman”的剩余字符后。删除公共前缀“rom”，并将新的公共前缀节点指向子节点“an”，并将子节点索引为“a”。

然后继续创建一个新的“ulus”结。 “ulus”是“romulus”中删除公共前缀“rom”后剩余的字符。

最后将公共前缀“rom”节点指向子节点“ulus”，其索引为“u”，并将节点“ulus”的结束标记设置为true。

继续插入rubens，从根节点开始逐字符比较。说明两者的前缀“r”是相同的。需要先将原来的“rom”节点进行拆分，创建一个新的公共前缀“r”节点，

然后将原来的“rom”节点设置为“om”，“om”是“rom”之后剩余的字符删除前缀公共ater“r”，并将新的公共前缀节点指向子节点“om”，子节点索引为“o”。

然后继续创建新的“ubens”节点。 “ubens”是“rubens”中删除公共前缀“r”后剩余的字符。

最后将该节点的公共前缀“r”指向子节点“ubens”，其索引为“u”，并将“ubens”节点的结束标签设置为true。

继续插入ruber并从根节点开始逐个字符进行比较。发现比较“r”后，根节点已经没有值可以比较了，于是我开始从“r”节点开始寻找子节点，

根据第二个字符“u”找到了对应的子节点。节点，即“ubens”节点。

剩余的“uber”字符串不断地与节点一一比较。发现前缀“ube”是相同的，原来的“ubens”应该被拆分。节点，首先创建一个新的公共“ube”节点，

然后将原来的“ubens”节点设置为“ns”，“ns”是“ubens”中去除公共前缀“ube”后剩余的字符，并点前缀节点 public new 到索引为“n”的子节点“ns”。而且，最初指向节点“ubens”的索引“u”指向节点“ube”。

然后继续创建新的“r”节点，“r”是“ruber”中去掉公共前缀“r”和“ube”后剩余的字符，

最后将公共前缀“ube”节点指向“r”子节点，索引为“r”，“r”节点的最后一个标签设置为true。

同样的方法，将rubicon放入树中，结果如下。

继续插入rubicundus，结果如下。

查询操作

如果查找ruok，则从根节点开始比较，“r”相同则根节点没有值继续比较，

所以根据查找下一个子节点索引“u”，在“ub”子节点中继续一一比较，

发现“uok”无法匹配，“ruok”不存在，因此搜索结束。

如果您正在寻找卢比孔，请从根节点开始比较。 “r”相同，根节点没有值继续比较。

所以根据索引“u”找到下一个子节点，并继续在子节点“ub”上。逐个字符比较，

比较节点后，继续按索引“i”查找子节点，在节点“ic”处继续逐个字符比较，

比较节点后，继续按索引“查找子节点” o”，继续在“on”节点中一一比较字符。此时“rubicon”已完成所有字符的比较，并且“on”节点的最后一个符号为true，这意味着字符串“rubicon”存在，搜索完成。

如果你正在寻找浪漫，就从根节点开始比较。 “r”相同，根节点没有值继续比较。

然后根据索引“o”找到下一个子节点，并在子节点“om”上继续。逐个字符比较，

比较节点后，继续根据索引“a”查找子节点，在节点“an”处继续逐个字符比较。至此，“roman”已完成所有字符的比较，但“an”标志节点为假，因此缺少字符串“roman”，搜索完成。

作者：超人王小健
来源：掘金