试

try(也称为基数树或前缀树)也是如此基于树的通常用于存储的数据结构关联数组钥匙通常在哪里字符串．因为它们也实现了关联数组，所以try经常被用来比较哈希表．在决定是使用try表还是使用哈希表时，有一些重要的利弊需要考虑，通常可以归结为如何将使用关联数组。

尝试是有趣的原因有很多。首先，树中的节点不存储键。相反，它们各自存储钥匙的一部分。从根节点向下遍历到叶节点允许您随着进度构建密钥。此外，不需要在每个节点上都有一个值。事实上，值通常只与叶节点相关联。构建密钥对于特定的应用程序非常有用，尤其是自动完成。

例如，下面是一个图形，它是一个包含以下关联数组的try的表示。记住关联数组是抽象数据类型，所以try是实现ADT的一种方法。

地图={32岁的“猿”:“球”:2,“原子”:16日,“吃”:18岁的“诱饵”:5}

一个单词查找树

正如您所看到的，密钥是在从根到叶的过程中构建的。“猿”这个词是通过遍历“a”边、“p”边和“e”边生成的。当我们到达叶节点时，我们可以提取它的值，也就是32。

比起它们的对手，尝试有很多优势哈希表．它们用于许多字符串搜索应用程序，如自动完成、文本搜索和前缀匹配。根树，是IP路由中常用的一种尝试。

与其他基于树的数据结构一样，try由一组通过指针连接的节点组成。这些指针指示节点之间的父子关系。在树上，父母在孩子的上方。通常，树的根节点是一个“空”节点，因此它可以指向try用来存储的字母表的所有成员。

与其他基于树的数据结构不同，例如AVL树，尝试不一定是平衡的。它完全依赖于树的内容。

try中的节点可以保存字母表中的单个成员，也可以保存到目前为止的整个单词。例如，树可以像上图那样，也可以像这样:

另一种尝试^[1]

try常被用作替换哈希表．为此，不存在冲突，因此try的最坏情况性能要比实现糟糕的哈希表好。另外，不需要哈希函数。此外，尝试有能力排序他们的信息，例如字母顺序。这在某些情况下是有用的应用程序．

决定如何设计尝试与尝试的应用有很大的关系。例如，如果您想使用try实现英语自动完成，它需要存储英语语言中的每个单词(外加一些俚语术语)。如果指针从根开始指向一个包含7个连续z节点的字符串是没有意义的。没有连续7个z的单词。因此，这将是对空间(和计算时间)的巨大浪费。如果你的整棵树是英语中最长的单词的高度，这就特别浪费。最长的非技术术语是反分离主义，有27个字。在这种情况下，不平衡的数据结构要高效得多!平衡树是指从根到叶的所有路径长度相差最多为1的树，就像AAVL树．不平衡的树没有这样的限制。不平衡的树会剪掉不必要的字符串，比如连续的7个z。

一个人在试验中使用的语言是非常重要的。例如，虽然存储字符串(人类语言)是一种常见的尝试应用，但也可以存储位序列。对于英语语言，每个节点最多可以有26个子节点。然而，使用比特将可能的子节点数量限制为2。此外，程序员可以通过压缩来限制他们语言的字母表。任何可以用 $n$字节也可以用 $2 n$4比特单元。当使用这种压缩时，在最坏的情况下查找可以访问多达两倍的节点，但存储需求减少了8倍。

try的时间复杂度很大程度上取决于try中存储的语言的表示。如上所述早些时候，对语言的字母表示的微小更改可能会对存储和操作时间复杂度产生很大的影响。

这是最坏情况下的情况 $米$最长单词的长度是多少 $n$是try中的单词数。 $一个$就是你要找的单词的长度。请注意，要将这些时间更改为平均或最佳情况，只需交换 $米$分别为平均字长或最短字长。

的复杂性决定了每个操作查找操作。从创建try到稍后搜索它，再到删除元素，都需要执行 $米$对每个 $n$单词。

参见:大O符号．

这些操作的复杂性在哈希表中反映为以下值。使用哈希表查找整个单词更容易。但是，try允许您通过前缀查找单词，这是散列表不能做到的，因为它们的键不是分开的。

下面的python代码是一个示例面向对象的接近试炼。它具有基本的功能，并使用英语作为它的字母表。

12 34 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51

类节点：def__init__（自我)：自我．关键＝没有一个自我．价值＝没有一个自我．孩子们＝{}类单词查找树：def__init__（自我)：自我．根＝节点（）def插入（自我，词，价值)：currentWord＝词currentNode＝自我．根而len（currentWord）>0：如果currentWord［0］在currentNode．孩子们：currentNode＝currentNode．孩子们［currentWord［0]]currentWord＝currentWord［1:]其他的：newNode＝节点（）newNode．关键＝currentWord［0］如果len（currentWord）= =1：newNode．价值＝价值currentNode．孩子们［currentWord［0]]＝newNodecurrentNode＝newNodecurrentWord＝currentWord［1:]def查找（自我，词)：currentWord＝词currentNode＝自我．根而len（currentWord）>0：如果currentWord［0］在currentNode．孩子们：currentNode＝currentNode．孩子们［currentWord［0]]currentWord＝currentWord［1:]其他的：返回“不是在单词查找树”如果currentNode．价值= =没有一个：返回“没有”返回currentNode．价值defprintAllNodes（自我)：节点＝［自我．根］而len（节点）>0：为信在节点［0］．孩子们：节点．附加（节点［0］．孩子们［信]）打印节点．流行（0）．关键defmakeTrie（单词)：单词查找树＝单词查找树（）为词，价值在单词．项目():单词查找树．插入（词，价值）返回单词查找树

下面是它的实际操作。

12 3 4 5 6 7 8 9 10 11 12 13 14 15

>>>单词查找树＝makeTrie({“你好”：5，“帽子”：7，“她”：1})>>>单词查找树．查找（“不”）“不是在单词查找树”>>>单词查找树．查找（“你好”）5>>>单词查找树．printAllNodes（）没有一个h一个etrllo

根节点打印出的键为没有一个,如预期。注意，只有一个节点的键为“h”？这是因为这两个“你好”而且“帽子”使用该节点。该节点充当所有以字母“h”开头的单词的根。

尝试有很多很酷的应用。你曾经在手机上使用过自动补全功能吗?这可能是最常见的应用。一旦输入了一个字母，潜在单词的树就大大减少了，使程序能够轻松枚举可能的字符串类型。

如果您只想存储单词，那么使用状态机可能会更容易一些。但是，try可以为每个单词存储额外的信息。例如，try可以存储一个单词的流行程度。这就是为什么当你输入“yes”时，建议在“大喊”之前先输入“yes”。

尝试对于近似也是有用的匹配算法，就像拼写检查中使用的那样。与拼写正确的单词相比，拼写稍有错误的单词从树的根处的路径相似。如果对try进行了某些修改，比如分支合并，则尤其如此。

字符串匹配是另一个用例，尝试和近似算法是有用的。最长后缀或前缀匹配使用这些方法。

try也可以用于排序．使用try来完成此操作类似于基数排序．树的预顺序遍历将产生递增顺序的输出，从而允许排序。

1. Bazookaj B。单词查找树．检索日期:2016年6月22日https://en.wikipedia.org/wiki/Trie