时间复杂度，空间复杂度

非线性结构

二叉树

二叉树的性质

深度为k的二叉树最多结点数目：深度为k即有k层，第k层的最大结点数等于2^(k-1)，经过等比数列求和后可得到深度为k的二叉树最多有(2^k)-1个结点，这就好比k位二进制能标识的最大的数为(2^k)-1，8位二进制数能表示的最大的数是2^8-1=127。
一条边出现表示一个新的结点（除了根节点）：结点数目=边数+1
边数 = 出度为1的结点数目+2*出度为2的结点数目*
结点总数=出度为1的结点数目+出度为2的结点数目+叶子结点数
结点数目=边数+1=（出度为1的结点数目+2*出度为2的结点数目）+1，即不需要确定叶子结点的数目，也可以得出结点总数
出度为2的结点数 + 1 = 叶子结点数

思路：

思考边数和结点数的关系
思考边数和结点出度之间的关系

二叉树的遍历

先序遍历(Preorder)

访问顺序：根节点 -> 左子树 -> 右子树

访问根节点。
递归地对左子树进行先序遍历。
递归地对右子树进行先序遍历。

假设有一棵二叉树如下：

    A
   / \
  B   C
 / \
D   E

先序遍历的结果为：A, B, D, E, C

中序遍历(Inorder)

访问顺序：左子树 -> 根节点 -> 右子树

递归地对左子树进行中序遍历。
访问根节点。
递归地对右子树进行中序遍历。

假设有一棵二叉树如下：

    A
   / \
  B   C
 / \
D   E

中序遍历的结果为：D,B,E,A,C

后序遍历（Postorder）

访问顺序：左子树 -> 右子树 -> 根节点

递归地对左子树进行后序遍历。
递归地对右子树进行后序遍历。
访问根节点。

假设有一棵二叉树如下：

    A
   / \
  B   C
 / \
D   E

后序遍历的结果为：D,E,B,C,A

结论

无右孩子的二叉树，先序序列和后序序列正好相反
1
2
3
4
5
A
/
B
/
D
只有根结点的二叉树或非叶子结点只有右子树的二叉树

常见名词解释

完全二叉树：即除了最后一层之外，每一层都被完全填满，并且最后一层尽可能靠左填充。

    A
   / \
  B   C
 / \  /
D   E F

满二叉树：每层结点都是满的

    A
   / \
  B   C
 / \  /\
D   E F G

二叉排序树搜索树查找树

要求左子树的所有结点的值<根结点的值<右子树所有结点的值

背景

二分查找一般要求线性存储，插入删除元素的时间复杂度为O(n)；而使用二叉查找树就能实现插入和删除的时间复杂度为O(logn)

构建二叉搜索树

同一批数字，按不同的方式排列，构建出来的二叉树可能是不同的，但是都必须满足规则，且中序遍历的序列都是有序的
如果这批数字本身就是有序的，那么构建出的二叉树就是链表，查找的时间复杂度变为O(n)

删除结点

如果删除的是叶子结点直接删除
否则从这个结点的左子树中找出最大的或者右子树最小的作为新的根。

平衡二叉树

背景

构建二叉搜索树有时候会出现链表，使得查找的时间复杂度变高；需要寻找一种方法解决这个问题

平衡二叉树，所有结点的(左子树高度-右子树高度)的绝对值<=1（平衡因子=|左子树高度-右子树高度|）

哈夫曼树

哈夫曼编码

能实现在不出现歧义的情况下实现最短编码

哈夫曼编码和二叉树有啥关系？利用二叉树实现哈夫曼编码，这棵树叫做哈夫曼树

构建哈夫曼树

确定结点的值：把每个元素归为一个节点，结点的值是元素的个数
合并结点：找出值最小的两个节点，合并为一个新的父节点，这个父节点的值是两个节点值的和
合并产生的节点继续参与拼接，重排队列，依此类推，从下往上构建一株哈夫曼树
给路径编号，得到该结点的编号；左边路径编号为0，右边路径编号为1（其实是任意的），某个节点的编号等于根节点到该节点路径编号的拼接

