本文已使用 Google Cloud Translation API 自动翻译。
某些文档最好以原文阅读。
特里树,也称为数字树,有时也称为基数树或前缀树(因为它们可以通过前缀搜索),是一种有序树数据结构,用于存储动态集或关联数组,其中键通常是字符串。与二叉搜索树不同,树中没有节点存储与该节点关联的键;相反,它在树中的位置定义了与其关联的键。一个节点的所有后代都有一个与该节点关联的字符串的公共前缀,并且根与空字符串关联。值不一定与每个节点相关联。相反,值往往与叶子相关联,并且与一些与感兴趣的键相对应的内部节点相关联。
为了简单起见,我们将在本文中假设键是单个字符。更现实的假设是键是字符串,但即使是这种更一般的情况也可以通过将字符串中的字符视为一系列击键来简化为单字符情况。
trie 可以看作是一棵树,它有一个非常特殊的性质,即从根到叶子的所有路径都具有相同的长度,并且在路径上的每个节点处,这个长度等于树中节点的深度。树。换句话说,trie 是一棵树,其中所有叶子都在同一层。
树的每个节点都标有一个字母。从根到叶子的路径对应一个词,路径上每个节点的标签就是组成这个词的字母。例如,在上图中,从根到标有字母“c”的节点的路径对应于单词“car”。
trie 算法背后的基本思想是将要搜索的字符串存储在一个 trie 数据结构中,然后在 trie 中搜索所需的字符串。
搜索算法从 trie 的根开始,在每个节点检查节点上的标签是否与要搜索的字符串的下一个字母匹配。如果匹配,则移动到 trie 中的下一个节点(即当前节点的子节点);如果没有匹配项,它将移动到树中的下一个节点(即当前节点的兄弟节点)。如果搜索到达叶节点但未找到匹配项,则该字符串不存在于 trie 中。
例如,考虑上图中所示的 trie,假设我们要搜索字符串“car”。搜索算法从标有字母“a”的根节点开始。由于这与字符串的第一个字母匹配,因此它会移动到标有字母“c”的子节点。由于这也与字符串的第二个字母匹配,因此它会移动到标有字母“a”的子节点。由于这与字符串的第三个字母不匹配,因此它移动到下一个节点,该节点标有字母“r”。由于这也不匹配,它会移动到下一个节点,该节点标有字母“b”。由于没有更多节点,搜索终止,我们得出结论,该字符串不存在于 trie 中。
插入算法与搜索算法类似,不同之处在于当它到达与要插入的字符串的下一个字母不匹配的节点时,它会创建一个带有下一个字母标签的新节点并将其作为子节点插入当前节点。
例如,考虑上图中所示的 trie,假设我们要插入字符串“cat”。插入算法从标有字母“a”的根节点开始。由于这与字符串的第一个字母匹配,因此它会移动到标有字母“c”的子节点。由于这也与字符串的第二个字母匹配,因此它会移动到标有字母“a”的子节点。由于这与字符串的第三个字母不匹配,因此它创建了一个带有标签“t”的新节点并将其作为当前节点的子节点插入。
删除算法与插入算法类似,只是当到达一个与要删除字符串的下一个字母不匹配的节点时,删除该节点及其所有后代。
例如,考虑上图中所示的 trie,假设我们要删除字符串“cat”。删除算法从标有字母“a”的根节点开始。由于这与字符串的第一个字母匹配,因此它会移动到标有字母“c”的子节点。由于这也与字符串的第二个字母匹配,因此它会移动到标有字母“a”的子节点。由于这与字符串的第三个字母不匹配,因此它会删除该节点及其所有后代。
trie 数据结构可以使用链表或数组来实现。
链表是一种由一组节点组成的数据结构,每个节点都包含对列表中下一个节点的引用。
列表中的每个节点包含两个字段:
列表中的第一个节点称为头节点,列表中的最后一个节点称为尾节点。
trie 的链表实现非常简单。要搜索字符串,我们从头节点开始,对于字符串中的每个字符,我们都遵循对下一个节点的引用,直到到达尾节点。如果该字符串不存在于 trie 中,则搜索将在到达字符串末尾之前到达尾节点。
要插入一个字符串,我们从头节点开始,对于字符串中的每个字符,我们都遵循对下一个节点的引用,直到我们到达尾节点。如果该字符串不存在于 trie 中,则插入将在到达字符串末尾之前到达尾节点,此时它将插入一个带有下一个字符标签的新节点并更新该节点的引用尾节点指向新节点。
要删除一个字符串,我们从头节点开始,对于字符串中的每个字符,我们遵循对下一个节点的引用,直到我们到达尾节点。如果字符串不存在于 trie 中,则删除将在到达字符串末尾之前到达尾节点。如果该字符串存在于 trie 中,则删除将到达该字符串的末尾,此时它将删除该节点及其所有后代。
数组是一种数据结构,由一组元素组成,每个元素都由一个索引标识。
在 trie 的数组实现中,trie 中的每个节点都由一个大小为 26 的数组表示,其中数组的每个元素都是对 trie 中下一个节点的引用。该数组由字母表中的字符索引,因此字符“a”的索引为 0,字符“b”的索引为 1,依此类推。
要搜索字符串,我们从根节点开始,对于字符串中的每个字符,我们遵循对下一个节点的引用。如果字符串不存在于 trie 中,则搜索将在到达字符串末尾之前到达空节点。
要插入一个字符串,我们从根节点开始,对于字符串中的每个字符,我们遵循对下一个节点的引用。如果该字符串不存在于 trie 中,则插入将在到达字符串末尾之前到达一个空节点,此时它将插入一个新节点并更新该节点的引用。
要删除一个字符串,我们从根节点开始,对于字符串中的每个字符,我们遵循对下一个节点的引用。如果字符串不存在于 trie 中,则删除将在到达字符串末尾之前到达空节点。如果该字符串存在于 trie 中,则删除将到达该字符串的末尾,此时它将删除该节点及其所有后代。
trie 数据结构用于许多应用程序,例如拼写检查器、文字游戏和数据压缩。
拼写检查器应用程序使用 trie 来存储单词字典,搜索算法用于检查给定单词是否在字典中。
文字游戏应用程序使用 trie 来存储游戏中的单词,并使用搜索算法来查找可以由一组给定字母组成的所有单词。
数据压缩应用程序使用 trie 来存储单词字典,搜索算法用于查找字典中作为给定字符串前缀的最长单词。然后使用最长单词的长度对字符串进行编码。
1、使用链表实现trie数据结构。
2.使用数组实现trie数据结构。
使用trie数据结构存储单词字典,并实现一个拼写检查器应用程序,使用搜索算法检查给定单词是否在字典中。
使用trie数据结构存储文字游戏中的单词,实现搜索算法,找出给定的一组字母可以组成的所有单词。
使用trie数据结构存储单词字典,实现搜索算法查找字典中最长的单词作为给定字符串的前缀。