数据结构与算法

按照索引，查询/遍历速度快

优点

大小固定，创建后无法扩容

只能存储一种类型数据

添加删除速度慢

缺点

频繁查询，数据量不大，少增删操作

适用场景

数组

特殊的线性结构，只能在一端进行操作

先进先出

特点

常用于实现递归方面的操作；如：斐波那契数列

栈

特殊的线性结构，一端操作数据入队，一端操作数据出队

先进先出特点，多线程阻塞队列中，常使用

队列

链表是物理存储单元上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现

单向链表

双向链表

循环链表

根据指针指向分类

不需要初始化容量，可以任意加减元素；加减元素只需要更改前后指针

含有大量指针域（每个节点数据都有），内存消耗高；遍历元素需要遍历链表，比较耗时

数据量少，频繁增删元素

链表

概念

结构

BF算法

KMP算法

匹配算法（字符串匹配算法）

串

线性数据结构

对于给定的一组记录，初始时假定第一个记录自成一个有序的序列，其余的记录为无序序列；

从第二个记录开始，按照记录的大小依次将当前处理的记录插入到其之前的有序序列中，直至最后一个记录插入到有序序列为止。

直接插入排序

把记录按步长 gap 分组，对每组记录采用直接插入排序方法进行排序。随着步长逐渐减小，所分成的组包含的记录越来越多，当步长的值减小到 1 时，整个数据合成为一组，构成一组有序记录，则完成排序。

希尔排序（缩小增量排序）

插入排序

冒泡排序

选择一个基准数，通过一趟排序将要排序的数据分割成独立的两部分；其中一部分的所有数据都比另外一部分的所有数据都要小。然后，再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

使用分治法策略

快速排序

交换排序

对于给定的一组记录，经过第一轮比较后得到最小的记录，然后将记录与第一个记录的位置进行交换；接着对不包括第一个记录以外的其他记录进行第二轮排序，得到最小的记录并与第二个记录进行位置交换；重复该过程，直到进行比较的记录只有一个为止。

简单选择排序

堆排序

选择排序

是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案\"修补\"在一起，即分而治之)递归深度为log2n

归并排序是稳定排序，它也是一种十分高效的排序，能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法，就是归并排序的优化版本。从上文的图中可看出，每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。

归并排序

不从最高位开始排序的原因，主要是出于空间的考虑，因为如果按照最高位开始排序，则之后的地位都需要创建一个完整的基数排序空间，空间占用量成指数增长

8

基数排序

将一个有向无环图(Directed Acyclic Graph简称DAG)进行排序进而得到一个有序的线性序列。

拓扑排序

排序

顺序查找

二分查找

分块查找

线性表查找

二叉树查找

AVL树查找

B-树

B+树

树形查找

拉链法

冲突解决

哈希查找

查找

图论算法

贪婪算法

分治算法

动态规划

随机化算法

回溯算法

算法

自顶向下伸展树

红黑树

确定性跳跃表

AA树

treap树

k-d树

配对堆

高级数据结构

根据键值（key/value）进行访问的数据结构；通过key/value来映射到集合中的元素，这样可以很快找到集合中的元素

散列表

堆中某个节点总是不大于父节点

最大堆（大根堆）

堆中某个节点总是不小于（最小堆）父节点

最小堆（小根堆）

定义

堆的常用结构使用二叉树表示，不特指的话为一棵完全二叉树，通常不必用指针，而是用数组来实现堆的存储堆：数组起始单元为1，在数组中按照完全二叉树的层序存储，根节点放在下标为1的位置中对于下标为i的结点，其父结点的下标为i/2取整，反过来，i的左右结点分别是2i和2i+1

性质

二叉堆

斐波那契堆

常用堆

例如，在一个最大堆中，最大的那一个元素总是位于 index 0 的位置，但是最小的元素则未必是最后一个元素。--唯一能够保证的是最小的元素是一个叶节点，但是不确定是哪一个。

堆的根节点中存放的是最大或者最小元素，但是其他节点的排序顺序是未知的。

可以使用普通树来模拟堆，但是那对空间是极大的浪费。

