这系列是根据极客时间《数据结构与算法之美》这个课程做的笔记

本篇目录

• 跳表
• 树
• 堆
• 图

跳表

什么是跳表？ 【代码】

为一个值有序的链表建立多级索引，比如每2个节点提取一个节点到上一级，我们把抽出来的那一级叫做索引或索引层。如下图所示，其中down表示down指针，指向下一级节点。以此类推，对于节点数为n的链表，大约可以建立log2n-1级索引。像这种为链表建立多级索引的数据结构就称为跳表。

跳表的时间复杂度？

1. 计算跳表的高度
   如果链表有n个节点，每2个节点抽取抽出一个节点作为上一级索引的节点，那第1级索引的节点个数大约是n/2，第2级索引的节点个数大约是n/4，依次类推，第k级索引的节点个数就是n/(2^k)。假设索引有h级别，最高级的索引有2个节点，则有n/(2^h)=2，得出h=log2n-1，包含原始链表这一层，整个跳表的高度就是log2n。

2. 计算跳表的时间复杂度
   假设我们在跳表中查询某个数据的时候，如果每一层都遍历m个节点，那在跳表中查询一个数据的时间复杂度就是O(m * logn)。那这个m是多少呢？如下图所示，假设我们要查找的数据是x，在第k级索引中，我们遍历到y节点之后，发现x大于y，小于后面的节点z，所以我们通过y的down指针，从第k级下降到第k-1级索引。在第k-1级索引中，y和z之间只有3个节点（包含y和z），所以，我们在k-1级索引中最多只需要遍历3个节点，以此类推，每一级索引都最多只需要遍历3个节点。所以m=3。因此在跳表中查询某个数据的时间复杂度就是O(logn)。

   

跳表的空间复杂度及如何优化？

1. 计算索引的节点总数
   如果链表有n个节点，每2个节点抽取抽出一个节点作为上一级索引的节点，那每一级索引的节点数分别为：n/2，n/4，n/8，…，8，4，2，等比数列求和n-1，所以跳表的空间复杂度为O(n)。
2. 如何优化时间复杂度
   如果链表有n个节点，每3或5个节点抽取抽出一个节点作为上一级索引的节点，那每一级索引的节点数分别为（以3为例）：n/3，n/9，n/27，…，27，9，3，1，等比数列求和n/2，所以跳表的空间复杂度为O(n)，和每2个节点抽取一次相比，时间复杂度要低不少呢。

高效的动态插入和删除？

跳表本质上就是链表，所以仅插作，插入和删除操时间复杂度就为O(1)，但在实际情况中，要插入或删除某个节点，需要先查找到指定位置，而这个查找操作比较费时，但在跳表中这个查找操作的时间复杂度是O(logn)，所以，跳表的插入和删除操作的是时间复杂度也是O(logn)。

跳表索引动态更新？

当往跳表中插入数据的时候，可以选择同时将这个数据插入到部分索引层中，那么如何选择这个索引层呢？可以通过随机函数来决定将这个节点插入到哪几级索引中，比如随机函数生成了值K，那就可以把这个节点添加到第1级到第K级索引中。

二叉树基础（上）

树

树的常用概念

根节点、叶子节点、父节点、子节点、兄弟节点，还有节点的高度、深度以及层数，树的高度。

概念解释

• 节点：树中的每个元素称为节点
• 父子关系：相邻两节点的连线，称为父子关系
• 根节点：没有父节点的节点
• 叶子节点：没有子节点的节点
• 父节点：指向子节点的节点
• 子节点：被父节点指向的节点
• 兄弟节点：具有相同父节点的多个节点称为兄弟节点关系
• 节点的高度：节点到叶子节点的最长路径所包含的边数
• 节点的深度：根节点到节点的路径所包含的边数
• 节点的层数：节点的深度+1（根节点的层数是1）
• 树的高度：等于根节点的高度

二叉树

概念

• 什么是二叉树？
  每个节点最多只有2个子节点的树，这两个节点分别是左子节点和右子节点。
• 什么是满二叉树？
  有一种二叉树，除了叶子节点外，每个节点都有左右两个子节点，这种二叉树叫做满二叉树。
• 什么是完全二叉树？
  有一种二叉树，叶子节点都在最底下两层，最后一层叶子节都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫做完全二叉树 。

完全二叉树的存储

链式存储

每个节点由3个字段，其中一个存储数据，另外两个是指向左右子节点的指针。我们只要拎住根节点，就可以通过左右子节点的指针，把整棵树都串起来。 这种存储方式比较常用，大部分二叉树代码都是通过这种方式实现的。