哈夫曼树的特点

结点的度只能是0，2；因为二叉树是叶子结点或者非叶子结点两两合并形成的，度为2的结点都是合并形成的，叶子结点是原来就有的（编码序列）；由这个特点很容易得到叶子结点和非叶子结点的关系
叶子节点数-1=非叶子结点数；边数+1 = 结点数 = 度为2的非叶子结点+叶子结点 = (2*度为2的非叶子结点数)+1，推导出叶子结点数等于非叶子结点数+1
也就是说如果需要给n个不同的元素编码，也就是有n个叶子结点，最终构建的哈夫曼树会有2*n-1个结点

带权路径长度

所有叶子节点的路径长度*节点的值的和，其实就是最终编码长度

如何实现最短？

个数越多的元素越晚被合并，到根节点的路径越短，编号越短；正因个数越多的编码越短，就能实现总编码序列最短。

如何实现无起歧义？

没有前缀就没有歧义（某个元素的编码不是任何一个元素编码的前缀部分），因为从根结点到任意叶子节点所经过的路径，不会是根结点到其他叶子节点所经过的路径的前缀，因为叶子结点之后不会再有结点。

散列表（哈希表）

构造

取余法

解决冲突

线性探测法：发生冲突时，顺着冲突地址的下一单元查找空位，如果表尾也没有空位，则从表头开始重新查找
二次探测法：d=1,-1,2^2,-2^2,3^3,-3^3,…….依此类推，往两边查找，所谓二次探测其实是指的是两个方向
伪随机数列：d=伪随机数，说白了就是随机选一个
链地址法：每个地址上都有一个链表，发生冲突把后添加的元素挂载链表后面。

装填因子

装填因子 = 装填元素个数 / 散列表长度

图

多对多的一种数据结构

名词解释

邻接：描述两个结点之间的关系，他们之间有边或者弧相连
网：有权图
连通图：在无向图中，如果从任意一个节点出发都可以到达图中的任何一个其他节点，则该图被称为连通图。
强连通图：在有向图中，如果对于每一对不同的顶点u和v，既存在从u到v的有向路径也存在从v到u的有向路径，则称此图为强连通图。；有n个顶点的强连通图最多有n(n-1)条边，也就是每两个结点间都有直接的2条边；最少有n条边，就是一个环。

存储方法

邻接矩阵

用一个一维数组存储结点，记录下标和结点的对应关系
用一个二维数组表示两结点之间的邻接关系，比如arr[i][j]=1表示有条边从i结点指向j结点，如果等于0就表示没有

结论：

无向图的邻接矩阵是对称的
无向图结点i的度等于arr[i]数组的和
有向图结点i的出度，等于arr[i]的和，入度等于对应列arr[x][i]的和
arr[i][j]=x表示有条边从i结点指向j结点，如果等于无穷大就表示没有，x表示该边的权值

优缺点

增删结点麻烦；空间复杂度和边数无关，只和结点数有关，可能浪费空间

邻接表

用一个一维数组记录下标与结点的关系（这一步邻接矩阵也需要，本质就是创建一个字典）；按编号顺序将顶点数据存储在一维数组中;
存储空间大小和结点数，边数都有关，因为节点数越多，存储下标与结点的关系的一维数组的长度也越长。
方便计算出度；节约稀疏图的空间
邻接表不唯一，每个链表后续结点的顺序都是可变的

逆邻接表

结构和邻接表相同，但是表示的含义不同，链表的第一个结点表示的是被指向的结点，后续结点都是指向这个结点的结点。

方便计算入度；节约稀疏图的空间

区别

对于任意无向图有向图，邻接矩阵是唯一的，但是邻接表不是唯一的，同样的逆邻接表也是不唯一的。

