数据结构与算法（一）

时间&空间复杂度

数据结构和算法的本质是解决“快”和“省”的问题：即如何让代码运行得更快、更省存储空间。

用什么来衡量呢？就是用复杂度来，包括时间复杂度和空间复杂度，通常用大 O 复杂度表示法。

时间复杂度：并非具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的「变化趋势」，因此也叫渐进时间复杂度（asymptotic time complexity），简称时间复杂度。

PS: 可以类比数学中的极限问题。

复杂度量级表示：

image.png

复杂度量级比较：

image.png

空间复杂度：

全称渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。

常见的空间复杂度有：O(1), O(n), O(n^2).

复杂度分析法则

1. 只关注循环执行次数最多的一段代码；

2. 加法法则：总复杂度等于量级最大的那段代码的复杂度；

3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。

最好、最坏、平均、均摊时间复杂度

1. 最好情况时间复杂度（best case time complexity）：最理想的情况下，执行一段代码的时间复杂度。

2. 最坏情况时间复杂度（worst case time complexity）：最糟糕的情况下，执行一段代码的时间复杂度。

3. 平均情况时间复杂度（average case time complexity）：加权平均时间复杂度。

场景分析：从一个无序数组中查找指定的元素 x 并返回。

case1: 若 x 在第一个位置出现，则查找时间复杂度为 O(1)，该情况为最好时间复杂度；

case2: 若 x 在该数组中不存在，则需要遍历整个数组，复杂度为 O(n)，为最坏状况复杂度；

而平均复杂度就是根据 x 在数组中每个位置出现的概率求出的加权平均值。

4. 均摊时间复杂度（amortized time complexity）

该复杂度比较特殊，通常用于对一个数据结构一组连续的操作：大部分情况下复杂度很低，个别情况下复杂度较高，而且前后一般规律性的出现。此时，可以将这些操作放在一起分析，将复杂度较高的操作平摊到其他复杂度低的操作中。这种方法通常称为「摊还分析」。

线性表&非线性表

线性表（Linear List）：

由 n (n>=0) 个数据元素组成的有限序列。每个元素均有一个直接前驱和直接后继元素。

PS: 可以认为，每个元素的前后元素都是唯一的（如果存在）。

常用的线性表有：数组、链表、栈和队列等。示意图：

image.png

非线性表，树、图等，示意图：

image.png

数组&链表

数组：

image.png

单链表：

image.png

单链表插入和删除操作：

image.png

循环链表：

image.png

双向链表：

image.png

数组&链表比较

内存分布对比：

image.png

查询时间复杂度对比：

image.png

数组&链表小结：

1. 数组内存空间连续，链表内存空间非连续；

2. 随机访问（下标访问）：数组支持随机访问，随机访问的时间复杂度为 O(1)；链表不支持随机访问，时间复杂度为 O(n)；

3. 插入数据：由于数组内存空间连续，在数组指定位置插入元素时需要做数据搬移，时间复杂度为 O(n)；链表则直接插入即可，时间复杂度为 O(1)。

栈&队列

示意图：

image.png

栈：后进先出（Last In First Out, LIFO）

image.png

栈可以用数组或链表实现：数组实现的栈称为「顺序栈」，链表实现的栈称为「链式栈」。

使用场景：函数调用栈、表达式求值、括号匹配、浏览器前进后退等。

队列：先进先出（First In First Out, FIFO）

操作：

1. 入队（enqueue）：将一个数据元素插入队列尾部；

2. 出队（dequeue）：从队列头部取一个数据元素。

示意图：

image.png

队列可以用数组或链表来实现：数组实现的队列称为「顺序队列」

，链表实现的队列称为「链式队列」。

阻塞队列：

“生产者-消费者”模型。即队列的两端分别对应生产者和消费者，队列满的时候，生产者阻塞等待；队列空的时候，消费者阻塞等待。示意图：

image.png

实现类有 ArrayBlockingQueue、LinkedBlockingQueue 等。

小结

本文主要总结了复杂度和线性表的一些概念。

复杂度

衡量代码执行速度和占用空间的标尺。包括时间复杂度和空间复杂度，用大 O复杂度表示法。

线性表

