RadixTree

基本概念

概念

如果对 Trie 不太了解，可以看看我的往期博客：

https://oreki.blog.csdn.net/article/details/109076473

Radix Tree是一种基于 Trie（字典树）的数据结构，旨在解决字符串搜索和匹配的问题。它最早由 Fredkin 在 1960 年提出，并在之后被广泛应用于各种应用领域。其最大的特点就是在 Trie 的基础上，加入了路径压缩的逻辑，通过合并前缀的方式大大的减少了 Trie 中的节点冗余问题，不仅提高了查询效率，还减少了存储空间的使用。

Radix Tree VS Trie Tree

那么，Radix Tree 是如何做到合并前缀的呢？在 Radix Tree 中每个节点存储的不再是一个字符，而是字符串的前缀，当插入/删除节点时，会通过合并/分裂前缀的方式，来尽可能的压缩树的高度，下面给出几个例子来进行对比。

下面来分别对比一下在 Radix/Trie 中，插入和删除的流程

插入：

初始状态

初始状态

插入 abcd，此时 Radix Tree 会将前缀保存到同一个节点中。而 Trie 一个节点只能保存一个字符。

插入 abcd

接着插入 abce，此时 Radix Tree 会获取找到匹配到最大前缀的节点 abcd，保留最大前缀，并将 d 和新插入的 e 存储到子节点中。

插入 abce

接着插入字符串 aecb。此时找到具有最大前缀的节点 abc，将其拆分为前缀 a，后缀 bc，将 bc 作为 a 的子节点，并继承其原有子节点，同时将新插入的字符串 ecb 存储到 a 的子节点中。

插入 aecb

插入 aecd，此时找到最大前缀节点 ecb，保留匹配前缀 ec，将剩余字符 b 和新插入节点 d 作为子节点。

插入 aecd

删除：

基于上面的树，接着进行删除，首先删除 abcd。此时由于 d 被删除，整下 bc 和 e 节点为单路径，此时将其合并为 bce。

删除 abcd

删除 abce，同理，此时 a 仅剩下单路径，将其与 ec 合并为 aec。

删除 abce

删除 aecb，合并 aec 与剩余路径 d，变为 aecd。

删除 aecb

接着删除 aecd，此时两树为空。

删除 aecd

应用场景

由于 RadixTree 具有高效的字符串匹配能力以及空间效率，其被广泛应用于字符串搜索、匹配的场景，比较常见的几个用法如：

• 路由表、DNS 等网络设备的查找和匹配。
• 编译器中预定义符号和关键词查找。
• Linux 的进程、线程管理，Page Cache 的搜索。
• 自然语言处理

实现

上面介绍了原理，下面用 C++ 来简单实现一个 Radix Tree 的 demo。

数据结构

首先定义 RadixTreeNode，我们需要用一个 string 来存储字符串前缀，用一个 bool 变量来标识当前路径是否构成一个完整的字符串，再用一个哈希表来存储所有的子节点（这里不用数组的原因是删除一个节点时，需要偏移多个节点，且查找时需要遍历数组）。

class RadixTreeNode {
public:explicit RadixTreeNode(const string &word = "", bool is_end = false): word(word), is_end(is_end) {}unordered_set<shared_ptr<RadixTreeNode>> children;string word;bool is_end;
};

接着定义 RadixTree，首先我们需要存储一个 root 节点的指针，由于 C++ 中没有 GC 机制，为了避免内存泄漏，这里统一用智能指针来进行管理。这里实现了基本的插入、删除、查找函数，以及递归调用的辅助函数。