图的遍历

从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历，它是图的基本运算。

存在结点重复访问的问题，因为图中出现环是很正常的，解决方法是使用辅助数组，记录每个结点的状态

深度优先遍历

先序遍历；访问的顺序不是固定的，是随机的

广度优先遍历

从图的某一结点出发，首先依次访问该结点的所有邻接点Vi, Vi2....Vi，再按这些顶点被访问的先后次序，依次访问与它们相邻接的所有未被访问的顶点；重复此过程，直至所有顶点均被访问为止，一般通过队列实现。

图的应用

生成树

图中所有点均由边连接在—起，但不存在回路的图，简单的来说生成树就是不存在回路的连通图。
一个图可以有多个生成树；生成树是图的最小连通子图
树是图的特例，不存在孤立的结点，不存在环；有n个结点，n-1条边；
可以通过深度/广度优先遍历来构造，每个结点只会被访问一次。

最小生成树

前提是图的各边有权值，最小指的是路径上各边权值和最小；最小生成树不一定唯一（ok，生成树和最小生成树都不是唯一的）

如何构造（本质都是用了贪心算法）：

普利姆算法：
- 选择点；起初选择权值最小的那条边对应的2个结点，再查找这两个节点中的那条和其他结点权值最小的边，纳入这个边另一侧的结点，依此类推。
- 时间复杂度O(N*2)；n为结点数，因为所有已包含的结点都要查看是否与所有未包含的结点之间存在权值最小的边;适合稠密图
克鲁斯卡尔算法：
- 选择边；每次选择一条权值最小的边，但是如果选择了不满足连通图，则选择次小的边，依此类推
- 时间复杂度O(eloge)e为边数；只需要对所有的边进行排序，排序的时间复杂度为eloge；适合稀疏图

最短路径

区别于最小生成树，不需要包含全部结点。

如何寻找：

迪杰斯特拉算法：求单个结点到所有其他结点的最短路径，实话只了解思想不懂得原理和算法实现很容易忘
弗洛伊德算法：求全部结点到其他结点的最短路径

区别与联系

第一步都是记录结点与其他结点的直接距离，对于不可达的结点距离设为无穷远
迪杰斯特拉算法算法后续选择距离最近的结点纳入；已确定最小距离的结点，然后重新计算这个结点加入后，源结点到其他结点的最小距离，然后再纳入距离最近的结点，依此类推，时间复杂度为O(N^2)
弗洛伊德算法纳入结点的顺序是随意的，一般按照编号纳入，每纳入一个结点就重新计算每个源节点与其他结点的最小距离。

有向无环图

aov网：拓扑序列
- 结点表示活动，边表示制约关系，不能存在回路
- 拓扑排序：把一个aov图输出为一个线性序列（拓扑序列）每个结点的先后顺序不变；可以通过广度优先遍历（队列）实现，必须从没有入度的结点开始，用来检测aov图中是否存在回路。
aoe网：关键路径
- 边表示活动；边的权值表示活动持续的时间，结点表示事件（既可以表示前一个事件的结束，又可以表示下一个事件的开始）
- 入度为0的结点也叫源点，出度为0的结点也叫汇点
- 关键路径——源点到汇点路径长度最长的路径。路径长度——路径上各活动持续时间之和。

线性结构

数组

定义：数组是一种固定大小的线性结构，它将元素存储在一个连续的内存位置中；

优点：数组可以通过索引直接访问其元素，因此访问速度快

缺点：插入和删除操作通常需要移动大量元素，增删操作的时间复杂度是O(n)

链表

链表中元素的存储是不连续的，每个结点包含数据和对下一个结点的引用

增删元素快，查询元素慢

单循环链表

单循环链表，即单个方向循环的链表

由图可知，单循环链表删除首结点的操作是:

1
2
3

const first = Q->rear->next
Q->rear->next = first.next
first.next = null//断开连接

栈

先进后出的线性结构