并不是每一个最小堆都是一个有序数组！要将堆转换成有序数组，需要使用堆排序。

注意

堆仅仅使用一个数据来存储数组，且不使用指针

实现

如果一个节点比它的父节点大（最大堆）或者小（最小堆），那么需要将它同父节点交换位置。这样是这个节点在数组的位置上升

shiftUp()

如果一个节点比它的子节点小（最大堆）或者大（最小堆），那么需要将它向下移动。这个操作也称作“堆化（heapify）”

shiftDown()

基本操作

构建优先队列

因为堆有序，常用来做数组排序——堆排序

常见应用

堆

1.每个节点有零个或多个子节点2.没有父节点的节点称为根节点；3.每一个非根节点有且只有一个父节点；4.除了根节点外，每个子节点可以分为多个不相交的子树；

一个节点含有的子树的个数称为该节点的度

节点的度

度为0的节点称为叶节点

叶节点/终端节点

度不为0的节点

非终端节点/分支节点

从根开始定义起，根为第1层，根的子节点为第2层，以此类推

节点的层次

树中节点的最大层次

树的高度或深度

由m（m>=0）棵互不相交的树的集合称为森林

森林

术语

父左右

前序遍历

左父右

中序遍历

左右父

后续遍历

从根节点开始，一层层往下

层序遍历

遍历方式

概述

1.每个节点最多有两个子树，节点的度最大为2；2.左子树和右子树是有顺序的，顺序不能颠倒；3.即使某个节点只有一个子树，也要区分左右节点

第i层至多有2^(i-1)个结点;深度为k的二叉树至多有2^k-1个结点

二叉树是数组和链表的折中方案，增加、删除速度都快，并且对查询也有算法优化；在动态处理大批量数据的时候很有用

一棵深度为k且有2^k-1（2的k次幂减1）个结点的二叉树称为满二叉树

满二叉树

深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应

完全二叉树

二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；它的左、右子树也分别为二叉排序树。

对于一般的二叉搜索树（Binary Search Tree），其期望高度（即为一棵平衡树时）为log2n，其各操作的时间复杂度O(log2n)同时也由此而决定；在某些极端的情况下（如在插入的序列是有序的时），二叉搜索树将退化成近似链或链，此时，其操作的时间复杂度将退化成线性的，即O(n)。原因：由于在删除时，我们总是选择将待删除节点的后继代替它本身，这样就会造成总是右边的节点数目减少，以至于树向左偏沉。这同时也会造成树的平衡性受到破坏，提高它的操作的时间复杂度

存在的问题

它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。（注：平衡二叉树应该是一棵二叉排序树）

n个结点的AVL树最大深度约1.44log2n

查找、插入和删除在平均和最坏情况下都是O(logn)

增加和删除可能需要通过一次或多次树旋转来重新平衡这个树；这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多

左左情况，单旋转自平衡处理

单旋转

左左/右右

子主题

多旋转

左右/右左

AVL树的自平衡操作——旋转

二叉树，B树

AVL树

1.满足AVL树的性质；2.节点可以存放1个或2个元素；3.每个节点有两个或三个子节点。

2-3树本质上也是一棵搜索树，和二叉搜索树的区别在于，2-3的节点可能存放 2 个元素，而且每个节点可能拥有 3 个子节点。

2-3树存在以下两种节点：2-节点（存在两个子节点）和3-节点（存在3个子节点）

2-3树

自平衡二叉查找

可以在O(logn)时间内做查找，插入和删除

在二叉查找树强制的一般要求以外增加：1.节点是红色或黑色；2.根是黑色；3.所有叶子都是黑色（叶子是NIL节点）；4.每个红色节点下有两个黑节点（每个叶子到根的路径上不能有两个连续的红色节点）；5.从任意节点到每个叶子节点的简单路径上有相同节点的黑色节点。

30张图带你彻底理解红黑树

红黑树（RB-tree）

SBT

Splay

Treap

自平衡树

自平衡二叉搜索树