常用的线性表包括数组、链表、栈、队列等。其中，可以认为数组和链表是最基本的数据结构，其他一些更复杂的数据结构通常可以基于二者实现或经过变形而来。

数据结构与算法（二）

跳表

前面的数据结构笔记中分析过链表，如图所示：

image.png

由于它的内存空间非连续，因此查找某个元素时只能从头到尾遍历，时间复杂度为 O(n)。那么能不能提高链表的查找效率呢？

我们可以对链表进行改造，在链表上建立一级“索引”，如图：

image.png

这样，在查找的时候就可以先在索引层查找，然后再根据索引去查数据（有点类似数据库的索引）。

为了进一步提高查找效率，还可以建立二级索引，如图：

image.png

以此类推，还可以建立更多层级的索引：

image.png

这种数据结构称为跳表（Skip List）。这样做查找速度更快了，但同时也会耗费更多的存储空间，它的思想其实就是空间换时间。

应用场景：Redis 的有序集合。

散列表

散列表（Hash table），又称“哈希表”或“Hash 表”。利用的是数组支持按照下标访问数据（时间复杂度为 O(1)）的特性，是数组的一种扩展。示意图：

image.png

其中的 key 为可理解为要存入的数据的键（键-值对形式）；hash() 是「散列函数」，它根据 key 计算得到一个非负整数，是哈希表实现的一个关键点；table 为存放数据的数组。

散列表存入数据的大概流程是：将 key 经过散列函数计算得到一个值（保证在数组长度范围内）作为数组的下标，然后将 key 的值保存在数组下标对应的位置。

散列函数

散列函数设计的基本要求：

1. 散列函数计算得到的散列值是一个非负整数（数组下标从 0 开始的）；

2. 如果 key1 = key2，那么 hash(key1) = hash(key2)；

3. 如果 key1 ≠ key2，那么 hash(key1) ≠ hash(key2)。

此外，散列函数的设计不能太复杂（会消耗很多计算时间），而且生成的值要尽可能随机并且均匀分布（尽量最小化散列冲突）。

例如，JDK 1.8 中 HashMap 的散列函数设计如下：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

注：

真实情况下，不同 key 对应的散列值都不一样的散列函数几乎是不存在的。业界著名的 MD5、SHA、CRC 等哈希算法也无法避免这种散列冲突。

因此，需要其他途径来解决散列冲突的问题。

散列冲突

解决散列冲突常用的有两种方法：开放寻址法（open addressing）和链表法（chaining）。

1. 开放寻址法

核心思想：如果出现了散列冲突，就重新探测一个空闲位置将其插入。常用的探测方法有三种：

1.1 线性探测（Linear Probing）

往散列表中插入数据时，若某个数据经散列函数散列之后，存储位置已经被占用，就从当前位置开始依次往后查找，直到找到空闲位置插入。示意图：

image.png

缺点：散列表中的数据越来越多时，空闲位置越来越少，散列冲突的可能性会越来越大，线性探测的时间会越来越久。

1.2 二次探测（Quadratic Probing）

线性探测每次探测的步长是 1，二次探测的步长则为“二次方”。

1.3 双重散列（Double hashing）

使用一组散列函数，当 hash1(key) 冲突时再用 hash2(key)……直至找到空闲的位置。

装载因子计算公式：

散列表的装载因子 = 填入表中的元素个数 / 散列表的长度

装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。

2. 链表法

该方法更为常用。在散列表中，每个“桶（bucket）”或“槽（slot）”会对应一条链表，所有散列值相同的元素都会放到相同槽位对应的链表中，如图所示：

image.png

二者对比

1. 当数据量比较小、装载因子小的时候，适合采用开放寻址法（例如 Java 中的 ThreadLocalMap）。

2. 链表法比较适合存储大对象、大数据量的散列表；而且比开放寻址法更灵活、支持更多的优化策略（比如用红黑树替代链表，JDK 1.8 中 HashMap 的实现）。

PS: 由于链表要存储指针，当存储比较小的对象时内存消耗可能会翻倍；而存储大对象，即存储对象的大小远大于一个指针的大小（4 或 8 个字节）时，链表中指针的内存消耗可以忽略了。

小结

1. 跳表

跳表是在链表的基础上增加索引层来提高查找效率，但同时也增加了存储空间开销，利用“空间换时间”的思想。

