为实习准备的数据结构（13）-- 前缀树（字典树、Trie）

什么是前缀树？

直接说可能不太理解，我直接来张图：

晓得了吧，一种特殊的N叉树。用于检索字符串数据集中的键。

Trie的应用场景

自动补全

就是前面那张谷歌的图，我也想自己截，奈何技术跟不上啊。

拼写检测

最长前缀匹配

比方说正则表达式，不过正则比这个要复杂一些了。

可以用来提取出表中所有以“ABC”开头的数据，但是数据表浩如烟海，你总不能让我去遍历吧！！！

Trie存在即合理

在平衡树、哈希表等树据结构的重重包围之下，Trie还是占据了一席之地，那么它有什么突出点呢？

这些树据结构，虽然各有千秋，但是总有鞭长莫及的时候，碧如：

找到具有同一前缀的全部键值。
按词典序枚举字符串的数据集。

  

 

  
1
  
2
 

没办法吧！！

随着哈希表大小增加，会出现大量的冲突，时间复杂度可能增加到 O(n)与哈希表相比，Trie 树在存储多个具有相同前缀的键时可以使用较少的空间。此时 Trie 树只需要 O(m)的时间复杂度，其中 m 为键长（顶多5*m）。而在平衡树中查找键值需要 O(mlog⁡n)时间复杂度。

Trie的实现

节点结构

Trie 树是一个有根的树，其结点具有以下字段：。

最多 R 个指向子结点的链接，其中每个链接对应字母表数据集中的一个字母。
布尔字段，以指定节点是对应键的结尾还是只是键前缀。

  

 

  
1
  
2
 

class Trie {
private: bool isEnd; Trie* next[26];
public: void insert(string word); bool search(string word); bool startsWith(string prefix);	//前缀匹配
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
 

先捋一下这个节点结构，会发现它没有包当前节点值。这是为什么呢？这是由于它的字母映射表机制决定的（next）。

next当中包括了接下来可能会出现的所有字母，所以只需：

for (int i = 0; i < 26; i++) { char ch = 'a' + i; if (parentNode->next[i] == NULL) { //说明父结点的后一个字母不可为 ch } else { //说明父结点的后一个字母可以是 ch }
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
 

自己捋一下。

增

往前缀树中插入一个单词。

这有三种情况。
1、这个单词已经存在
2、这个单词已经是前缀了
3、这个单词不存在

对这三种情况，首先要做的都是遍历这棵树。
如果存在，那就没事儿了。
如果是前缀，那就改成完整的单词。
如果不存在，那就把缺少的字母补进去，并设为完整的单词。

void insert(string word) { Trie* node = this; for (char c : word) { if (node->next[c-'a'] == NULL) { node->next[c-'a'] = new Trie(); } node = node->next[c-'a']; } node->isEnd = true;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
 

查

在前缀树中查找一个单词是否存在。
这里有两种情况：
查到一半发现单词断层了，这妥妥的没了、
查到最后，结果这个单词只是前缀，那也是不行的。

bool search(string word) { Trie* node = this; for (char c : word) { node = node->next[c - 'a']; if (node == NULL) { return false; } } return node->isEnd;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
 

前缀匹配

匹配一个单词是否是前缀树中的前缀。

你看呢？

bool search(string word) { Trie* node = this; for (char c : word) { node = node->next[c - 'a']; if (node == NULL) { return false; } } return true;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
 

习题推荐

困难题·单词搜索

文章来源: lion-wu.blog.csdn.net，作者：看，未来，版权归原作者所有，如需转载，请联系作者。

原文链接：lion-wu.blog.csdn.net/article/details/114939297