试

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

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

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

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

一个单词查找树

如您所见，密钥是在您从根向下到叶子的过程中建立起来的。单词“猿”是通过横过“a”边、“p”边和“e”边构成的。当我们到达一个叶节点时，我们可以提取它的值，即32。

与同类产品相比，试品有许多优点哈希表．它们用于许多字符串搜索应用程序，如自动完成、文本搜索和前缀匹配。根树是一种trie，常用于IP路由中。

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

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

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

另一种尝试^[1]

try常被用来代替哈希表．为此，没有冲突，所以trie的最差性能要比实现糟糕的哈希表好。另外，不需要哈希函数。此外，用户还可以按字母顺序对信息进行排序。这在某些情况下是有用的应用程序．

决定如何设计trie与trie的应用程序有很大关系。例如，如果您想使用trie实现英语自动补全，它需要存储英语语言中的每个单词(加上一些俚语)。让指针从根结点指向由7个连续的'z'节点组成的字符串是没有意义的。没有一个单词是连续七个z的。因此，这将是对空间(和计算时间)的巨大浪费。如果你的整棵树是英语中最长单词的高度，那么这就特别浪费了。最长的非专业术语是Antidisestablishmentarianism，有27个字。在这种情况下，不平衡的数据结构效率更高!平衡树是指从根结点到所有叶结点的所有路径长度不超过1的树，就像anAVL树．不平衡树没有这样的限制。不平衡树会剪掉不必要的字符串，比如7个连续的z。

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

进行trie的时间复杂度很大程度上取决于trie中存储的语言的表示形式。如上所述早些时候在美国，对一种语言的字母表示的微小改变可能会对存储和操作时间复杂度产生很大影响。

这是最坏的情况 $米$最长的单词的长度，和 $n$是单词的数量。 $一个$是您要搜索的单词的长度。请注意，要将这些时间更改为平均值或最佳情况，只需进行换出 $米$分别为单词的平均长度或最短单词的长度。

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

参见:大O符号．

这些操作的复杂性通过以下值反映在哈希表中。使用哈希表查找整个单词更容易。然而，tries允许您通过前缀查找单词，而哈希表无法做到这一点，因为它们的键没有分割。

下面的python代码是面向对象的尝试的方法。它有基本的功能，并使用英语作为其字母。

12 34 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 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})>>>单词查找树．查找（“不”）'Not in try '>>>单词查找树．查找（“你好”）5>>>单词查找树．printAllNodes（）没有一个h一个etrllo

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

try有很多很酷的应用。你在手机上用过自动完成功能吗?这可能是try最常见的应用。一旦你输入了一个字母，潜在的单词树就会大大减少，使程序能够轻松地列举出可能的字符串类型。

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

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

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

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

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