常见应用场景：Redis 中的有序集合。

2. 散列表

两个核心问题：散列函数设计和散列冲突解决。

散列冲突常用的解决方法有两种：开放寻址法和链表法。

散列函数设计的好坏决定了散列冲突的概率，也决定了散列表的性能。

数据结构与算法（三）

树

数据结构中的树（Tree）与生活中常见的树有些类似，可以类比为生活中的树倒过来。示意图：

image.png

相关概念

每个元素称为「节点」，用来连线相邻节点之间的关系叫作「父子关系」。示意图：

image.png

其中，A 节点是 B 节点的「父节点」，B 节点是 A 节点的「子节点」。B、C、D 节点有同一个父节点 A，它们互称为「兄弟节点」。没有父节点的节点（E）称为「根节点」，没有子节点的节点（G、H、I、J）称为「叶子节点」或「叶节点」。

高度、深度和层

1. 节点的高度（Height）：节点到叶子节点的最长路径；

2. 节点的深度（Depth）：根节点到这个节点所经历的边的个数；

3. 节点的层数（Level）：节点的深度 + 1；

4. 树的高度：根节点的高度。

示意图：

image.png

二叉树

树的结构有多种，其中最常用的是二叉树（Binary Tree）。

二叉树的每个节点最多有两个“叉”，也就是两个节点，分别为「左子节点」和「右子节点」。如图所示：

image.png

1. 左边的二叉树：一棵普通的二叉树；

2. 中间的二叉树：叶子节点全都在最底层，而且除了叶子节点外，每个节点都有左右两个子节点，称为「满二叉树」；

3. 右边的二叉树：叶子节点都在最底下两层，且最后一层的叶子节点都靠左排列，除了最后一层，其他层的节点个数都达到最大，称为「完全二叉树」。

二叉树的存储

两种方式：基于指针（或引用）的链式存储法，基于数组的顺序存储法。

链式存储法：每个节点有三个字段，其中一个存数据，另外两个分别为指向左右子节点的指针。如图所示：

image.png

顺序存储法：根节点存储在下标为 *i *= 1 的位置，左子节点下标为 2 * i = 2， 右子节点下标为 2 * i + 1 = 3，以此类推。如图所示：

image.png

值得注意的是，这里存储的是一颗完全二叉树，因此它在数组中只有第一个位置为空。若不是完全二叉树，则其存储结构如下：

image.png

数组中为空的位置就很多，这样会浪费很多存储空间。

二叉树的遍历

二叉的遍历就是循环打印出二叉树中的所有节点。经典的方法有三种，分别为：前序遍历、中序遍历和后序遍历。其中的前、中、后指的是节点与它的左右子节点遍历打印的先后顺序，即：

1. 前序遍历：本节点 --> 左子节点 --> 右子节点；

2. 中序遍历：左子节点 --> 本节点 --> 右子节点；

3. 后序遍历：左子节点 --> 右子节点 --> 本节点。

可以看到，前、中、后就是本节点在遍历中的顺序。示意图：

image.png

二叉查找树

二叉查找树（Binary Search Tree）是二叉树中最常用的一种类型，又称「二叉搜索树」，它支持快速查找、插入、删除一个数据。

结构特点

二叉树中的任一节点，其左子树中每个节点的值，都小于该节点的值；右子树中每个节点的值都大于该节点的值。示意图：

image.png

查找

查找步骤：

1. 先将要查找元素的值与根节点的值比较，若相等则返回；

2. 若小于根节点的值，则在左子树中递归查找；

3. 若大于根节点的值，则在右子树中递归查找。

查找过程示意图：

image.png

插入

插入过程与查找的比较过程有些类似，操作示意图如下：

image.png

删除

相比查找和插入，删除过程略微复杂一些。主要分为三种情况：

1. 待删除的节点无子节点：直接删除（下图的节点 55）；

2. 待删除的节点有一个子节点：将待删除节点的父节点指向待删除节点的子节点（下图的节点 13）；

3. 待删除的结点有两个子节点：需要先找到待删除节点的右子树中的最小节点，用它替换要删除的节点，然后再删除该最小节点（下图的节点 18）。

这三种情况的删除操作示意图如下：

image.png

