Data Structures Algorithms 简明教程
Tries Data Structure
trie 是一种多路搜索树，它根本用于从字符串或一组字符串中检索特定的键。它以一种有效的方式存储数据，因为它对字母表中的每个字母都使用指针。
trie 数据结构基于字符串的公共前缀。考虑到集中字符串的数量，根节点可以具有任意数目的节点。trie 的根节点不包含任何值，只包含其子节点的指针。
有三种类型的 trie 数据结构 −
-
Standard Tries
-
Compressed Tries
-
Suffix Tries
trie 的实际应用包括：自动更正、文本预测、情感分析和数据科学。
Insertion operation
trie 中的插入操作是一种简单的方法。trie 中的根不包含任何值，并且插入操作从根的直接子节点开始，这些子节点充当其子节点的键。然而，我们观察到trie中的每个节点都代表输入字符串中的一个字符。因此，字符一个接一个地添加到trie中，而trie中的链接充当指向下一级节点的指针。
Deletion operation
trie 中的删除操作使用自下而上的方法执行。在trie中搜索元素并进行删除（如果找到）。然而，在执行删除操作时需要记住一些特殊的情况。
Case 1 - 键是唯一的 - 在这种情况下，整个键路径从节点中删除。（唯一键表示没有其他路径从一条路径分支出来）。
Case 2 - 键不是唯一的 - 更新叶节点。例如，如果要删除的键是 see ，但它是另一个键 seethe 的前缀；我们删除 see 并将 t、h 和 e 的布尔值更改为 false。
Case 3 - 要删除的键已经有一个前缀 - 直到前缀的值被删除，并且前缀保留在树中。例如，如果要删除的键是 heart ，但存在另一个键 he ；因此，我们删除 a、r 和 t，直到只剩下 he。