顺序存储

用数组来存储，对于完全二叉树，如果节点X存储在数组中的下标为i，那么它的左子节点的存储下标为2i，右子节点的下标为2i+1，反过来，下标i/2位置存储的就是该节点的父节点。注意，根节点存储在下标为1的位置。完全二叉树用数组来存储时最省内存的方式。

二叉树的遍历 代码

• 前序遍历：对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。
• 中序遍历：对于树中的任意节点来说，先打印它的左子树，然后再打印它的本身，最后打印它的右子树。
• 后序遍历：对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印它本身。

前序遍历的递推公式： 
preOrder(r) = print r->preOrder(r->left)->preOrder(r->right) 
中序遍历的递推公式： 
inOrder(r) = inOrder(r->left)->print r->inOrder(r->right) 
后序遍历的递推公式： 
postOrder(r) = postOrder(r->left)->postOrder(r->right)->print r 
复制代码

时间复杂度：3种遍历方式中，每个节点最多会被访问2次，所以时间复杂度是O(n)。

二叉树基础（下）

二叉树常用操作

根据性质查找 & 前中后序遍历 & 层次遍历 & 高度深度层次计算 & 查找某结点右子树的最小子节点 & 查找某结点左子树的最大子节点 & 查找前驱结点和后继结点 & 左右旋 & 根据子节点情况进行插入和删除操作 & 根据父节点和叔叔结点情况进行旋转

重复数据的二叉查找树：

1. 每个结点通过链表或动态扩容数组的方式把相同值存储在同一个结点上
2. 统一一种CRD规则，如在插入时相同值插入到该结点的右子树中，查询和删除时类似，需要在右子树中查找直到遇到叶子结点

二叉查找树相对散列表的优势

我们在散列表那节中讲过，散列表的插入、删除、查找操作的时间复杂度可以做到常量级的O(1)，非常高效。而二叉查找树在比较平衡的情况下，插入、删除、查找操作时间复杂度才是O(logn)，相对散列表，好像并没有什么优势，那我们为什么还要用二叉查找树呢？
我认为有下面几个原因：

1. 散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序。而对于二叉查找树来说，我们只需要中序遍历，就可以在O(n)的时间复杂度内，输出有序的数据序列。

2. 散列表扩容耗时很多，而且当遇到散列冲突时，性能不稳定，尽管二叉查找树的性能不稳定，但是在工程中，我们最常用的平衡二叉查找树的性能非常稳定，时间复杂度稳定在O(logn)。

3. 笼统地来说，尽管散列表的查找等操作的时间复杂度是常量级的，但因为哈希冲突的存在，这个常量不一定比logn小，所以实际的查找速度可能不一定比O(logn)快。加上哈希函数的耗时，也不一定就比平衡二叉查找树的效率高。

4. 散列表的构造比二叉查找树要复杂，需要考虑的东西很多。比如散列函数的设计、冲突解决办法、扩容、缩容等。平衡二叉查找树只需要考虑平衡性这一个问题，而且这个问题的解决方案比较成熟、固定。

5. 最后，为了避免过多的散列冲突，散列表装载因子不能太大，特别是基于开放寻址法解决冲突的散列表，不然会浪费一定的存储空间。

综合这几点，平衡二叉查找树在某些方面还是优于散列表的，所以，这两者的存在并不冲突。我们在实际的开发过程中，需要结合具体的需求来选择使用哪一个。

红黑树（上）

二叉查找树是常用的一种二叉树，他支持快速插入，删除，查找操作，各个操作的时间复杂度跟树的高度成正比，理想情况下，时间复杂度是O(logn)。在很多书籍中，但凡讲到平衡二叉查找树，就会那红黑树做为例子。在工程中，很多用到平衡二叉查找树的地方都会用红黑树。

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

• 定义：二叉树中任意一个节点的左右子树的高度相差不能大于1。
  所以：完全二叉树，满二叉树都是平衡二叉树，非完全二叉树也有可能是平衡二叉树。

• 平衡二叉查找树不仅满足上面平衡二叉树的定义，还满足二叉查找树的特点。

• 发明平衡二叉查找树这类数据结构的初衷是解决普通二叉查找树在频繁的插入，删除等动态更新的情况下，出现时间复杂度退化的问题。 所以，平衡二叉查找树中“平衡”的意思，其实就是让整棵树左右看起来比较“对称”，比较“平衡”，不要出现左子树很高，右子树很矮的情况。这样就能让整颗树的高度相对低一些，相应的插入，删除，查找等操作的效率高一些。

