特里简介

你有没有想过搜索引擎是如何工作的？Google 如何在几毫秒内为你提供数百万的结果？位于数千英里外的庞大数据库如何找到你正在搜索的信息并将其发回给你？这背后的原因不仅仅是使用更快的互联网和超级计算机。一些令人着迷的搜索算法和数据结构在它背后起作用。其中一个是特里 。

Trie ，也称为数字树，有时称为基数树或前缀树 （因为它们可以通过前缀搜索），是一种搜索树 - 一种有序树数据结构，用于存储动态集或关联数组，其中键是通常是字符串它是可以轻松实现的数据结构之一。假设你有一个庞大的数百万字的数据库。你可以使用 trie 来存储这些信息，搜索这些单词的复杂性仅取决于我们搜索的单词的长度。这意味着它不依赖于我们的数据库有多大。这不是很棒吗？

假设我们有一个包含这些词的字典：

algo
algea
also
tom
to

我们希望将这个字典存储在内存中，以便我们可以轻松找到我们正在寻找的单词。其中一种方法涉及按字典顺序排序单词 - 现实生活中的词典如何存储单词。然后我们可以通过二进制搜索找到这个词。另一种方法是使用前缀树或 Trie ，简而言之。 Trie 这个词来自 Re trie val 这个词。这里， prefix 表示字符串的前缀，可以这样定义：从字符串的开头开始可以创建的所有子字符串都称为前缀。例如：‘c’，‘ca’，‘cat’都是字符串’cat’的前缀。

现在让我们回到特里。顾名思义，我们将创建一棵树。首先，我们有一个只有根的空树：

我们会插入 ‘algo’ 这个词。我们将创建一个新节点并命名这两个节点之间的边缘 ‘a’ 。从新节点开始，我们将创建另一个名为 ’l’的边，并将其与另一个节点连接。这样，我们将为 ‘g’ 和 ‘o’ 创建两个新边。请注意，我们不会在节点中存储任何信息。目前，我们只考虑从这些节点创建新边。从现在开始，让我们调用名为 ‘x’的边 - edge-x

现在我们要添加 algea 这个词。我们需要一个来自 root 的 edge-a ，我们已经拥有了它。所以我们不需要添加新的优势。同样，我们有一个从 ‘a’ 到 ’l’ 和 ’l’ 到 ‘g’ 的边缘。这意味着 ‘alg’ 已经在特里。我们只会添加 edge-e 和 edge-a 。

我们将添加 也 这个词。我们从 root 获得前缀 ‘al’ 。我们只会添加 ‘so’ 。

让我们添加 ‘汤姆’ 。这一次，我们从 root 创建了一个新的边缘，因为我们之前没有创建任何 tom 的前缀。

现在我们应该如何添加 ’to’ ？ ’to’ 完全是 ’tom’ 的前缀，所以我们不需要添加任何边缘。我们可以做的是，我们可以在某些节点中添加结束标记。我们将在那些至少完成一个单词的节点中放置结束标记。绿色圆圈表示结束标记。trie 看起来像：

你可以轻松理解我们添加结束标记的原因。我们可以确定存储在 trie 中的单词。字符将位于边缘，节点将包含结束标记。

现在你可能会问，存储这样的单词的目的是什么？比方说，你被要求在词典中找到 ‘alice’ 这个词。你将穿越特里。你将检查是否存在来自 root 的 edge-a 。然后从 ‘a’ 检查，如果有边缘 l 。在那之后，你将找不到任何 edge-i ，所以你可以得出结论，字典中不存在 alice 这个词。

如果要求你在字典中找到单词 ‘alg’ ，你将遍历 root-> a ， a-> l ， l-> g ，但最后你将找不到绿色节点。所以字典中不存在这个词。如果你搜索 tom ，你将最终进入绿色节点，这意味着该词存在于词典中。

复杂：

在 trie 中搜索单词所需的最大步骤数是我们要查找的单词的长度。复杂度为 O（长度） 。插入的复杂性是相同的。实现 trie 所需的内存量取决于实现。我们将在另一个例子中看到一个实现，我们可以在一个 trie 中存储 10 个 6 个 字符（不是单词，字母）。 ****

使用 Trie：

• 在字典中插入，删除和搜索单词。
• 查明字符串是否是另一个字符串的前缀。
• 要找出有多少个字符串有一个共同的前缀。
• 根据我们输入的前缀，建议我们手机中的联系人姓名。
• 找出两个字符串的’Longest Common Substring’。
• 使用最长的共同祖先找出两个单词的共同前缀的长度