class RadixTree {
public:RadixTree() : root(make_shared<RadixTreeNode>()){};virtual ~RadixTree() = default;RadixTree(const RadixTree &) = delete;RadixTree &operator=(const RadixTree &) = delete;void insert(const string &str);void erase(const string &str);bool search(const string &str);private:shared_ptr<RadixTreeNode> root;void insert_helper(const string &str, shared_ptr<RadixTreeNode> node);shared_ptr<RadixTreeNode> erase_helper(const string &str,shared_ptr<RadixTreeNode> node);bool search_helper(const string &str, shared_ptr<RadixTreeNode> node);

插入

1. 如果插入的是空字符串，则直接将根节点标记为完整字符串，否则继续往下。
2. 遍历当前节点的子节点，共有以下三种情况：
   • 节点没有子节点：将字符串的内容直接作为新的子节点插入。
   • 子节点中有能够匹配到前缀的节点：
     • 当前节点的内容与字符串完全匹配：将当前前缀标记为完整字符串。
     • 当前节点的内容是字符串的前缀：此时将字符串拆分为公共前缀和剩余字符，用剩余字符与该子节点继续递归进行查找，寻找合适的插入位置，继续回到流程 2。
     • 当前节点的内容和字符串具有公共前缀：此时将当前节点的内容拆分为公共前缀，剩余后缀两部分。当前节点保留前缀内容，将后缀作为子节点插入，此时如果字符串还有剩余字符，则将其也作为子节点一同插入。
   • 子节点中没有与之具有公共前缀的节点：将字符串的内容直接作为新的子节点插入。

void insert(const string &str) {if (str.empty()) {root->is_end = true;} else {insert_helper(str, root);}
}void insert_helper(const string &str, shared_ptr<RadixTreeNode> node) {// 如果当前没有子节点，则直接作为新的子节点if (node->children.empty()) {auto new_node = make_shared<RadixTreeNode>(str, true);node->children.insert(new_node);return;}bool is_match = false;for (auto current : node->children) {int i = 0;for (; i < str.size() && i < current->word.size(); i++) {if (str[i] != current->word[i]) {break;}}if (i != 0) {is_match = true;// 情况一：当前节点的内容与字符串完全匹配，则直接将该前缀标记为完整if (i == str.size() && i == current->word.size()) {current->is_end = true;} else if (i != current->word.size()) {// 如果当前节点的内容是字符串的部分前缀，则进行分裂auto new_node = make_shared<RadixTreeNode>(current->word.substr(i),current->is_end);current->word = current->word.substr(0, i);current->is_end = (i == str.size()) ? true : false;current->children.swap(new_node->children);current->children.insert(new_node);if (i != str.size()) {auto new_node2 = make_shared<RadixTreeNode>(str.substr(i), true);current->children.insert(new_node2);}} else {// 如果当前节点已匹配完，则继续往子节点匹配insert_helper(str.substr(i), current);}if (is_match) {return;}}}// 如果没有找到，则直接插入auto new_node = make_shared<RadixTreeNode>(str, true);node->children.insert(new_node);
}

删除

1. 如果删除的是空字符串，则直接将 root 标记为非完整字符串。
2. 遍历当前节点的子节点：
   • 当前节点的内容与字符串完全匹配：
     • 当前节点有子节点：将当前节点标记为非完整字符串。
     • 当前节点没子节点：直接删除该节点。此时如果在删除了该节点后，当前节点的父节点仅剩下一个子节点，并且父节点中存储一个不完整字符串，此时可以将当前节点和父节点合并，用于压缩路径。
   • 当前节点的内容是字符串的前缀：将字符串拆分为公共前缀和剩余后缀，用后缀继续向下递归查找到合适的位置进行删除。
   • 字符串是当前节点内容的前缀：该字符串一定不在树中，删除结束。

void erase(const string &str) {if (str.empty()) {root->is_end = false;} else {erase_helper(str, root);}
}shared_ptr<RadixTreeNode> erase_helper(const string &str,shared_ptr<RadixTreeNode> node) {bool is_match = false;for (auto current : node->children) {int i = 0;for (; i < str.size() && i < current->word.size(); i++) {if (str[i] != current->word[i]) {break;}}if (i != 0) {is_match = true;// 情况一：当前节点的内容与字符串完全匹配if (i == str.size() && i == current->word.size()) {// 如果该节点没有子节点，则将该节点删除。否则将is_end标记为falseif (current->children.empty()) {node->children.erase(current);} else {current->is_end = false;}// 如果删除了该节点后，父节点仅剩下一个子节点，且父节点不完整，则将两个节点合并if (node->children.size() == 1 && !node->is_end && node != root) {auto sub_node = *node->children.begin();node->children.erase(sub_node);node->is_end = sub_node->is_end;node->word.append(sub_node->word);node->children = sub_node->children;return node;}}// 情况二：当前节点是字符串的前缀else if (i == current->word.size()) {// 继续向下搜索，如果返回值不为空则说明需要合并节点auto sub_node = erase_helper(str.substr(i), current);if (sub_node && node->children.size() == 1 && !node->is_end &&node != root) {auto sub_node = *node->children.begin();node->children.erase(sub_node);node->is_end = sub_node->is_end;node->word.append(sub_node->word);node->children = sub_node->children;}}// 情况三：字符串是当前节点的前缀，此时字符串必定不存在，删除结束else {break;}}if (is_match) {return nullptr;}}return nullptr;
}

查找

查找实现的逻辑如下：

1. 从根节点出发，如果字符串为空，判断空字符有没有存储到根节点，没有往下执行。
2. 遍历当前节点的所有子节点，查找是否存在公共前缀，此时存在以下四种情况：
   • 当前节点的内容与字符串完全匹配：此时根据当前路径是否为完整单词，判断查找是否成功。
   • 当前节点的内容是字符串的前缀：将字符串拆分为前缀和剩余后缀，将后缀继续递归到该节点的子节点处继续查询，重复流程 2
   • 字符串是当前节点内容的前缀：查找失败，这一部分前缀必定没有插入到树中。
   • 无公共前缀：继续遍历下一个子节点，如果已经遍历完，则认为查找失败，该字符串不存在。

bool search(const string &str) {if (str.empty()) {return root->is_end;}return search_helper(str, root);
}bool search_helper(const string &str, shared_ptr<RadixTreeNode> node) {for (auto current : node->children) {int i = 0;for (; i < str.size() && i < current->word.size(); i++) {if (str[i] != current->word[i]) {break;}}if (i != 0) {// 情况一：当前节点的内容与字符串完全匹配，根据是否为完整单词判断结果if (i == str.size() && i == current->word.size()) {return current->is_end;}// 情况二：当前节点的内容是字符串的前缀else if (i == current->word.size()) {return search_helper(str.substr(i), current);}// 情况三：字符串的内容是当前节点的前缀，直接返回错误else {return false;}}}// 没有找到return false;
}

完整代码

//
// Created by orekilee on 2023/3/31.
//#ifndef RADIX_RADIXTREE_CPP
#define RADIX_RADIXTREE_CPP#include <iostream>
#include <memory>
#include <string>
#include <unordered_set>using namespace std;class RadixTreeNode {
public:explicit RadixTreeNode(const string &word = "", bool is_end = false): word(word), is_end(is_end) {}unordered_set<shared_ptr<RadixTreeNode>> children;string word;bool is_end;
};class RadixTree {
public:RadixTree() : root(make_shared<RadixTreeNode>()){};virtual ~RadixTree() = default;RadixTree(const RadixTree &) = delete;RadixTree &operator=(const RadixTree &) = delete;void insert(const string &str) {if (str.empty()) {root->is_end = true;} else {insert_helper(str, root);}}void erase(const string &str) {if (str.empty()) {root->is_end = false;} else {erase_helper(str, root);}}bool search(const string &str) {if (str.empty()) {return root->is_end;}return search_helper(str, root);}private:shared_ptr<RadixTreeNode> root;void insert_helper(const string &str, shared_ptr<RadixTreeNode> node) {// 如果当前没有子节点，则直接作为新的子节点if (node->children.empty()) {auto new_node = make_shared<RadixTreeNode>(str, true);node->children.insert(new_node);return;}bool is_match = false;for (auto current : node->children) {int i = 0;for (; i < str.size() && i < current->word.size(); i++) {if (str[i] != current->word[i]) {break;}}if (i != 0) {is_match = true;// 情况一：当前节点的内容与字符串完全匹配，则直接将该前缀标记为完整if (i == str.size() && i == current->word.size()) {current->is_end = true;} else if (i != current->word.size()) {// 如果当前节点的内容是字符串的部分前缀，则进行分裂auto new_node = make_shared<RadixTreeNode>(current->word.substr(i),current->is_end);current->word = current->word.substr(0, i);current->is_end = (i == str.size()) ? true : false;current->children.swap(new_node->children);current->children.insert(new_node);if (i != str.size()) {auto new_node2 = make_shared<RadixTreeNode>(str.substr(i), true);current->children.insert(new_node2);}} else {// 如果当前节点已匹配完，则继续往子节点匹配insert_helper(str.substr(i), current);}if (is_match) {return;}}}// 如果没有找到，则直接插入auto new_node = make_shared<RadixTreeNode>(str, true);node->children.insert(new_node);}shared_ptr<RadixTreeNode> erase_helper(const string &str,shared_ptr<RadixTreeNode> node) {bool is_match = false;for (auto current : node->children) {int i = 0;for (; i < str.size() && i < current->word.size(); i++) {if (str[i] != current->word[i]) {break;}}if (i != 0) {is_match = true;// 情况一：当前节点的内容与字符串完全匹配if (i == str.size() && i == current->word.size()) {// 如果该节点没有子节点，则将该节点删除。否则将is_end标记为falseif (current->children.empty()) {node->children.erase(current);} else {current->is_end = false;}// 如果删除了该节点后，父节点仅剩下一个子节点，且父节点不完整，则将两个节点合并if (node->children.size() == 1 && !node->is_end && node != root) {auto sub_node = *node->children.begin();node->children.erase(sub_node);node->is_end = sub_node->is_end;node->word.append(sub_node->word);node->children = sub_node->children;return node;}}// 情况二：当前节点是字符串的前缀else if (i == current->word.size()) {// 继续向下搜索，如果返回值不为空则说明需要合并节点auto sub_node = erase_helper(str.substr(i), current);if (sub_node && node->children.size() == 1 && !node->is_end &&node != root) {auto sub_node = *node->children.begin();node->children.erase(sub_node);node->is_end = sub_node->is_end;node->word.append(sub_node->word);node->children = sub_node->children;}}// 情况三：字符串是当前节点的前缀，此时必定查询失败else {break;}}if (is_match) {return nullptr;}}return nullptr;}bool search_helper(const string &str, shared_ptr<RadixTreeNode> node) {for (auto current : node->children) {int i = 0;for (; i < str.size() && i < current->word.size(); i++) {if (str[i] != current->word[i]) {break;}}if (i != 0) {// 情况一：当前节点的内容与字符串完全匹配，根据是否为完整单词判断结果if (i == str.size() && i == current->word.size()) {return current->is_end;}// 情况二：当前节点的内容是字符串的前缀else if (i == current->word.size()) {return search_helper(str.substr(i), current);}// 情况三：字符串的内容是当前节点的前缀，直接返回错误else {return false;}}}// 没有找到return false;}
};#endif // RADIX_RADIXTREE_CPP