• 若设计一个新的平衡二叉查找树，只要树的高度不比log2n大很多（如树的高度仍然是对数量级的），尽管它不符合严格的平衡二叉查找树的定义，但它仍然可以被认为是一个合格的平衡二叉查找树。

如何定义一棵“红黑树”

平衡二叉查找树有很多，如：Splay Tree(伸展树)，Treap（树堆）等，但是我们提到平衡二叉查找树，听到的基本都是红黑树。他的出境率甚至要高于“平衡二叉查找树”这几个字，甚至在有些时刻，默认平衡二叉查找树就是红黑树

红黑树：英文“Red-Black-Tree”，简称R-B Tree，有如下特性：

• 它是一种不严格的平衡二叉查找树。
• 红黑树中的节点，一类别标记为黑色，一类被标记为红色。
• 根节点是黑色的；
• 每个叶子节点都是黑色的空节点（NIL）,也就是说，叶子节点不存储数据；
• 任何相邻的节点都不能同时为红色，即红色节点都是被黑色节点隔开的；
• 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；

二叉查找树很多操作的性能都跟树的高度成正比，一课极其平衡的二叉树（满二叉树或完全二叉树）的高度大约是log2n,所以要证明红黑树是近似平衡的，我们只需要分析，红黑树的高度是否比较稳定地趋近log2n就好。

红黑树的高度分析

1. 首先，若将红色节点从红黑树中去除，那单纯包含黑色节点的红黑树的高度比包含相同节点个数的完全二叉树的高度要小。所以去掉红色节点的“黑树”的高度也不会超过log2n。
2. 在红黑树中，红色节点不能相邻，即有一个红色节点就要至少有一个黑色节点，将它更其他红色节点隔开。 红黑树中包含最多黑色节点的路径不会超过log2n,所以加入红色节点之后，最长路径不会超过2log2n，即，红黑树的高度近似2log2n
3. 红黑树的高度只比高度平衡的AVL树的高度（log2n）仅仅大了一倍，在性能上下降的并不多。

工程中大家都喜欢用红黑树这种平衡二叉查找树的原因：

1. Treap，Splay Tree，绝大部分情况下，它们操作的效率都很高，但是也无法避免极端情况下时间复杂度的退化。尽管这种情况出现概率不大，但是对于单次操作时间非常敏感的场景来讲，它们不适用。
2. AVL树是一种高度平衡的二叉树，所以查找的效率非常高，但是，有利有弊，AVL树为了维持这种高度平衡，要付出更多代价，每次插入，删除都要做调整，就比较复杂，耗时。所以有频繁的插入，删除操作的数据集合，使用AVL树的代价就有点高了。
3. 红黑树只是做到了近似平衡，并不是严格的平衡，所以维护平衡的成本上，要比AVL树低。

所以，红黑树的插入，删除，查找各种操作性能都比较稳定。对于工程应用来说，结果状态可控可预期。

红黑树（下）

我的红黑树学习之路

堆

如何理解“堆”

1. 堆是一个完全二叉树；
   完全二叉树要求除了最后一层，其他层的节点都是满的，最后一层的节点都靠左排列。
2. 堆中每个节点都必须大于等于（或小于等于）其子树中每个节点的值。
   堆中每个节点的值都大于等于（或者小于等于）其左右子节点的值。
3. 对于每个节点的值都大于等于子树中每个节点值的堆，叫作“大顶堆”。对于每个节点的值都小于等于子树中每个节点值的堆，叫“小顶堆”。

如何实现“堆”

要实现一个堆，要先知道堆都支持哪些操作，已及如何存储一个堆。

如何存储一个堆：

完全二叉树比较适合用数组来存储。用数组来存储完全二叉树是非常节省存储空间的。因为不需要存储左右子节点的指针，单纯地通过数组的下标，就可以找到一个节点的左右子节点和父节点。

往堆中插入一个元素

往堆中插入一个元素后，需要继续满足堆的两个特性

• 如果把新插入的元素放到堆的最后，则不符合堆的特性了，于是需要进行调整，让其重新满足堆的特性，这个过程叫做 堆化（heapify）
• 堆化实际上有两种，从下往上和从上往下
• 堆化方法： 堆化非常简单，就是顺着节点所在的路径，向上或者向下，对比，然后交换。

删除堆顶元素