二叉树&散列表

1. 散列表中的数据是无序的；二叉查找树中序遍历可在 O(n) 时间复杂度内输出有序的数据序列；

2. 散列表的扩容比较耗时，散列冲突时性能不稳定；平衡二叉查找树的性能稳定在 O(logn)；

3. 散列表构造比二叉树复杂不少（散列函数设计、冲突解决、扩容等）；二叉树只需考虑平衡性问题，且解决方案比较成熟、固定。

堆

堆（Heap）是一种特殊的树，它满足以下结构特征：

1. 堆是一个完全二叉树；

2. 堆中每个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。

其中，每个节点值都大于等于子树中每个节点值的堆称为「大顶堆」，小于等于树中每个节点值的堆称为「小顶堆」。示意图：

image.png

其中 1、2 为大顶堆，3 为小顶堆，4 不是堆（不是完全二叉树）。

存储

前面分析了二叉树的存储方法有两种：链式存储和顺序存储，而顺序存储比较适合完全二叉树。堆的顺序存储示例如下：

image.png

堆化

当向堆中插入元素、或从堆中删除元素时，可能会导致堆不满足其结构特点。因此需要对其进行调整使其重新满足堆的特性，该过程称为堆化（heapify）。

堆化有两种方式：从下往上和从上往下。

从下往上堆化示意图（插入节点 22）：

image.png

从上往下堆化示意图（删除节点 33）：

image.png

注意：这样操作会使堆不满足完全二叉树的特性。

如果转换思路，把最后一个节点放到堆顶，然后再进行从上到下堆化，如图所示：

image.png

这样就不会出现“数组空洞”，又能满足完全二叉树的特性。

应用场景

堆的几个非常重要的应用场景：优先级队列、Top K 问题、求中位数。

小结

1. 数据结构中的树可以类比生活中常见的树倒过来。其中二叉树最常用，二叉树有两种特殊的情况：满二叉树和完全二叉树；

2. 二叉树的遍历方式有三种：前序、中序和后序遍历；在二叉树中，二叉查找树最常用，可以快速查找、插入、删除一个元素；

3. 堆是一种特殊的树：它是完全二叉树；且每个节点的值都大于等于（或小于等于）子树中每个节点的值（分别为大顶堆和小顶堆）。

数据结构与算法笔记（四）

平衡二叉树

二叉查找树支持快速插入、删除、查找操作，各个操作时间跟树的高度成正比，理想情况下，时间复杂度为 O(logn)。但是，在极端的情况下，二叉树会退化成链表（比如按顺序插入一组数据），时间复杂度会退化到 O(n)。

为了解决这种问题，就有了平衡二叉树，红黑树就是平衡二叉树中的一种。

平衡二叉树的严格定义：二叉树中任意一个节点的左右子树的高度差不能大于 1。示意图如下：

image.png

最先被发明的平衡二叉查找树是 AVL 树，它严格符合上述定义，是一种高度平衡的二叉查找树。但是，很多平衡二叉查找树并未严格符合上述定义，比如经典的红黑树。

PS: 平衡二叉树发明的初衷是为了解决普通二叉查找树在极端情况下退化成链表，插入、删除等操作复杂度增加的问题。而“平衡”的意思就是让整棵树的左右子树比较均衡，从而使整棵树的高度相对低一些，插入、删除等操作效率更高。因此，尽管有些二叉树没有严格符合平衡二叉查找树的定义，但只要树的高度没有比 logn 大很多，仍然可以认为它是一棵平衡二叉树。

红黑树

红黑树（Red-Black Tree），简称 R-B Tree，它的每个节点都有颜色（红与黑）属性，是“出场率”很高的二叉树，它是一种不严格的平衡二叉树。示意图如下：

image.png

红黑树需要满足以下几个约束：

1. 节点是红色或黑色；

2. 根节点是黑色；

3. 所有叶子节点都是黑色（叶子是 NIL 节点）；

4. 每个红色节点必须有两个黑色的子节点（从每个叶子到根节点的所有路径上不能有两个连续的红色节点）；

5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

PS: 上面说的“叶节点”或“NIL节点”，不包含数据而只是充当树在此结束的指示，绘图中通常被省略。

平衡性调整

