Data Structures Algorithms 简明教程
Tries Data Structure
trie 是一种多路搜索树，它根本用于从字符串或一组字符串中检索特定的键。它以一种有效的方式存储数据，因为它对字母表中的每个字母都使用指针。
A trie is a type of a multi-way search tree, which is fundamentally used to retrieve specific keys from a string or a set of strings. It stores the data in an ordered efficient way since it uses pointers to every letter within the alphabet.
trie 数据结构基于字符串的公共前缀。考虑到集中字符串的数量，根节点可以具有任意数目的节点。trie 的根节点不包含任何值，只包含其子节点的指针。
The trie data structure works based on the common prefixes of strings. The root node can have any number of nodes considering the amount of strings present in the set. The root of a trie does not contain any value except the pointers to its child nodes.
有三种类型的 trie 数据结构 −
There are three types of trie data structures −
-
Standard Tries
-
Compressed Tries
-
Suffix Tries
trie 的实际应用包括：自动更正、文本预测、情感分析和数据科学。
The real-world applications of trie include − autocorrect, text prediction, sentiment analysis and data sciences.
Basic Operations in Tries
trie 数据结构还执行树数据结构执行的相同操作。它们是：
The trie data structures also perform the same operations that tree data structures perform. They are −
-
Insertion
-
Deletion
-
Search
Insertion operation
trie 中的插入操作是一种简单的方法。trie 中的根不包含任何值，并且插入操作从根的直接子节点开始，这些子节点充当其子节点的键。然而，我们观察到trie中的每个节点都代表输入字符串中的一个字符。因此，字符一个接一个地添加到trie中，而trie中的链接充当指向下一级节点的指针。
The insertion operation in a trie is a simple approach. The root in a trie does not hold any value and the insertion starts from the immediate child nodes of the root, which act like a key to their child nodes. However, we observe that each node in a trie represents a singlecharacter in the input string. Hence the characters are added into the tries one by one while the links in the trie act as pointers to the next level nodes.
Deletion operation
trie 中的删除操作使用自下而上的方法执行。在trie中搜索元素并进行删除（如果找到）。然而，在执行删除操作时需要记住一些特殊的情况。
The deletion operation in a trie is performed using the bottom-up approach. The element is searched for in a trie and deleted, if found. However, there are some special scenarios that need to be kept in mind while performing the deletion operation.
Case 1 - 键是唯一的 - 在这种情况下，整个键路径从节点中删除。（唯一键表示没有其他路径从一条路径分支出来）。
Case 1 − The key is unique − in this case, the entire key path is deleted from the node. (Unique key suggests that there is no other path that branches out from one path).
Case 2 - 键不是唯一的 - 更新叶节点。例如，如果要删除的键是 see ，但它是另一个键 seethe 的前缀；我们删除 see 并将 t、h 和 e 的布尔值更改为 false。
Case 2 − The key is not unique − the leaf nodes are updated. For example, if the key to be deleted is see but it is a prefix of another key seethe; we delete the see and change the Boolean values of t, h and e as false.
Case 3 - 要删除的键已经有一个前缀 - 直到前缀的值被删除，并且前缀保留在树中。例如，如果要删除的键是 heart ，但存在另一个键 he ；因此，我们删除 a、r 和 t，直到只剩下 he。
Case 3 − The key to be deleted already has a prefix − the values until the prefix are deleted and the prefix remains in the tree. For example, if the key to be deleted is heart but there is another key present he; so we delete a, r, and t until only he remains.
Search operation
在trie中搜索是一种相当直接的方法。我们只能基于键节点（插入操作开始的节点）向下移动trie的级别。搜索直到路径的末尾。如果找到该元素，则搜索成功；否则，搜索提示不成功。
Searching in a trie is a rather straightforward approach. We can only move down the levels of trie based on the key node (the nodes where insertion operation starts at). Searching is done until the end of the path is reached. If the element is found, search is successful; otherwise, search is prompted unsuccessful.