把最后一个节点放到堆顶，然后利用同样的父子节点对比方法，对于不满足父子节点大小关系的，互换两个节点，并且重复进行这个过程，直到父子节点之间满足大小关系为止，这是从上往下的堆化方法。

一个包含n个节点的完全二叉树，树的高度不会超过log2n。堆化的过程是顺着节点所在路径比较交换的，所以堆化的时间复杂度跟树的高度成正比，即O(log n)。插入数据和删除堆顶元素的主要逻辑就是堆化，所以往堆中插入一个元素和删除堆顶元素的时间复杂度都是O(log n)。

如何基于堆实现排序

• 排序方法有时间复杂度是O(n^2)的冒泡排序，插入排序，选择排序，有时间复杂度是O（nlogn）的归并排序，快速排序，线性排序。

• 借助堆这种数据结构实现的排序算法就叫作堆排序，这种排序方法的时间复杂度非常稳定，是O(nlogn)，并且它还是原地排序算法。

堆排序的过程

大致分解为两大步骤：建堆和排序

• 建堆：

  1. 首先将数组原地建成一个堆。“原地”：是指不借助另一个数组，就在原地数组上操作。
  2. 建堆有两种思路：
     • 第一种：在堆中插入一个元素的思路。尽管数组中包含n个数据，但是可以假设起初堆中只包含一个数据，就是下标为1的数据。然后，调用插入方法，将将下标从2到n的数据依次插入到堆中，这样就将包含n个数据的数组，组织成了堆
     • 第二种：是从后往前处理数组，并且每个数据都是从上往下堆化。

  第二种和第一种思路截然相反，第一种建堆思路的处理过程是从前往后处理数据，并且每个数据插入堆中时，都是从下往上堆化。第二种对下标从n/2开始到1的数据进行堆化，下标是n/2 + 1到n的节点，是叶子节点，不需堆化

  

  3. 建堆的时间复杂度
  每个节点堆化的时间复杂度是 O(log n)，那 n/2 个节点堆化的总时间复杂度是不是就是 O(nlog n)呢？这个答案虽然也没错，但是这个值还是不够精确。实际上，堆排序的建堆过程的时间复杂度是O(n)。

• 排序：
  建堆结束后，数组中的数据已是按照大顶堆的特性来组织的。数组中的第一个元素就是堆顶，也就是最大的元素。将它和最后一个元素交换，最大元素就放到了下标为n的位置。这个过程有点类似“删除堆顶元素”的操作，当堆顶元素移除后，把下标为n的元素放到堆顶，然后在通过堆化的方法，将剩下的n-1个元素重新构建成堆。堆化完成之后，在取堆顶元素，放到下标是n-1的位置，一直重复这个过程，直到最后堆中只剩下标为1的一个元素，排序工作就完成了。

  

时间，空间复杂度，以及稳定性分析

①：整个堆排序的过程，都只需要极个别临时存储空间，所以堆排序是原地排序算法。
②：堆排序包括建堆和排序两个操作，建堆过程的时间复杂度是O(n)，排序过程的时间复杂度是O(nlogn),所以堆排序的时间复杂度是O(nlogn)
③：堆排序不是稳定的排序算法，可能改变值相等的数据原始相对顺序。

建堆的时间复杂度O(n)推导

因为叶子节点不需要堆化，所以需要堆化的节点从倒数第二层开始。每个节点堆化的过程中，需要比较和交换的节点个数，跟这个节点的高度 k 成正比。

我把每一层的节点个数和对应的高度画了出来，你可以看看。我们只需要将每个节点的高度求和，得出的就是建堆的时间复杂度。

我们将每个非叶子节点的高度求和，就是下面这个公式：

这个公式的求解稍微有点技巧，不过我们高中应该都学过：把公式左右都乘以 2，就得到另一个公式 S2。我们将 S2 错位对齐，并且用 S2 减去 S1，可以得到 S。

S 的中间部分是一个等比数列，所以最后可以用等比数列的求和公式来计算，最终的结果就是下面图中画的这个样子。

因为 h=log2 n，代入公式 S，就能得到 S=O(n)，所以，建堆的时间复杂度就是O(n)。

堆的应用

优先级队列

• 优先级队列，数据的出队顺序不是先进先出，而是而是按照优先级来，优先级最高的，最先出队。
• 实现一个优先级队列方法很多，但是用堆来实现是最直接，最高效的，这是因为堆和优先级队列非常相似。一个堆可以看作一个优先级队列，很多时候，他们只是概念上的区分。往优先级队列中插入一个元素，就相当于往堆中插入一个元素；从优先级队列中取出优先级最高的元素，就相当于取出堆顶元素。
• 优先级队列的应用广泛，如赫夫曼编码，图的最短路径，做小生成树的算法等等

