1.概述

在本教程中,我们将讨论trie数据结构,也称为前缀树。我们将简要介绍基础知识,然后了解如何实现最重要的特性:插入、查找和前缀搜索。

2.什么是尝试?

尝试树或前缀树是一种特殊的搜索树,其中节点通常用字符串作为键。

try可用于实现集合和关联数组等数据结构,但当我们需要执行有序遍历或高效搜索以特定前缀开始的键时,它们才真正有用。

由于这个原因,它们经常被用于实现像自动完成这样的功能。

3.单词查找树结构

在trie的基本实现中,每个节点包含单个字符和指向其子节点的指针列表。节点的键不是显式存储的:相反,我们可以通过计算从根到节点的路径来派生它。

下面是尝试的样子:

为了区分树中哪些节点表示有效键,使用了一个布尔标志。此外,如果我们使用try来实现关联数组数据结构,节点可以包含指向任意数据的指针。

图中显示了一个尝试存储键“geek”,“genius”,“gene”和“genetic”,其中突出显示的节点表示有效键。通过构造,所有叶节点都是有效的键,但是对于那些不是叶节点的,我们需要将布尔标志设置为真正的

4.在Trie中插入一个元素

要将一个元素插入到trie中,我们需要从根节点开始并遍历树,只有在缺少节点时才创建节点。当我们创建了所有必要的节点后,我们将布尔标志设置为真正的最后一个。

例如,如果单词“gene”已经包含在树中,而我们现在插入单词“genetic”,我们将:

  1. 遵循“基因”路径
  2. 为“t”、“i”和“c”创建所需的额外节点
  3. 将最后一个“c”节点标记为有效键

相反,如果“基因”这个词已经出现在这棵树上,现在我们插入了“基因”这个词,我们不需要向树中添加任何新节点。

唯一要执行的操作是将结束节点标记为有效键:

呈现由QuickLaTeX.com

5.查找

查找用于查看树中是否包含特定的键,如果我们正在实现关联数组,则返回与键关联的数据。

让我们看看查找算法:

呈现由QuickLaTeX.com

这和插入算法很相似,但这一次,当我们找到一个缺失的节点时,我们就知道我们要找的值不存在。如果迭代已经完成,这意味着我们已经找到了从根到节点的匹配路径,我们只需要检查它是否是一个有效的键。

注意,在插入和查找算法中,我们不用遍历树本身,比如,深度优先广度优先搜索。不需要遍历,因为我们必须遵循的路径是在输入本身中提供的。

6.前缀搜索

我们已经学过了前缀树的基本运算。现在是时候看看它们的优势了,也就是说,从词汇表中检索具有给定前缀的所有单词。

为此,我们将:

  1. 找出前缀P在树中的路径,从根开始
  2. 从路径“L”的最后一个节点,计算“L”的所有后代,它们是有效的键
  3. 返回找到的节点

以下是实际情况:

呈现由QuickLaTeX.com

7.结论

在本文中,我们了解了如何实现前缀树数据结构。具体来说,我们学习了如何实现基本的插入和查找操作以及前缀搜索功能。

对这篇文章的评论关闭!