红黑树在插入或删除节点的过程中，上述第 3、4 点性质可能会被破坏，为了让它重新保持红黑树的性质，需要进行平衡性调整。

平衡性调整操作主要包括旋转（结构调整）和着色（红黑转换），其中旋转又分为左旋（rotate left）和右旋（rotate right）两个操作，左旋指的是围绕某个节点的左旋，右旋同理。左旋和右旋的操作示意图如下：

image.png

插入操作

红黑树规定，插入的节点必须是红色的。插入的情况分为多种，下面两种情况无须进行旋转操作：

1. 若插入节点的父节点是黑色的，则无需操作，仍满足红黑树的定义；

2. 若插入节点是根节点，那么直接将它变为黑色即可。

除此之外的其他情况都会违背红黑树的定义，需要进行平衡性调整（旋转和着色）。

case1

关注节点为 a，它的叔叔节点 d 为红色。则进行如下操作：

1. 将 a 的父节点 b、叔叔节点 d 的颜色都设置为黑色；

2. 将 a 的祖父节点 c 的颜色设置为红色；

3. 关注节点变成 a 的祖父节点 c；

4. 跳到 case2 或 case3。

操作示意图如下：

image.png

case2

关注节点是 a，它的叔叔节点 d 是黑色，a 是其父节点 b 的右子节点。则进行如下操作：

1. 关注节点变成 a 的父节点 b；

2. 围绕 b 左旋；

3. 跳到 case3。

操作示意图如下：

image.png

case3

若关注节点是 a，它的叔叔节点 d 是黑色，a 是其父节点 b 的左子节点。则进行如下操作：

1. 围绕 a 的祖父节点 c 右旋；

2. 将 a 的父节点 b、兄弟节点 c 的颜色互换。

操作示意图如下：

image.png

小结：插入后的修复操作是一个向 root 节点回溯的操作过程，一旦涉及的节点都符合了红黑树的定义，则修复操作结束。之所以会向上回溯是由于 case1 操作会将父节点、叔叔节点和祖父节点的颜色进行互换，可能会导致祖父节点不平衡，此时需要对祖父节点进行修复，以此类推。

删除操作

若删除的是叶子节点就直接删除；若不是叶子节点，会用对应的中序遍历的后继节点来顶替要删除的节点的位置。

删除操作的总体思想：从兄弟节点借调黑色节点使树保持局部的平衡，如果局部的平衡达到了，就看整体的树是否平衡，若不平衡则继续向上追溯调整。

删除节点的平衡性调整大概分为四种情况（对称情况下的操作类似）：

case1

待删除节点的兄弟节点是红色。则进行如下操作：

1. 围绕父节点 A 进行左旋；

2. 将父节点 A 和祖父节点 C 颜色互换；

3. 跳转到 case2、case3 或 case4。

操作示意图如下：

image.png

case2

待删除节点的兄弟节点是黑色，且兄弟节点的子节点都是黑色。则进行如下操作：

1. 将兄弟节点 C 的颜色设置为红色；

2. 关注节点上溯为父节点 A。

操作示意图如下：

image.png

case3

待调整节点的兄弟节点是黑色，且左子节点是红色、右子节点是黑色（兄弟节点在右边的情况。若兄弟节点在左边，就是右子节点是红色，左子节点是黑色）。则进行如下操作：

1. 围绕兄弟节点 C 右旋；

2. 将节点 C 和 D 变换颜色；

3. 跳到 case4。

操作示意图如下：

image.png

case4

待调整节点的兄弟节点是黑色，且右子节点是红色、左子节点是黑色（兄弟节点在右边的情况。若兄弟节点在左边，就是左子节点是红色、右子节点是黑色）。则进行如下操作：

1. 围绕父节点 A 进行左旋；

2. 删除 B 节点。

操作示意图如下：

image.png

删除修复操作是针对删除黑色节点才有的，需要从兄弟节点上借调黑色的节点过来，如果兄弟节点没有黑色节点可以借调的话，就只能向上追溯。

小结

红黑树是一种常见的平衡二叉树，结构稍微复杂了点，主要体现在插入和删除的时候需要进行旋转和变色的平衡性调整操作。

在 JDK 1.8 的源码中，TreeMap 和 HashMap 都用到了红黑树