背景

去年下半年，我在微信书架里加入了许多技术书籍，各种类别的都有，断断续续的读了一部分。

没有计划的阅读，收效甚微。

新年伊始，我准备尝试一下其他方式，比如阅读周。每月抽出1~2个非连续周，完整阅读一本书籍。

这个“玩法”虽然常见且板正，但是有效，已经坚持阅读七个月。

已读完书籍：《架构简洁之道》、《深入浅出的Node.js》、《你不知道的JavaScript（上卷）》、《你不知道的JavaScript（中卷）》、《你不知道的JavaScript（下卷）》、《数据结构与算法JavaScript描述》、《WebKit技术内幕》、《前端架构：从入门到微前端》。

当前阅读周书籍：《秒懂算法：用常识解读数据结构与算法》。

字典树又何妨

字典树

字典树（trie）是一种适合自动补全等文字类功能的树。

字典树节点

和大多数树一样，字典树中有一些节点，而这些节点会指向其他节点。不过，字典树不是二叉树。二叉树的节点的子节点数量不能大于2，但是字典树节点可以有任意数量的子节点。

实际字典树节点的实现非常简单。TrieNode类的Python实现如下。

class TrieNode:
  def __init__(self):
    self.children = {}

可以看到，TrieNode只包含一个哈希表。

如果（在命令行中）打印上面的例子中的根节点的数据，就会看到以下内容。

{'a': <__main__.TrieNode instance at 0x108635638>,
 'b': <__main__.TrieNode instance at 0x108635878>,
 'c': <__main__.TrieNode instance at 0x108635ab8>}

在这个哈希表中，键是独立的字母字符串，值是其他TrieNode的实例。

Trie类

要完整实现字典树，还需要一个单独的Trie类来记录根节点。

class Trie:
  def __init__(self):
    self.root = TrieNode()

这个类记录了self.root变量，该变量指向根节点。在这个实现中，每次创建新的Trie，都会有一个空的TrieNode作为根节点。

存储单词

字典树的用途是存储单词。

以字典树如何存储单词“ace”“bad”和“cat”。

字典树把3个单词的每个字母都作为一个字典树节点存储。如果从根节点开始，那么跟着键"a"就能找到包含键"c"的子节点。而键"c"又会指向包含键"e"的节点。把这3个字母串联起来，就得到了单词“ace”。

字典树也会采用同样的方式存储单词“bad”和“cat”。

注意，单词的最后一个字母实际上也有自己的子节点。例如，在单词“ace”的"e"节点中，"e"就指向一个子节点，而该子节点中是一个有键"*"的哈希表。（因为它的值是什么无所谓，所以把它设为空。）这意味着已经抵达了单词末尾，说明“ace”是一个完整单词。

需要星号的原因

假设要在字典树中存储单词“bat”和“batter”。这是一个有趣的情况，因为“batter”中就包含了“bat”。

第一个"t"指向了一个有两个键的节点。一个键是"*"（值为空），另一个键是"t"，其值指向另一个节点。这意味着虽然“bat”是另一个更长的单词“batter”的前缀，但它自己也是一个单词。

我们用花括号来表示节点包含哈希表。但是{*, "t"}不再表示键-值对，而是两个键。"*"键的值为空，"t"键的值则是下一个节点。

这就是"*"很重要的原因。我们需要用星号来表示单词的一部分也是一个完整单词。

字典树查找

字典树最经典的操作是查找，也就是判断字符串是否在字典树中。字典树查找分为两类：既可以查找以判断字符串是否是完整单词，也可以查找以判断字符串是否至少是某个单词的前缀（也就是单词的开头部分）。这两类查找很相似，但这里会实现后一类，也就是查找前缀。因为完整单词也可以算作前缀，所以后一类查找最后也能找到完整单词。

前缀查找的算法有以下步骤：

(1) 创建一个变量currentNode。在算法开始时，该变量会指向根节点。

(2) 遍历查找字符串的每个字母。

(3) 指向查找字符串中的一个字母时，检查currentNode是否有以该字母为键的子节点。

(4) 如果没有，就意味着字典树中不存在这个字符串，我们返回None。

(5) 如果currentNode确实有以当前字母为键的子节点，就把currentNode更新为该子节点。然后回到步骤(2)，继续遍历字符串中的字母。

(6) 如果成功遍历了查找字符串的所有字母，就意味着字典树中存在该字符串。

字典树查找的效率

字典树查找的一大优势是高效。

哈希表查找只需要O(1)时间。事实上，查找字符串中有多少个字母，算法就需要多少步。

这比在有序数组中使用二分查找要快得多。二分查找需要O(log N)步，其中N表示字典中的单词数量。而字典树查找需要的步骤数和要查找的单词的字母数相同。例如，查找“cat”只需要3步。

用大O记法表示字典树查找的效率有一点儿难。因为步骤数取决于要查找的单词的长度，所以如果步骤数不固定，就不能说它是O(1)。因为N通常指的是数据结构中存储的数据量，所以O(N)也不太准确。这里N表示字典树的节点数量，它可比要查找的字符串的字母数量多多了。

大部分资料把它的效率表示为O(K)，其中K表示查找字符串中的字母数量。虽然用除了N以外的任何字母表示都可以，但大家都是用K。

总结

如果数组中的词汇按字母顺序排列，那么就可以使用二分查找在O(log N)时间内找到以“catn”开头的词。虽然O(log N)并不慢，但是我们还能做得更好。

字典树可以在O(1)步之内找到想要找的词。因为字典树可以实现自动补全或者自动纠错等功能。

每种树的特点和用法都不一样，适用于不同的场景。希望你能去了解这些不同的树。但无论如何，你现在都已经学到了一点：不同的树可以解决不同的问题。

作者介绍
非职业「传道授业解惑」的开发者叶一一。
《趣学前端》、《CSS畅想》等系列作者。华夏美食、国漫、古风重度爱好者，刑侦、无限流小说初级玩家。
如果看完文章有所收获，欢迎点赞👍 | 收藏⭐️ | 留言📝。