(1) 每个节点或者是黑色，或者是红色这是红黑树的定义，没什么好说的。(2) 根节点是黑色根节点要么对应2-3树的2-节点或者3-节点，而这两者的根节点都是黑色的，因而根节点必然是黑色。(3) 每个叶子节点是黑色注意，这里的叶子是指的为空的叶子节点

二叉排序树

Treap（树堆）

二叉树

是一种平衡的多路查找树。B-树的阶是所有结点的孩子结点树的最大值。B树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树（查找路径不只两个），数据库索引技术里大量使用者B树和B+树的数据结构

一棵m阶B-树，或为空树，或为满足下列特性的m叉树：1）树中每个结点至多有m棵子树；2）若根节点不是叶子节点，则至少有两棵子树；3）除根之外的所有非终端结点至少有[m/2]（）向上取整）棵子树；4）所有的非终端结点中包含下列信息数据：（n，A0，K1，A1，K2，A2，…，Kn，An），       n：为结点中的关键字树，       A：为指向子树根结点的指针，       K：为关键字，且Ai-1所指子树中所有结点的关键字均小于Ki，An所指子树中所有结点的关键字均大于Kn；5）所有的叶子结点都出现在同一层次上，并且不带信息   （可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）

规则

多叉平衡查找树

从B树、B+树、B*树谈到R 树

平衡二叉树、B树、B+树、B*树 理解其中一种你就都明白了

参考

B+树是B树的一个升级版，相对于B树来说B+树更充分的利用了节点的空间，让查询速度更加稳定，其速度完全接近于二分法查找

1）B+跟B树不同B+树的非叶子节点不保存关键字记录的指针，只进行数据索引，这样使得B+树每个非叶子节点所能保存的关键字大大增加；2）B+树叶子节点保存了父节点的所有关键字记录的指针，所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样；3）B+树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。4）非叶子节点的子节点数=关键字数（来源百度百科）（根据各种资料 这里有两种算法的实现方式，另一种为非叶节点的关键字数=子节点数-1（来源维基百科)，虽然他们数据排列结构不一样，但其原理还是一样的Mysql 的B+树是用第一种方式实现）;

当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针。

分裂

数据库索引

应用场景

B*树是B+树的变种，相对于B+树他们的不同之处如下：（1）首先是关键字个数限制问题，B+树初始化的关键字初始化个数是cei(m/2)，b*树的初始化个数为（cei(2/3*m)）（2）B+树节点满时就会分裂，而B*树节点满时会检查兄弟节点是否满（因为每个节点都有指向兄弟的指针），如果兄弟节点未满则向兄弟节点转移关键字，如果兄弟节点已满，则从当前节点和兄弟节点各拿出1/3的数据创建一个新的节点出来；

在B+树的基础上因其初始化的容量变大，使得节点空间使用率更高，而又存有兄弟节点的指针，可以向兄弟节点转移关键字的特性使得B*树额分解次数变得更少；

当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针。

B*树分配新结点的概率比B+树要低，空间使用率更高。

B*树

B树（B-树）

R树

在叶子结点和权重确定的情况下，带权路径长度最小的二叉树，也被称为最优二叉树。

哈夫曼编码

典型运用

什么是哈夫曼树

哈夫曼树

前缀树，典型运用：关键字过滤

trie 树（字典树）

常见树

树

图是由结点的有穷集合V和边的集合E组成。在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。

定点

边上带权重的为带权图

边

有向图

无向图

按照顶点方向划分

占用空间太大

邻接矩阵

图的每一个顶点都是一个链表的头节点，其后连接着该顶点能够直接达到的相邻顶点

邻接表

每一个顶点作为链表的头节点，后继节点所存储的是能够直接达到该顶点的相邻顶点

逆邻接表

十字链表

邻接表+逆邻接表=十字链表

邻接多重表

边集数组

图的表示

利用栈实现

深度优先遍历

利用队列实现

广度优先遍历

遍历

最小生成树

广度优先算法

无权图

迪杰斯特拉算法

带权图

佛洛依德算法

多源最短路径

最短路路径

关键路径

应用

漫画：什么是 “图”？（修订版）

图

数据结构及算法