数据结构之Radix和Trie

数据结构可视化演示链接，也就是视频中的网址

Radix树：压缩后的Trie树

Radix树演示

Radix树，也被称为压缩前缀树或缩写为PATRICIA，是一种非常有效的数据结构，用于存储字符串集合。它是一种自平衡的树形数据结构，用于快速查找、插入和删除字符串。Radix树在处理具有许多不同前缀的字符串时非常有效。

工作原理类

1. Radix树由一个根节点开始，每个节点可以包含多个子节点。每个节点代表一个字符或者字符序列，通常是一个字母或者单词。节点之间的连接代表了字符之间的关系，使得在查找时能够沿着路径进行导航。
2. 在Radix树中，每个节点都存储与其关联的字符串前缀。这个前缀是该节点到根节点路径上的字符序列。通过比较目标字符串的前缀与树中节点的前缀，可以确定目标字符串是否在树中。
3. 当查询一个字符串时，从根节点开始，沿着与目标字符串前缀匹配的路径向下遍历。如果找到一个节点的前缀与目标字符串完全匹配，那么就找到了目标字符串。如果遍历完整个字符串都没有找到匹配的节点，则说明目标字符串不在树中。
4. Radix树的优点在于它通过共享相同前缀来压缩存储空间，并提供高效的插入、删除和查找操作。这种数据结构特别适用于处理具有许多不同前缀的字符串集合。

优缺点

优点

1. 高效处理具有许多不同前缀的字符串。通过存储共享前缀的字符串，Radix树可以减少所需的存储空间，并提高查找操作的效率。
2. 插入、查询和删除操作的时间复杂度为O(k)，其中k是字符串的长度。这使得Radix树在处理大量数据时相对高效。
3. 由于其自平衡的特性，Radix树在插入和删除操作时能够保持高效。

缺点

1. 键的分布对树的结构和内存利用率影响很大。如果键的分布很稀疏，那么Radix树就会浪费很多空间，节点的使用率不高。
2. 即使只想存储一个键值对，如果键的长度有几百字符长，那么每个字符的层级都需要大量的额外空间。这会导致空间使用效率低下。
3. 插入、查找和删除操作可能会涉及多个层级，导致这些操作的时间复杂度较高。因此，Radix树在处理大量数据时可能不够高效。
4. 由于Radix树的结构特性，它可能不适合处理动态数据集。在动态数据集中，频繁的插入、删除操作可能会导致树结构的失衡，进而影响查询效率。

Trie树

Trie是一种用于存储字符串集合的数据结构，它可以快速地查找、插入和删除字符串。每个节点表示一个字符，每个节点都有多个子节点，每个子节点表示一个字符。根节点表示一个空字符串，所有其他节点都通过从根节点到该节点的路径唯一标识。

Trie树演示

Trie的一个关键特性是它可以有效地处理具有许多不同前缀的字符串。例如，对于一个包含"apple"、“application”、"append"和"applicable"的字符串集合，Trie将有效地存储这些字符串，并且可以快速查找具有特定前缀的字符串。

工作原理类

1. 将字符串集合中的每个字符串逐个插入到Trie树中。在插入过程中，将字符串的每个字符作为节点存储在树中，每个节点都有一个指向其子节点的链接数组，其中每个子节点都表示一个字符。
2. 当插入一个字符串时，从根节点开始逐个比较字符串中的字符。如果当前节点没有与字符串中当前字符匹配的子节点，则创建一个新的子节点。通过这种方式，将所有字符串插入Trie树中。
3. 在查询过程中，从根节点开始，逐个比较目标字符串中的字符。如果在某个节点处匹配成功，则继续向下遍历直到终点节点。如果遍历完所有字符后达到终点节点，表示找到了匹配的字符串。如果在某个节点处没有匹配的字符，则返回空或继续向下遍历其他可能的路径。
4. Trie树的核心思想是利用字符串的公共前缀来降低存储和查询的开销。通过将具有相同前缀的字符串聚合在一起，Trie树可以显著减少存储空间和查询时间。

优缺点

优点

1. 快速查找：Trie能够快速地查找目标字符串，时间复杂度为O(m)，其中m是目标字符串的长度。通过比较字符串的每个字符，从根节点开始遍历到目标字符串的最后一个字符的路径，可以找到目标字符串在Trie中的位置。
2. 节省空间：Trie只存储实际出现的字符，而不是存储整个字符串。这使得Trie在存储大量字符串时可以节省空间。
3. 自动完成：Trie广泛用于需要自动完成功能的应用程序，例如搜索引擎或预测文本输入。通过存储常见的字符串，Trie可以快速提供可能的完成选项。
4. 高效插入和删除：Trie支持快速插入和删除字符串，时间复杂度为O(m)。通过简单地修改树中的节点链接，可以添加或删除字符串。
5. 高效排序：Trie可用于对字符串集合进行高效排序。通过遍历Trie的节点，可以轻松地按照字典序排列所有存储的字符串。

缺点

1. 空间消耗大：当处理大量字符串时，Trie可能会占用大量内存空间。这是因为在Trie中，每个字符串都由多个节点组成，每个节点都需要存储字符信息和指向子节点的指针。
2. 键的分布对树的结构和内存利用率影响很大。如果键的分布很稀疏，那么Trie就会浪费很多空间，节点的使用率不高。
3. 对于较长的字符串的处理可能会让链变得很长，导致空间利用率降低。

总的来说，Trie树把很多的公共前缀独立出来共享了。这样避免了很多重复的存储。想想字典集的方式，一个个的key被单独的存储，即使他们都有公共的前缀也要单独存储。相比字典集的方式，Trie树显然节省更多的空间。

Trie树其实依然比较浪费空间，比如：如果大量字符串没有共同前缀时。

总结

综上所述，树结构适应的应用场景不同，在使用时需要注意其可能存在的缺点，并考虑是否适合具体的应用需求。