优先级队列应用一：合并有序小文件

假设：有100个小文件，每个文件大小为100MB，每个文件中储存的都是有序的字符串。现需要将这100个小文件合并成一个有序的大文件。
思路：

1. 整体思路有点像归并排序中的合并函数，从100个文件中，各取第一个字符串，放入数组中，然后比较大小，把最小的那个字符串合并后的大文件中，并从数组中删除。
2. 假设，最小的字符串来自于13.txt这个文件，就再次从这个文件找那个取下一个字符串，放到数组中，重新比较大小，并且选择最小的放入合并后的大文件，将它从数组中删除。依次类推，直到所有的文件中的数据都放入到大文件为止。
3. 使用数组来存储从小文件中取出来的字符串，每次从数组中取最小字符串，都需要循环遍历整个数组，效率不高。
4. 可以用到优先级队列，也可以说是堆。将从小文件中取出的字符串放入到小顶堆中，堆顶的元素就是优先级队列队首的元素，就是最小的字符串。
5. 依次从小文件中取出下一个字符串，放入到堆中，循环这过程。

删除堆顶数据和往堆中插入数据的时间复杂度都是O(logn)，n表示堆中的数据个数，这里就是100

优先队列应用二：高性能定时器

假设：有一个定时器，定时器中维护了很多定时任务

1. 每过1秒就扫描一遍任务列表做法太低效。原因1：任务的约定执行时间离当前时间可能还有很久，大量的扫描徒劳无功。原因2：每次都要扫描整个任务列表，若列表较大，会比较耗时。
2. 针对这种文件，可用优先队列来解决。按照任务设定的执行时间，将这些任务存储在优先级队列中，队列首部（最小顶堆）存储的是最先执行的任务。
3. 这样定时器就不用每隔一秒就扫描一遍任务列表了。它拿队首任务的执行时间点，与当前时间点相减，即可得到一个时间间隔T。
4. 当T秒时间过去后，定时器取优先级队列中队首的任务执行，然后在计算新的队首任务的执行时间点和当前时间点的差值。
5. 这样定时器就不用间隔1秒就轮询一次，也不用遍历整个任务列表，性能就提高了。

利用堆求Top K

求Topk的问题可抽象成两类：

1. 针对静态数据
   可以维护一个大小为k的小顶堆，顺序遍历数组，从数组中取出数据与堆顶元素比较。如果堆顶元素大，就将堆顶元素删除，并且将这个元素插入到堆中；如果比堆顶元素小则不做处理，继续遍历数组。这样等数组中的数据都遍历完之后，堆中的数据就是前k大数据了。
   遍历数据需要O(n)的时间复杂度，一次堆化操作需要O(logk)的时间复杂度，最坏情况下，n个元素都入堆一次，时间复杂度就是O(nlogk)。

2. 针对动态数据求得Topk就是实时Topk。 一个数据集合有两个操作，一个是添加数据，另一个询问当前的前k大数据。 可以维护一直都维护一个k大小的小顶堆，当有数据被添加到集合时，就那它与堆顶的元素对对比。如果比堆顶元素大，就把堆顶元素删除，并将这个元素插入到堆中，如果比堆顶元素小，这不处理。这样，无论任何时候需要查询当前的前k大数据，就都可以 立刻返回给他。

利用堆求中位数

1. 对于一组静态数据，中位数是固定的，可以先排序，第n/2个数据就是中位数。
2. 对于动态数据集合，就无法先排序了，需要借助堆这种数据结构，我们不用排序，就可以非常高效的实现求中位数操作。

实现思路：

1. 需要维护两个堆，大顶堆中存储前半部分数据，小顶堆中存储后半部分数据，且小顶堆中的数据都大于大顶堆中的数据。
2. 即：如果有n个数据，n是偶数，从小到大排序，那前n/2个数据存储在大顶堆中，后n/2个数据存储在小顶堆中。这样，大顶堆中堆顶元素就是要找的中位数。
3. 如果新加入的数据小于等于大顶堆的堆顶元素，就将这个数据插入到大顶堆；否则就插入小顶堆
4. 当两个堆中的数据量不服和中位数的约定时，就从一个堆中不停的将堆顶的元素移动到另一个堆，重新让两个堆中数据满足上面的约定。

