是特里和基数特里数据结构是一回事吗？
如果它们是相同的，那么什么是基数特里（AKA帕特里夏线索）的含义是什么？
Answer 1:
基数树是特里结构的一个压缩版本。 在一个线索，在每条边上你写一个字母，而在Patricia树（或基数树）您存储整个单词。
现在，假设你有话hello ， hat和have 。 将它们存储在一个线索 ，它看起来像：
e - l - l - o
/
h - a - t
\
v - e
而你需要9个节点。 我已经把字母中的节点，但实际上他们标示的边缘。
在基数树，你将有：
*
/
(ello)
/
* - h - * -(a) - * - (t) - *
\
(ve)
\
*
而你只需要五个节点。 另外，在上述节点中的图象是星号。
因此，总体而言，基数树花费更少的内存 ，但是这是很难实现的。 否则，两者的使用情况是大同小异的。
Answer 2:
我的问题是特里数据结构和基数特里是否是一回事？
总之，没有。 类别板蓝根特里介绍特里结构的一个特殊类别，但是，这并不意味着所有的尝试都是基数尝试。
如果他们[不]相同的，那么什么是板蓝根特里（又名帕特里夏特里）的含义是什么？
我假设你的意思是写不是你的问题，因此我的修正。
类似地，PATRICIA表示特定类型的基数特里结构的，但不是所有的基数尝试是试图PATRICIA。
什么是线索？
“Trie树”描述适合用作一个关联数组，其中枝条或边缘对应于键的部分树数据结构。 份的定义是相当含糊，在这里，因为尝试不同的实现方式使用不同的比特长度，以对应于边缘。 例如，一个二进制特里结构具有每对应于0或1节点的两个边缘，而一个16路特里结构具有每节点16层的边缘对应于四个比特（或十六进制数字：通过对0xf为0x0）。
该图中，维基百科检索，似乎描绘了具有（至少）键“A”字典树，“到”，“茶”，“泰德”，“10”和“旅馆”插入：
如果此字典树是存储用于键“T”，“TE”项，“i”或“在”有将需要存在于每个节点无参节点和节点与实际值之间进行区分的额外信息。
什么是基数线索？
“板蓝根特里”似乎来形容特里是凝聚共同的前缀部分的形式，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 。 对于这四个项目，总共有14个节点。 它们都具有前四个字节中常见（对应于第一四个节点），但是。 通过冷凝那些四个字节来创建root对应于['s']['m']['i']['l'] ，四个节点访问已被优化了。 这意味着更少的内存和更少的节点的访问，这是一个很好的指示。 优化可以递归应用，以减少需要访问不必要的后缀字节。 最终，你会得到一个点，你只在比较的线索索引的位置搜索键和索引键之间的差异 。 这是一个基数线索。
root = smil_dummy;
root['e'] = smile_item;
root['e']['d'] = smiled_item;
root['e']['s'] = smiles_item;
root['i'] = smiling_item;
要检索的项目，每个节点都需要一个位置。 用“微笑”的检索关键字和一个root.position 4，我们访问root["smiles"[4]]这恰好是root['e'] 我们这些信息存储在一个名为可变current 。 current.position是5，其是之间的差的位置"smiled"和"smiles" ，因此下一个访问将是root["smiles"[5]] 这给我们带来smiles_item ，和我们的字符串的结束。 我们的搜索已经结束，该项目已被检索到，只有三个节点接入的不是8。
什么是PATRICIA线索？
一个PATRICIA特里是基数的尝试应该有的只是永远的变体n使用的节点包含n项目。 在我们的粗略表明基数线索上述伪代码中，总共有五个节点： root （这是一个无参节点;它不包含任何实际值）， root['e'] root['e']['d'] root['e']['s']和root['i'] 。 在PATRICIA特里应该只能为四种。 让我们来看看如何将这些前缀可能是由二进制看着他们不同，因为PATRICIA是一个二进制算法。
smile: 0111 0011 0110 1101 0110 1001 0110 1100 0110 0101 0000 0000 0000 0000
smiled: 0111 0011 0110 1101 0110 1001 0110 1100 0110 0101 0110 0100 0000 0000
smiles: 0111 0011 0110 1101 0110 1001 0110 1100 0110 0101 0111 0011 0000 0000
smiling: 0111 0011 0110 1101 0110 1001 0110 1100 0110 1001 0110 1110 0110 0111 ...
让我们考虑的节点在它们上面显示的顺序添加。 smile_item是这棵树的根。 所不同的，加粗，使其稍微容易被发现，是在最后一个字节"smile" ，在36位直到此时，我们所有的节点都具有相同的前缀。 smiled_node属于在smile_node[0] 之间的差"smiled"和"smiles"发生在位43，在那里"smiles"具有“1”比特，所以smiled_node[1]是smiles_node 。
而不是使用NULL作为分支机构和/或额外的内部信息，表示当搜索终止，树枝链接回了树的地方，所以搜索结束时偏移测试减少而不是增加。 这里有这样一棵树的一个简单的示意图（虽然PATRICIA真的更多的是一种循环图，比一棵树，你会看到），其中包括在下文提到的塞奇威克的书：
涉及变体长度的密钥的更复杂的Patricia算法所是可能的，尽管一些PATRICIA的技术特性的过程中（即，任何节点包含与在它之前的节点的公共前缀）丢失：
通过分支就是这样，有很多好处：每个节点都包含一个值。 包括所述根。 其结果是，该代码的长度和复杂度变短了很多，而实际上他快一点。 至少一个分支和至多k分支（其中k是在检索关键字的比特数）后面跟着以定位项目。 节点是微小的 ，因为它们存储每个只有两个分支，这使得它们非常适合于高速缓存局部性优化。 这些特性使得PATRICIA我最喜欢的算法至今...
我要在这里短切本说明书中，为了减少我即将关节炎的严重程度，但如果你想知道更多关于PATRICIA你可以咨询书，例如高德纳“计算机程序设计艺术，第3卷” ，或任何“在{你最喜欢的语言}算法，部分1-4”的塞奇威克的。
Answer 3:
TRIE：
我们可以有一个搜索方案，其中，代替比较现有的所有键（如哈希方案）的整体搜索键，我们也可以比较搜索键的每个字符。 依照该思路，我们可以建立一个结构（如下图所示），它有三个现有的密钥- “ 爸爸 ”，“DAB”和” 驾驶室 ”。
[root]
...// | \\...
| \
c d
| \
[*] [*]
...//|\. ./|\\... Fig-I
a a
/ /
[*] [*]
...//|\.. ../|\\...
/ / \
B b d
/ / \
[] [] []
(cab) (dab) (dad)
这实质上是一个M进制树具有内部节点，表示为[*]和叶节点，表示为[]。 这种结构被称为线索 。 每个节点的分支决定可以保持等于字母表中的独特码元的数目，说R.对于小写英文字母AZ，R = 26; 用于扩展的ASCII字母，R = 256和二进制数字/串R = 2。
紧凑型TRIE：
典型地，在一个线索节点使用具有大小= R的阵列，并且因此引起记忆的废物时每个节点具有较少的边缘。 为了规避内存的关注，提出了各种建议提出。 基于这些变化线索也被命名为“ 紧凑型线索 ”和“ 压缩的线索 ”。 虽然一致的命名是罕见的，紧凑的特里结构的一个最常见的版本是把所有边缘节点时有一个边缘形成。 使用此概念，与键“爸爸”，“轻拍”，和“CAB”以上（图-I） 特里结构可以采取以下的形式。
[root]
...// | \\...
| \
cab da
| \
[ ] [*] Fig-II
./|\\...
| \
b d
| \
[] []
请注意，每个“C”，“A”，和“b”是其相应父节点唯一边缘，并且因此，它们被聚结到一个单一的边缘“CAB”。 类似地，“D”和”被合并到标记为‘大’单个边缘。
板蓝根特里：
术语基数 ，在数学，指数系统的基站，并且它基本上表示以表示在该系统中任何数量的所需的唯一的符号的数目。 例如，十进制系统芩十个，和二进制系统芩两项。 使用类似的概念，当我们感兴趣的表征数据结构或底层表象系统的独特符号的数量的算法，我们标记的“基数”一词的概念。 例如，“基数排序”为某些排序算法。 在同一行的逻辑， 特里其特性（如深度，内存需求，搜索小姐/打运行时间等）取决于标的字母的基数的所有变体，我们可以称他们为基数“特里的”。 例如，未压实和压实的线索时使用字母AZ，我们可以称之为一个基数26 线索 。 仅使用两个符号的任何线索（传统“0”和“1”）可以被称为基数2 线索 。 然而，不知何故许多文献限制使用的术语“板蓝根特里”的只为压实线索 。
前奏Patricia树/特里：
这将是有趣的发现，即使字符串作为键可以使用二进制字母表来表示。 如果我们假设ASCII编码，然后一键“爸爸”，可以以二进制形式写在序列中的每个字符的二进制表示写，说为“01100100 01100001 01100100”写“d”，“A”的二进制形式， 'D' 顺序。 使用这个概念，可以形成特里 （含麦冬二）。 下面我们用一个简单的假设，即字母“A”，“B”，“C”，and'd”是从一个较小的字母，而不是ASCII描述这个概念。
注意图-III为：如所提到的，为了使描述简单，我们假定只用4个字母{A，B，C，d}和其相应的二进制表示为“00”的字母，“01”，“10”和“11”分别。 有了这个，我们的字符串键“爸爸”，“DAB”和“出租车”，成为“110011”，“110001”，及“100001”。 造成这种情况的线索将被如图-III在如下所示（位从向左阅读向右就像琴弦从左读取到右）。
[root]
\1
\
[*]
0/ \1
/ \
[*] [*]
0/ /
/ /0
[*] [*]
0/ /
/ /0
[*] [*]
0/ 0/ \1 Fig-III
/ / \
[*] [*] [*]
\1 \1 \1
\ \ \
[] [] []
(cab) (dab) (dad)
PATRICIA特里/树：
如果我们使用单刃压实压实上述二进制特里结构 （图-III），它必须比上述少得多的节点，然而，节点仍然会比3以上，键的数量它包含。 唐纳德R.莫里森发现（1968年），以使用二进制特里描绘仅使用N个节点N个按键中一种创新的方式和他命名的这个数据结构PATRICIA。 他的线索结构基本摆脱了单一的边缘（单程分支）的; 并在这样做，他也摆脱了两种节点的概念 - 内部节点（即不描绘任何键）和叶节点（即描绘键）。 不同于压实逻辑上面所解释的，他的特里结构使用不同的概念，其中每个节点包括如何的密钥的许多比特被跳过用于制备支化的决定的指示。 然而，他PATRICIA特里的另一个特点是，它并没有存储密钥-这意味着这样的数据结构将不适合回答这样的问题， 列出所有符合给定前缀，所有的钥匙 ，但对于查找是否存在的关键或没有线索 。 尽管如此，术语Patricia树或帕特里夏Trie树已经，从那以后，已经在许多不同但相似的感官，如所使用的，以指示一个紧凑的线索[NIST]，或者以指示与基数2 [如在微妙指示的基数线索在WIKI方式]等。
特里这可能不是一个基数特里：
三元搜索特里 （又名三元搜索树），通常缩写为TST是看起来非常相似，特里结构三路分支的数据结构（由J.宾利和R.塞奇威克提议）。 对于这样的树中，每个节点具有这样的特性字母“X”，使得分支决定通过键的字符是否大于“x”的小于，等于或大于驱动。 由于这个固定的3路分支的特征，它提供了线索的存储器高效的替代方案中，特别是当R（基数）是非常大的，例如对于Unicode字母。 有趣的是，TST，不同于（R向） 线索 ，不具有由R.影响例如它的特点，为TST搜索未命中是LN（N），而不是对数R（N），用于R-方式Trie树。 TST的存储器要求，不同于R-方式特里结构 不是 R的函数，以及。 因此，我们应该小心调用TST基数线索。 我个人认为我们不应该把它因为没有一个基数特里（据我所知），其特点是由基数，R，其基本字母的影响。
文章来源: What is the difference between trie and radix trie data structures?
{var%20f='http://v.t.sina.com.cn/share/share.php?appkey=1515056452',u=z||d.location,p=['&url=',e(u),'&title=',e(t||d.title),'&source=',e(r),'&sourceUrl=',e(l),'&content=',c||'gb2312','&pic=',e(p||'')].join('');function%20a(){if(!window.open([f,p].join(''),'mb',['toolbar=0,status=0,resizable=1,width=440,height=430,left=',(s.width-440)/2,',top=',(s.height-430)/2].join('')))u.href=[f,p].join('');};if(/Firefox/.test(navigator.userAgent))setTimeout(a,0);else%20a();})(screen,document,encodeURIComponent,'','','https://i.stack.imgur.com/EmJmU.png', '推荐 一夜七次 的文章《是什么线索和基数特里数据结构之间的区别？(What is the difference betwee》','https://www.manongdao.com/article-1144960.html','页面编码gb2312|utf-8默认gb2312'));){kind=link}