day8 实现 Trie (前缀树)

每周五组会；今天应当开始准备了。

读题

Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。
请你实现 Trie 类：

• Trie() 初始化前缀树对象。
• void insert(String word) 向前缀树中插入字符串 word 。
• boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
• boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

思路

第一思路

感觉是纯代码，不涉及算法的一道题，照着前缀树的定义写就是了；不过，题目没有给出前缀树的定义和操作细节。未来的面试中或许会作为题目（或者题目的一部分）出现，考察我是否知道并熟悉前缀树这种数据结构。
按照实例，前缀树应该是按照一定规则排列的单个字母（在本题中），按照特定顺序组合起来得到词。例如，插入 “apple”，于是树里就有节点 “a””p””p””l””e”；应该是从上往下排列，因此可以便捷搜索其开头的 “app” 字符串。
但如果仅仅是这样，数列也能完成。既然是树，一定有是树的道理。
是什么呢？
是以树的结构组织数据能令搜索更加高效吗？
是将具有相同前缀的字符串合并？例如 application 和 apple，都合并到 app 中 p 节点的子树下？

---

问题来了：应该怎么判断根节点应当是哪个？例如，我有树插入了 apple，现在我想要插入 pear，但是首个字母与 apple 不同。
或许可以有共同根节点，不保存数据，仅仅是作为众多数据的根。
因为数据都是小写英文字母，考虑使用一个二十六叉树，通过穷举完成。
于是：
方法 Trie：新建一个根节点。是 Trie 类的构造函数。

1. 新建一个根节点，不需要返回，而是作为全局的（这个 Trie 的）根

方法 insert：先搜索，找到对应的位置；在其末尾递归插入数据。

1. 循环向下搜索开头的字母
2. 如果遇到下一个字母不存在于树中的情况：
   1. 循环插入

方法 search：循环判断是否存在于树中。

1. 循环判断是否存在于树中

方法 startsWith：

1. 遍历，找到输入字符串开头的那个字母
2. 使用 search 方法判断是否是之前插入的那个字符串
   1. 如果是，则 search 开头的字符串
   2. 如果不是，则下一个

百度一下

要是我臆想的前缀树从根本上就是错的，那我岂不是白写代码了？
所以写代码前，百度一下。
百度言：
前缀树的3个基本性质：

1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
3. 每个节点的所有子节点包含的字符都不相同。

第一条第二条第三条都和我臆想的基本一致，不过这第三条性质应该不是通过所谓二十六叉树实现的，而是更高明的使用到了哈希的表示方法？
经过搜索，一般是使用一个数列保存子指针（变相的二十六叉树），或者通过哈希表（也就是 python 的字典）来保存，将二十六个字母和子树节点指针对应起来。

---

值得一提的是，一般会使用一个节点来标记单词的结尾，以和其他“未填充”的节点区分开。
虽然我不是很理解为什么这么做但先照做。

---

看上去我的思路基本没错，打算用哈希表来实现。于是有节点定义：

struct node {
  int val;
  map<char, node*> next_map;
  node() : val(0) {} // 是 node 自己的构造函数，赋初值，免得新建节点时总是要手动赋值
};

构造函数/初始化：

Trie() {
    root = new node();
}

我发现 cpp 有个类似 python for a in b 的语法，for (char c : word)。挺方便。
插入：

void insert(string word) {
	node* p = root;
	for (char c : word) {
	    // 插入，深入
		if (p->next_map.find(c) == p->next_map.end()) {
			p->next_map[c] = new node();
		}
		p = p->next_map[c]; // 向下
	}
	p->val = 1; // 单独新建节点说明是一个单词的结尾
}

if (p->next_map.find(c) == p->next_map.end()) 这个是检查 next_map 中是否包含我想要的子节点（这是抄来的，如果让我自己写，应该会写成巨繁琐的嵌套 for 循环），其中：

• 方法 find 是 map 的成员函数，
  • 如果找到，返回一个迭代器（iterator），指向该条目
    • 键为 c，值为对应的子节点指针。
  • 如果没找到，返回 next_map.end()。
• map::end() 是 “尾后迭代器”，它不指向任何实际元素，仅作为 “查找失败” 的标志。
  因此，find(c) == end() 表示 “在 next_map 中没有找到字符 c 对应的子节点”。

搜索：

bool search(string word) {
	node* p = root;
	for (char c : word) {
		if (p->next_map.find(c) == p->next_map.end()) {
			return false;
		}
		p = p->next_map[c];
	}
	return p->val == 1; // 最后一个节点的val为1，才表示是完整单词
}

条件判断同理。

搜索前缀：

bool startsWith(string prefix) {
	node* p = root;
	for (char c : prefix) {
		if (p->next_map.find(c) == p->next_map.end()) {
			return false;
		}
		p = p->next_map[c];
	}
	return true;
}

太优雅了这个 for。
如果没有它，我可能会循环一个 i，然后将字符串视为数组。

结果

过了，37 ms，38.63 MB，时间中规中矩，空间用得比较少，应该是得益于哈希表写法。
总而言之，理解前缀树是什么就好写。
寻找 next_map 中是否有指定子节点那里的逻辑比较难写；如果是我自己写，我会写成数列和 for 循环。
用 map 和 find 就优雅了不少。

官方题解

官方题解没有定义 node，而是定义了一个 vector<Trie*> children 和 bool isEnd, 对应构造函数 Trie() : children(26), isEnd(false) {}。
用数列表示，观感妥妥的是二十六叉树……客观上用了二十六个子节点的空间。哈希表应该是能节约不少空间。
官方只有这一个题解。

收获

题目不难，但是收获颇丰。

1. 前缀树本身
2. 基于范围的for循环(C++11)
3. if (p->next_map.find(c) == p->next_map.end()) 优雅的 map 搜索
4. 复习了构造函数的写法