于是，可以利用两个堆实现动态数据集合中求中位数的操作，插入数据因为涉及堆化，所以时间复杂度变成了O(logn)，但求中位数只需要返回大顶堆的堆顶元素就可以了，所以时间复杂度就是O(1)。

图

如何理解“图”

• 图和树一样都是非线性表数据结构，和树不同的是图是一种更加复杂的非线性表结构
• 树中的元素称之为节点，图中的元素则称之为顶点。
• 顶点可以与任意其他顶点建立关联，这种建立的关系叫做边，与顶点相连接的条数叫做顶点的度。
• 图可以分为有向图和无向图两种，有向图的边有方向。
• 在有向图中，度可以分为入度和出度（Out-degree）。顶点的入度，表示有多少条边指向这个顶点；顶点的出度，表示有多少条边是以这个顶点为起点指向其他顶点。
• 带权图：在带权图中，每条边都有一个权重

邻接矩阵存储方法

图最直观的一种存储方法是：邻接矩阵（Adjacency Matrix），邻接矩阵的底层依赖一个二维数组。对于无向图来说，如果顶点i与顶点j之间有边，我们就将A[i][j]和A[j][i]标记为1；对于有向图来说，如果顶点i到顶点j之间，有 一条箭头从顶点i指向顶点j的边，那我们就将A[i][j]标记为1。同理，如果有一条箭头从顶点j指向顶点i的边，我们就将A[j][i]标记为1。对于带权图，数组中就存储相应的权重。

用邻接矩阵来表示一个图，虽然简单，直观，但是浪费存储空间。

• 对于无向图的二维数组中，如果将其对角线划分为上下两部分，那我们只需要利用上面或者下面这样的一半的空间就足够了，另一半白白浪费掉了。
• 若存储的是稀疏图（Sparse Matrix），即顶点很多，但每个顶点的边并不多，那邻接矩阵的存储方法就更加浪费空间了。

用邻接矩阵存储的优点：

1. 存储方式简单，直接，因为基于数组，所以在获取两个顶点的关系时，就非常高效。
2. 其次是计算方便。因为，可以将很多图的运算转换成矩阵之间的运算。如求解最短路径问题时会提到一个Floyd-Warshall算法，就是利用矩阵循环相乘若干次得到结果。

邻接表存储方法

邻接表（Adjacency List）可以解决邻接矩阵存储方式比较浪费内存空间的问题

每个顶点对应一条链表，链表中存储的是与这个顶点相连接的其他顶点。另外我需要说明一下，图中画的是一个有向图的邻接表存储方式，每个顶点对应的链表里面，存储的是指向的顶点。对于无向图来说，也是类似的，不过，每个顶点的链表中存储的，是跟这个顶点有边相连的顶点

• 邻接矩阵存储起来比较浪费空间，但使用比较节省时间，邻接表存储与之相反。 如图中，如果要确定是否存在从顶点2到顶点4的边，就需要遍历顶点2对应的链表，看那条链表中是否存在顶点4。但链表的存储方式对缓存不友好。
• 我们可以将邻接表中的链表改成平衡二叉查找树，实际开发中国还可选用红黑树。这样可以快速查找两个顶点之间是否存在边了。

图的应用

如何存储微博，微信等社交网络中的好友关系？

1. 微博，微信是两种“图”，前者是有向图，后者是无向图。
2. 数据结构是为算法服务的，所以具体选择哪种存储方法，与期望支持的操作有关系。针对微博的用户关系，需要支持：
   • 判断用户A是否关注了用户B;
   • 判断用户A是否是用户B的粉丝
   • 用户A关注用户B；
   • 用户A取消关注用户B；
   • 根据用户名称的首字母排序，分页获取用户的粉丝列表；
   • 根据用户名称的首字母排序，分页获取用户的关注列表。
3. 因为社交网络是一张稀疏图，使用邻接矩阵存储比较浪费存储空间，所以使用邻接表来存储。
4. 但用一个邻接表来存储这种有向图是不够的，查找某个用户关注了哪些用户非常容易，但是如果想要知道某个用户都被哪些用户关注了，是非常困难的。
5. 因此，需要一个逆邻接表。邻接表中存储了用户的关注关系，逆邻接表中存储的是用户的被关注关系。
6. 对应到图上，邻接表中，每个顶点的链表中，存储的就是这个顶点指向的顶点，逆邻接表中，每个顶点的链表中，存储的是指向这个顶点的顶点。