trie和radix trie数据结构有什么区别？
trie和radix trie的数据结构是一样的吗？
如果它们是相同的，那么基数特里（AKA Patricia trie）的含义是什么？
基数树是树的压缩版本。 在每一个边缘你写一个单一的字母，而在一个PATRICIA树（或基数树），你存储整个单词。
现在，假设你有这个词hello ， hat和have 。 要将它们存储在一个trie中 ，它看起来像：
e - l - l - o / h - a - t \ v - e
你需要九个节点。 我已经把这些字母放在了节点上，但是实际上它们标记了边缘。
在基数树中，您将拥有：
* / (ello) / * - h - * -(a) - * - (t) - * \ (ve) \ *
你只需要五个节点。 在上面的图片中，节点是星号。
所以，总体而言，基数树占用的内存较less ，但实施起来较为困难。 否则两者的用例几乎相同。
我的问题是Trie数据结构和Radix Trie是否是同一件事？
总之，没有。 Trie类描述了Trie的一个特定类别，但这并不意味着所有尝试都是基数尝试。
如果它们不一样，那么什么是特里特里（又名帕特里夏特里）呢？
我假设你的意思是写在你的问题，因此我的更正。
同样，PATRICIA表示特定types的基数trie，但不是所有的基数尝试都是PATRICIA尝试。
什么是特里？
“Trie”描述适合用作关联数组的树数据结构，其中分支或边对应于键的部分 。 在这里， 部分的定义是相当模糊的，因为try的不同实现使用不同的比特长度来对应边缘。 例如，二进制特里结构在每个节点上有两个对应于0或1的边，而16路特里结构有16个边，每个结点对应于四个位（或hex数字：0x0到0xf）。
从维基百科检索到的这个图表似乎描述了至less插入了'A'，'to'，'tea'，'ted'，'ten'和'inn'
如果这个存储库存储了关键字“t”，“te”，“i”或“in”的项目，则需要在每个节点上存在额外的信息来区分具有实际值的无效节点和节点。
什么是基数树？
“基数特里”似乎描述了一种浓缩共同前缀部分的特里特里的forms，正如Ivaylo Strandjev在他的回答中所描述的那样。 考虑一下使用下面的静态分配索引键“微笑”，“微笑”，“微笑”和“微笑”的256行索引：
root['s']['m']['i']['l']['e']['\0'] = smile_item; root['s']['m']['i']['l']['e']['d']['\0'] = smiled_item; root['s']['m']['i']['l']['e']['s']['\0'] = smiles_item; root['s']['m']['i']['l']['i']['n']['g']['\0'] = smiling_item;
每个下标访问一个内部节点。 这意味着检索smile_item ，你必须访问七个节点。 八个节点访问对应于smiled_item和smiles_item ，九个对应于smiling_item 。 对于这四个项目，共有十四个节点。 但是，它们都有前四个字节（对应于前四个节点）。 通过压缩这四个字节来创build对应于['s']['m']['i']['l'] ，四个节点访问已经被优化。 这意味着更less的内存和更less的节点访问，这是一个很好的指示。 可以recursion地应用优化以减less访问不必要的后缀字节的需要。 最终，您只能比较search关键字和索引键之间的区别 。 这是一个基数线索。
root = smil_dummy; root['e'] = smile_item; root['e']['d'] = smiled_item; root['e']['s'] = smiles_item; root['i'] = smiling_item;
要检索项目，每个节点都需要一个位置。 用“微笑”和4的root["smiles"[4]]的search关键字，我们访问root["smiles"[4]] ，恰好是root['e'] 。 我们把它存储在一个名为current的variables中。 当前的位置是5，这是"smiled"和"smiles"之间的区别的位置，所以下一个访问将是root["smiles"[5]] 。 这将我们带到了smiles_item ，并且结束了我们的string。 我们的search已经结束，并且该项目已经被检索，只有三个节点访问而不是八个。
什么是PATRICIA特里？
PATRICIA trie是一个基数尝试的变体，只有n节点用于包含n项目。 在我们粗略地演示的基数上面的伪代码中，总共有五个节点： root （它是一个空节点，它不包含实际值）， root['e'] ， root['e']['d'] ， root['e']['s']和root['i'] 。 在PATRICIA里，只有四个。 我们来看看这些前缀如何通过二进制查看而有所不同，因为PATRICIA是一种二进制algorithm。
smile: 0111 0011 0110 1101 0110 1001 0110 1100 0110 0 101 0000 0000 0000 0000 smiled: 0111 0011 0110 1101 0110 1001 0110 1100 0110 0 101 0110 0100 0000 0000 smiles: 0111 0011 0110 1101 0110 1001 0110 1100 0110 0 101 0111 0011 0000 0000 smiling: 0111 0011 0110 1101 0110 1001 0110 1100 0110 1 001 0110 1110 0110 0111 ...
让我们考虑一下，节点是按照上面的顺序添加的。 smile_item是这棵树的根。 粗略的区别使它更容易被发现，位于"smile"的最后一个字节，在第36位。直到这一点，我们所有的节点都有相同的前缀。 smiled_node属于smile_node[0] 。 "smiled"和"smiles"之间的区别发生在位43，其中"smiles"具有“1”位，所以smiled_node[1]是smiles_node 。
而不是使用NULL作为分支和/或额外的内部信息来表示search何时终止，分支将链接返回到某处，因此当testing的偏移量减less而不是增加时，search结束。 下面是这样一棵树的简单图表（虽然PATRICIA实际上更像是一个循环图，而不是树，正如你将会看到的那样），它被包含在下面提到的Sedgewick的书中：
虽然PATRICIA的一些技术特性在这个过程中丢失了（也就是说，任何节点都包含一个与之前的节点相同的前缀），但是更复杂的PATRICIAalgorithm也可能涉及变长的密钥。
通过这样分支，有许多好处：每个节点都包含一个值。 包括根。 结果，代码的长度和复杂度变得非常短，实际上可能要快一些。 至less一个分支和至多k分支（其中k是search关键字中的位数）被跟踪以find一个项目。 节点很小 ，因为它们每个只存储两个分支，这使得它们非常适合caching局部性优化。 这些属性使得PATRICIA成为我最喜欢的algorithm。
为了减轻我即将发生的关节炎的严重程度，我将在这里缩短这个描述，但是如果你想了解更多关于PATRICIA的信息，你可以参考Donald Knuth的“计算机程序devise艺术第3卷” ，或Sedgewick的“你最喜欢的语言，1-4部分的algorithm”。
TRIE：
我们可以有一个searchscheme，而不是比较整个search关键字与所有现有的关键字（如哈希scheme），我们也可以比较search关键字的每个字符。 按照这个想法，我们可以build立一个结构（如下图所示），它有三个现有的键 – “ 爸爸 ”，“ 民主 ”和“ 驾驶室 ”。
[root] ...// | \\... | \ cd | \ [*] [*] ...//|\. ./|\\... Fig-I aa / / [*] [*] ...//|\.. ../|\\... / / \ B bd / / \ [] [] [] (cab) (dab) (dad)
这实际上是一个具有内部节点的M-tree，表示为[*]，叶节点表示为[]。 这个结构被称为trie 。 在每个节点处的分支决定可以保持等于字母的唯一符号的数量，例如R.对于小写英文字母az，R = 26; 对于扩展ASCII字母，R = 256和二进制数字/stringR = 2。
紧凑型TRIE：
通常情况下， 树中的节点使用大小= R的数组，因此当每个节点的边数较less时会导致内存浪费。 为了回避记忆，提出了各种build议。 基于这些变体， trie也被称为“ compact trie ”和“ compressed trie ”。 尽pipe一致的命名是罕见的，但是当节点具有单个边缘时，通过对所有边进行分组来形成紧凑型特里结构的最常见版本。 使用这个概念，具有键“爸爸”，“爸爸”和“驾驶室”的上述（图1）可以采取下面的forms。
[root] ...// | \\... | \ cab da | \ [ ] [*] Fig-II ./|\\... | \ bd | \ [] []
请注意，“c”，“a”和“b”中的每一个对于其对应的父节点都是唯一边缘，因此它们被合并成单个边“cab”。 类似地，“d”和“a”被合并成标记为“da”的单个边缘。
Radix Trie：
基数在math中意味着数字系统的基数 ，它基本上表示在该系统中表示任何数字所需的唯一符号的数量。 例如，十进制是十进制，二进制是二进制。 使用相似的概念，当我们有兴趣通过底层代表系统的唯一符号的数量表征数据结构或algorithm时，我们用“基数”这个术语来标记这个概念。 例如，某些sortingalgorithm的“基数sorting”。 在同一行逻辑中，所有特征（例如深度，内存需求，search未命中/命中运行时间等）的变体都依赖于基本字母的基数，我们可以称它们为基数“trie”。 例如，一个非压缩的以及一个压缩的trie当使用字母az时，我们可以称它为基数。 任何只使用两个符号（传统上'0'和'1'）的树可以被称为基2 树 。 然而，不知何故，许多文献仅限于使用“Trie”这个术语，而仅仅是用于压缩的Trie 。
帕特里克的前奏：树/特里：
有趣的是，即使string作为键也可以用二进制字母表示。 如果我们假定ASCII编码，那么可以通过按顺序写入每个字符的二进制表示，如“ 01100100 01100001 01100100 ”，通过写入“d”，“a”和'd'依次。 使用这个概念，可以形成一个三元组 （基数二）。 下面我们用一个简单的假设来描述这个概念，即字母“a”，“b”，“c”和“d”来自一个更小的字母而不是ASCII。
如图所示，为了便于描述，我们假定一个只有4个字母{a，b，c，d}的字母表，其相应的二进制表示为“00”，“01”，“10”和“11”。 这样，我们的string键“dad”，“dab”和“cab”分别变为“110011”，“110001”和“100001”。 这将如图三所示（比特从左到右读取，就像从左到右读取string一样）。
[root] \1 \ [*] 0/ \1 / \ [*] [*] 0/ / / /0 [*] [*] 0/ / / /0 [*] [*] 0/ 0/ \1 Fig-III / / \ [*] [*] [*] \1 \1 \1 \ \ \ [] [] [] (cab) (dab) (dad)
PATRICIA Trie /树：
如果我们使用单边压缩来压缩上面的二进制树 （图三），它将比上面显示的less得多的节点，但是节点仍然会多于它所包含的密钥的数目3。 唐纳德·R·莫里森 （DonaldR.Morrison）在1968年发现了一种创新的方法来使用二进制字典来描述只有N个节点的N个密钥，他命名了这个数据结构PATRICIA 。 他的结构基本上摆脱了单边（单向分支）; 在这样做的同时，他也摆脱了两种节点 – 内层节点（不描述任何关键字）和叶节点（描述关键字）的概念。 与上面所述的压缩逻辑不同，他的特里使用了一个不同的概念，其中每个节点都包括一个要跳过的密钥的多less位以作出分支决定的指示。 他的PATRICIA特有的另一个特点是它不存储密钥 – 这意味着这样的数据结构将不适合回答问题，例如列出与给定前缀匹配的所有密钥 ，但是有利于查找密钥是否存在或不在于此 。 尽pipe如此，“帕特里夏树”或帕特里夏·特里这个词从那时起就被用于许多不同但相似的意义上，如表示紧密的结构[NIST]，或者指示基数为2的基数结构[如微妙在WIKI的方式]等等。
这可能不是一个Radix Trie：
三元searchTrie （又称三元search树）通常缩写为TST是一种数据结构（由J.Bentley和R.Sedgewick提出 ），它看起来与具有三路分支的三元组非常相似。 对于这样的树，每个节点都有一个特征字母“x”，这样分支决定就是由一个键的字符是小于，等于还是大于'x'来驱动的。 由于这个固定的3路分支function，它为trie提供了一个高效的内存select，特别是当R（基数）非常大时，例如Unicode字母。 有趣的是，与（R-way） trie不同，TST没有受到R影响的特性。例如，对于R-way Trie，TST的search未命中是ln（N）而不是log R （N） 。 TST的内存要求，不像R-way trie，也不是R的函数。 所以我们应该小心地把TST称为基数树。 我个人认为，我们不应该把它称为基数（radix-trie），因为它的特征没有一个（据我所知）受其基本字母R的影响。