队列

先进先出的线性结构

存储结构

顺序存储（数组）
链式存储（链表）

指针

front指向队头的元素，rear指向下一个空地址，起初这两个指针的指向是相同的。

入队一个元素，rear++；出队一个元素front--，可以看出front始终指向队列中最先入队的元素。

循环队列（顺序存储）

循环队列用来解决队列假满的问题，就是rear=maxsize，但是font!=0，此时虽然队列中还有空间，但是无法放入元素。

原理

在逻辑上实现循环，实际上存储结构还是数组
出队一个元素，头指针的指向改变：front=(front+1)%maxsize
入队一个元素，尾指针的变化：rear=(rear+1)%maxsize
这样好像是进出队列就没限制了，但是其实只要保证出队列的时候，是弹出front指针指向的元素就行。

判断非空

循环队列虽然能解决假满的问题，又引出一个新的问题，当front==rear时存在两种情况，队满和队空，无法判断具体是情哪种况。

解决办法：

设置一个标志位，记录元素个数
少用一个元素空间（一般是最后一位空间）：
- 这样能确保rear始终指向的是空的位置
- 队空：front==rear，因为rear始终指向空位置，所以如果front指向rear的时候，就是队空的时候
- 队满：(rear+1)%maxsize == front ，即尾指针的下一个位置就是头指针的位置，这个时候就记作队满
- 初始状态：front=rear=0，初始状态也是队空状态
- 判断元素个数：(rear+maxsize-front)%maxsize，如果rear本来就比front大，那么rear-front>0，加上maxsize求余的结果也不变，反之如果出现rear<front这种异常情况，给rear加上maxsize才能转化出rear原本的下标。

以后如果不是特别说明都认为循环队列少用一个元素空间

总的来说，我们通过循环队列和少用一个元素空间的方法，完美的解决了队列假满和front==rear时状态二义的问题。

链队（带头结点）

也是带有头尾两个指针，带有头结点，头节点不存储实际的数据

起初，两个指针都指向头节点即front=rear=new Node()，后续元素入队则rear.next = new Node()，rear = rear.next，front始终指向头节点。

我们也注意到，在用链表表示的队列中，尾指针rear指向的竟然是最后一个结点，而在用数组表示的队列中，rear指向的是下一个元素填入的位置，而不是最后一个元素…..

出队

const first = front.next(存储队首元素地址)
front.next = first.next(修改头节点的下一个结点)
first.next = null(断开队首元素与队列的连接)
一般情况下，元素出队只需要修改头结点，但如果链队只有一个结点，那么出队不仅要修改头结点，还要修改尾指针，让尾指针指向头节点。

入队

const last = rear
rear = new Node()
last.next = rear

注意

可以观察到，对于带头结点的队列，无论插入元素还是弹出元素，头指针(front)始终指向头节点。

串

零个或多个字符组成的有限序列，存储的是字符

名词解释

空串：长度为0的串

空白串：由空白字符组成的串，长度不为0

子序列：是主串中的字符集合，这些字符的相对顺序与在主串中相同，可以不连续。

子串：主串中任意个连续字符组成的子序列

子串位置：子串第一个字符在主串中的位置序号

真字串：不包含本身的子串

主串：包含子串的串

串的模式匹配算法

BF算法：暴力算法/简单匹配法
KMP算法

存储模式

顺序存储：结构存储密度高
链式存储结构：存储密度低，因为还要存储下一个节点的地址；操作方便

堆

堆在逻辑上是一种特殊的完全二叉树，分为大根堆和小根堆；大根堆指的是根节点比左右子节点的值大，小根堆反之，至于左右子节点的大小没有限制。

堆的实现

堆通常使用数组来实现，这样可以方便地进行索引操作。

在数组表示的堆中，对于任意节点 i（索引从 0 开始）：

