zdaiot

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

我们经常使用搜索引擎的搜索关键词提示功能，如下图所示：

那么它底层使用的是什么数据结构呢？具体是怎么实现的呢？

什么是“Trie 树”？

首

先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

BM 算法很复杂，也不好理解，却是工程中非常常用的一种高效字符串匹配算法。有统计说，它是最高效、最常用的字符串匹配算法。不过，所有的字符串匹配中，最知名的是 KMP 算法。当然实际开发中，不大可能自己亲手实现一个 KMP 算法。但是学习下这个算法的思想，让你开拓眼界、锻炼下逻辑思维，也是极好的。

实际上，KMP 算法和 BM 算法的本质是一样的。

KMP 算法基本原理

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是最简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

字符串匹配算法有很多种。例如简单、好理解的BF 算法和 RK 算法。还有比较难理解、但更加高效的BM 算法和 KMP 算法。

字符串匹配算法也可以分为单模式串匹配算法，也就是一个串跟一个串进行匹配。还有多模式串匹配算法，也就是在一个串中同时查找多个串，它们分别是 Trie 树和 AC 自动机。

本节主要讲述两个算法：RK 算法和 BF 算法。前者主要是对后者的改进，巧妙借住了前面说过的哈希算法，让匹配的效率有很大的提升。那RK 算法是如何借助哈希算法来实现高效字符串匹配的呢？

BF 算法

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

文本编辑器中有查找替换功能，比如将Word中一个单词统一替换成另外一个。它是怎么实现的呢？上一节讲的 BF 算法在某些极端情况下，性能会退化的比较严重。RK 算法需要用到哈希算法，而设计一个可以应对各种类型字符的哈希算法并不简单。

那对于查找功能是重要功能的软件来说，它们的查找功能是用哪种算法实现的呢？实际上它是用BM（Boyer-Moore）算法实现的。它是非常高效的字符串匹配算法，性能是著名的KMP算法的3倍到4倍。

BM算法的核心思想

将模式串和主串的匹配过程，看作模式串在主串中不停地往后滑动。当遇到不匹配的字符时，BF 算法和 RK 算法的做法是，模式串往后滑动一位，然后从模式串的第一个字符开始重新匹配。如下图所示：

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

社交网路中，有一个六度分割理论。也就是说，你与世界上的另一个人间隔的关系不会超过六度，也就是说平均只需要六步就可以联系到任何两个互不相识的人。

用户的一度连接用户就是他的好友，而二度连接用户就是他好友的好友，三度连接用户就是他好友的好友的好友。那么给定一个用户，如何找出这个用户的所有三度（其中包含一度、二度和三度）的好友关系？

这就需要用到本节的深度优先和广度优先搜索算法。

什么是“搜索”算法？

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

如何存储微博、微信等这些社交网络的好友关系呢？这就需要用到接下来要说的图这种数据结构。

如何理解“图”？

跟树一样，图也是一种非线性表数据结构。不过它比树更加复杂。

树中元素称为节点，而图中元素称为顶点（vertex）。顶点与顶点之间可以建立连接关系，称为边（edge）。

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

假设现在我们有一个包含 10 亿个搜索关键词的日志文件，如何能快速获取到热门榜 Top 10 的搜索关键词呢？

这个问题可以使用堆来解决。实际上，堆除了可以应用在堆排序，还有几个特别重要的应用：优先级队列、求 Top K 和求中位数。

堆的应用一：优先级队列

优先级队列首先应该是一个队列，队列的最大的特性就是先进先出。不过在优先级队列中，数据的出队顺序不是先进先出，而是按照优先级来，优先级最高的，最先出队。

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

“堆”（Heap）是一种特殊的树，其最常用的场景为堆排序。堆排序是一种原地的、时间复杂度为 $O(nlogn)$ 的排序算法。

快速排序，平均情况下，它的时间复杂度为 $O(nlogn)$。尽管这两种排序算法的时间复杂度都是 $O(nlogn)$，甚至堆排序比快速排序的时间复杂度还要稳定，但是，在实际中，快速排序的性能要比堆排序好，这是为什么呢？

如何理解“堆”？

堆是一种特殊的树，需要满足下面两点：

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

之前我们使用过递推公式求解归并排序、快速排序的时间复杂度。但是有些情况，比如说使用递推公式求解快排的平均时间复杂度，会涉及到非常复杂的数学推导。此时使用递归树来分析递归算法的时间复杂度会更加简单。

递归树与时间复杂度分析

递归的思想就是：将大问题分解为小问题来求解，然后再将小问题分解为小小问题。这样一层一层地分解，直到问题的数据规模被分解得足够小，不用继续递归分解为止。

如果把这个一层一层的分解过程画成图，它其实就是递归树。如下为斐波那契数列的递归树，节点里的数字表示数据的规模，一个节点的求解可以分解为左右子节点两个问题的求解。

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

二叉查找树是最常用的一种二叉树，支持快速插入、删除、查找操作，各个操作的时间复杂度跟树的高度成正比，理想情况下时间复杂度是$O(logn)$。

不过，二叉查找树在频繁的动态更新过程中，可能会出现树的高度远大于 log2n 的情况，从而导致各个操作的效率下降。极端情况下，二叉树会退化为链表，时间复杂度会退化到 $O(n)$。为了解决这个问题，需要设计一种平衡二叉查找树。

常用的平衡二叉查找树是红黑树，为什么工程中都喜欢红黑树，而不是其他平衡二叉查找树呢？

什么是“平衡二叉查找树”？