根节点索引为i
左子节点的索引为 2i + 1。
右子节点的索引为 2i + 2。
父节点的索引为 (j - 1) / 2（向下取整）, j指的是左右子节点索引

建堆

自顶向下构建

自顶向下通常是指每次插入一个元素到堆的末尾，然后通过上浮{sift up）操作调整堆结构，保持堆的性质。假设有n个元素，则有大概有log(n)层（2^x-1=n，x是层数，得到x等于log(n+1)），对于每个插入到堆末尾的元素，最多上浮log(n)层，因为有n个元素，所以这种建立堆的方法的时间复杂度为n*log(n)

自底向上构建（也叫筛选法）

已知一串序列，从下到上，从左到右构建二叉树；
构建好了再从底部最后一个非叶子结点开始调整堆（下滤，意思就是每个非叶子结点都有可能被交换到下一层）；时间复杂度看似是O(n log n)，因为有大约n/2个结点可能需要下滤，每次下滤最多log(n)层，看似时间复杂度也是n*log(n)，实际可收敛到 **O(n)**，这个计算过程涉及到较为复杂的数学知识，暂且记住吧。

调整堆

下滤

适用于非叶子节点不符合堆序的情况，在筛选法建堆中常见，越靠近顶部的非叶子结点下滤的层数一般越多。
弹出堆顶元素，并用末尾元素替代堆顶元素时，适合使用这种方式调整堆。

上浮

在自顶向下构建堆中常见

应用

优先队列
- 队首元素永远是最大/最小的，每次弹出或者加入元素都会重新调整队列
- 弹出（下滤）和插入结点（上滤）维护的时间复杂度都为log2(N)
堆排序：通常用自底向上法（时间复杂度为O(n)）来初次构建堆，弹出堆顶元素；然后用末尾元素充当堆顶元素，进行下滤调整堆，需要调整堆n-1次，每次下滤操作的时间复杂度为O(log n)，每次调整好后再弹出堆顶元素，以此类推，总时间复杂度为:
O(nlog n)+O(n)

补充

在计算机科学中，“堆”也指代一种内存区域，用于动态分配内存，但这与作为数据结构的堆有所不同。
一棵二叉树，第1层最多有2^0个结点，第2层最多有2^1，第三层最多有2^2…..；每层最多有2^(n-1)个结点（n代表第几层）; 规律和2进制一样。
假设二叉树有n层（n位），结点数目最多为2^n-1，比如8位二进制能表示的最大数就是2^8-1=255

排序

直接插入排序

直接插入排序的基本思想是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入，逐步排序数组。这个过程就好比我们打扑克牌整理牌的过程。

时间复杂度

如果数组是逆序的，每个数都要和前面的所有的数进行比较，最坏时间复杂度为O(n^2);
如果本来就有序，只需要比较n-1次，不需要插入，时间复杂度为O(n)；
平均情况时间复杂度：O(n^2)，和选择排序，冒泡排序坐一桌

空间复杂度：直接插入排序只需要借助O(1)的辅助空间，基本上算是原地排序。

稳定性：直接插入排序是稳定的，当和前面有序的数进行比较的时候，遇到了相等的情况，把当前访问的数，插入到其后面。

数据结构合集 - 直接插入排序(算法过程, 效率分析, 稳定性分析)_哔哩哔哩_bilibili

希尔排序

插入排序的一个更高效的改进版本

步骤：

根据步长分为多个子表，步长为n就有n组子表
对每组子表进行直接插入排序
更改步长为n/2，即原来的一半，再对每组子表进行直接插入排序
依此类推，直至步长缩短为1，进行最后一次插入排序

冒泡排序

const arr = [2, 5, 3, 4, 6, 1]
 for (let i = 1; i < arr.length; i++) {
   for (let j = 0; j < arr.length - i; j++) {
     if (arr[j] > arr[j + 1]) {
       let temp = arr[j]
       arr[j] = arr[j + 1]
       arr[j + 1] = temp
     }
   }
 }
console.log(arr)

从右往左维护，遍历n-1遍
从第二个元素开始遍历，判断该元素是否小于前一个元素，如果是则交换
以此类推确保当前遍历位置的元素是遍历到的所有元素中最大的；下次遍历维护好的元素不参与比较
冒泡冒泡就是让最大的冒泡到最后面，重点在找最大的元素

时间复杂度：如果序列本身有序，则只走一趟，比较n-1次，不交换元素，时间复杂度为O(n)

简单选择排序

for (let i = 0; i < arr3.length - 1; i++) {
    for (let j = i + 1; j < arr3.length; j++) {
    }
 }

从左往右维护，遍历n-1遍；找出最小的元素，和第i个元素交换，第i个元素就是要维护的元素
比较次数与初始序列无关，时间复杂度和初始序列无关；
无论初始序列如何，每次遍历都要比较n-1，n-2, n-3,….,1次，总的比较次数为n(n-1)/2，时间复杂度为O(n^2)
算法的排序趟数与初始序列无关,就是要遍历n-1遍

快速排序

用到了递归的思想，用到了轴的思想，每次只确定一个元素的位置

每次都以第一个元素为轴，遍历所有其他元素，让所有比第一个元素小的元素在轴的左边，比第一个元素是大的元素在轴的右边，遍历完所有元素就能确定第一个元素该在哪个位置，每次遍历只能确定一个元素的位置，所以还需要递归轴左边的和轴右边的部分，确定所有元素的位置

时间复杂度：平均情况为nlogn，最坏情况n^2,最坏情况是数组本身就有序，每次快排都要比较n-1,n-2,….,1次，所以时间复杂度为n^2

空间复杂度：O(1)原地排序

堆排序

用到了二叉树的逻辑结构，对数组中的数据进行层次遍历

也是每次建堆都能等到最大的/最小的元素，就和选择排序每次能得到最小（最大）的元素一样，堆排序其实就是选择排序的优化

如果是升序排列则是构建大根堆，反之小根堆

时间复杂度：O(nlogn)，最好最坏情况都是，而且不占用额外空间，缺点是不稳定

空间复杂度：O(1)原地排序

归并排序

两有序并为1有序，利用了一个元素必然就是有序的这一特点作为递归出口
合并有序数组的算法实现也是一个重点，用到了分治的思想，分而治之，对一个数组排序的工作可以划分为多左半部分排序再对右半部分排序，再合并，当一部分划分到只有一个元素时候，这部分自然就是有序的了直接返回即可

时间复杂度：O(nlogn)，没有最坏情况，而且稳定没缺点就是需要额外空间（递归栈来维护）
空间复杂度：需要额外的空间，非O（1）

如何判断排序方法是否稳定

大小相同的元素排序后，前后顺序保持不变的就是稳定的

不稳定的排序算法

选择排序：比如：[4, 4, 2, 1]->[1,4,2,4]->[1,2,4,4]
希尔排序比如：[2, 2, 1, 3]->[2,1],[2,3]->[1,2],[2,3]->[1,2,2,3]
快速排序：可能不稳定
堆排序：可能不稳定

其他排序算法都是稳定的，口诀：一堆希尔快选

排序方法的选择

算法的时间复杂度与初始序列无关的是：选择排序、堆排序、归并排序

插入/删除的时间复杂度

假设有n个元素，则有n+1中插入方式，位置从左到右边分别移动n，n-1，….,0个元素，总共移动（1+n）*n/2次，平均每次插入移动n/2次，所以插入的时间复杂度是O(n)。删除同理。

二分查找次数

快速判断

假设有100个元素，最大查找次数为n，则有2^n>=100，n=6为64<100,n=7为128>100满足题意

详细过程

每查找一次都将区间减半，直到区间长度为1（对于每次查找的中间元素，我们都把它纳入下次查找区间，方便理解，虽然它不可能是要查找的元素，理应不存在这个区间）