一、概念
（一）它是干什么的？
对大规模的数据进行处理，提高操作效率。
- 时间复杂度
1.是干什么的
衡量一个算法的效率，看执行次数，数据总量（大规模数据）
不能只看时间决定：受电脑配置和偶然数据的影响，CPU调度是靠操作系统决定，我们无法控制。
2.执行次数y 和 数据总量x的关系
常见的时间复杂度：
(1)Y=ax+b -> y=x ->O(n) (例如遍历数组)
(2)Y=ax^2+bx-c -> y=x^2->O(n^2)
(3)Y=a -> O(1)
(4)Y=logax(a^x=y) -> O(logn)
时间复杂度：O(n^2)>O(n)>O(logn)>O(1)
O(1)是最理想时间复杂度，比如数组通过下标获取数组里的数据。
所以学算法就是为的把时间复杂度降低，提高计算机的效率.
（二）数据结构
1.数组
特点：数据紧紧挨着，是开辟的连续空间。根据数据类型占用的各自不一样。
数组为什么能通过下标进行获取？
比如arr数组存的是第一个数据的地址，不然找不到这个数组的未知。
[123456]+0*4B+4B
[123456]+1*4B+4B
[123456]+2*4B+4B
通过下标获取是O(1)的时间复杂度
通过遍历获取是O(n)的时间复杂度
计算机绝大多数的操作都是在查找，无论要对数据做什么操作都要先进行查找。
对于有序数组：
（1）二分查找法（logn）：
我们想要将无序数组变有序数组就需要进行排序的操作
排序常见的时间复杂度：
O(nlogn) O(n^2)
（2）哈希算法
通过num%arr.length取余来存储，时间复杂度O(1)
存在问题：两种不同数据计算出同一个位置（如12和32）——哈希冲突
解决办法：
①往后顺位，查找时再遍历（但是会占用其他未知）
②加入链表（哈希表）
2.链表
特点：是分散的，和数组一样，链表也会有一个变量存链表的地址。
（1）单向链表
链表除了存数据本身之外，也会存下一个数据的地址。
遍历时间复杂度只能是O(n),只能从前往后找。链表短的情况下默认是O(1)
（2）双向链表
特点：分散，每个节点除了存数据和下一节点地址，还会存有上一节点地址。
可以从前往后也可以从后往前找，但是遍历的时间复杂度还是O(n)
对于哈希表，Java里提供有哈希表，链表短就是O(1)，链表长就是O(logn)——红黑树
3.树
（1）二叉树
①有序二叉树
特点：左边节点值大于右边节点的
查找的时间复杂度：O(logn)——不稳定，比较次数和树的层数有关系.不一定查找的数据在最下边，也不一定是满叉树，可能是单边树。
②平衡二叉树
四种旋转方法（LL LR RR RL）
旋转的本质是修改节点的left和right值
左子树高度和右子树高度差的绝对值不能超过一。
LL型：
LR型（先变为LL再用LL型的方式）：
RR型：
RL（先变成RR再用RR的方式）型：
平衡二叉树每次都需要检查，所以会很耗性能。
③红黑树（O(logn)）：
·叶子节点是黑色（下图中红色或黑色的节点并非真正的叶子节点，而是左右子树会是黑色的null）
·根节点是黑色的
·红色节点的下一个永远是黑色
·从根节点到叶子节点的最长路径是黑红相间的，最短路径是黑色，但最长路径和最短路径黑色节点数量一样。（因为是由2-3-4树转换过来的，2-3-4每个节点只会提供一个黑色节点）
·最长路径比最短路径长度不会超过两倍（最大是两倍）
和2-3-4树的转换：
二节点转换为一个黑色节点
三节点转化为一个黑色节点，下边一个红色节点
四节点转换为一个黑色节点和两个红色节点
④哈夫曼树
数据变成流（0101…）之后根据协议（如ASCII码——八位一组定长编码）翻译成原来的数据。
数据压缩：变长编码，出现次数多的字符编码短。
·节点的权：节点存的值
·路径：从根节点到目标节点所走过的路线
·路径长度：从根节点到目标节点经历的边的数量
·边：父子节点之间的连线
·带权路径长度：节点的权值x路径长度
·树的带权路径长度（WPL）：叶子节点的带权路径长度之和（因为组合形式不唯一，WPL值最小的就是哈夫曼树）
如何构造哈夫曼树？
先把每个数值看成每一个节点，进行排序，大的节点离根节点近一些，小的节点离根节点远一些。
选择两个权值最小的节点，父节点的权值为它们的权值和，拿着父节点权值继续参与构建
哈夫曼编码：会以每个节点出现的次数作为权值来构建哈夫曼树
例：i like bananas 以字母出现次数为权值
左边为0，右边为1：则
a:11
S:100
L:1010
K:1011
N:011
E:0100
B:0101
空格：001
i:000
没有任何一个编码是其他编码的前缀，所以很方便解析出来
练习：
（2）多叉树
·构建是从下往上构建的
·value是有序的（从小到大）
①2-3-4树
特点：叶子节点都在同一层，不满足的节点就往上挤
二节点
三节点
四节点
例子：
②B树和B+树
B树有2-3-4-5-6-7-8…很多种节点
例如k阶B树：
可以分k个叉（数量指的是有多少个能存地址的区域）
K个Key-Value值
key就相当于页数，value就相当于页的内容，一页可以放很多个key-value值。
磁盘：
磁盘切面有许多小磁颗粒，因为存有不同的磁极来存储不同数据
写入数据： 电生磁
磁头通电带有不同的磁极，击穿小磁颗粒使得其带有对应的磁极
读数据： 磁生电
磁头不同电，通过读取到不同磁极产生电压来读取不同信息
磁头大概5~6ms读一次信息，但是比如int要32位代表一个数，一根导线就很慢，所以加入多个导线（总线）使得速度更快，内存的存在也会使得读取速度更快
磁盘当中以页（4kb）的形式存储信息，内存也是按页去接受。
为什么不用内存？
因为内存使用的是电容器，存在带电和不带电的区别，一旦断电没人加电压就会放电，电一跑数据就没了（断电数据就消失）。所以内存的数据不能永久性地存储。
B树的存储又在磁盘，尽可能降低树的高度，因为查找依赖于机械臂的移动。
红黑树和B/B+树的对比：
场景1：全部数据放在内存中（JavaTreeMap、C++map）
小规模数据：红黑树最优
内存随机访问极快，CPU比较代价很低；
B树每个节点内部大量关键字二分查找会引入额外开销，多叉优势发挥不出来
场景2：数据存在磁盘（数据库、文件索引、海量数据）
B/B+树碾压红黑树
磁盘I/O速度比内存慢上万倍，减少访问层数（树高）是第一优先级
红黑树层数太多->大量磁盘读取；
B树树高极小，只需要少数几次IO,哪怕每层多几次对比页完全划算
所以红黑树适合内存的操作，m阶B树适合磁盘的操作。
B树：
（1）节点分裂规则：K阶B树中，非根节点的子节点数量最少为K/2向上取整，最多为K。以5阶B树为例，非根节点最少有3个子节点，最多有5个。
（2）分裂形态分析：在节点插入导致分裂时，刚分裂完的节点子节点数量处于最少状态（如5阶B树分裂后为3个），这是推导树高的关键依据。
树高与数据量的数学关系：
等比数列模型建立：假设每个节点有M个子节点（M介于K/2与K之间），则第H层的节点数为M的(H-1)次方。
数据总量公式：每个节点存储M-1个数据，总数据量X等于节点总数乘以(M-1)，即X = (M^H – 1) * (M-1)。
时间复杂度结论：化简公式可得树高H约等于log以M为底X的对数。由于M是常数，在大数据量下忽略常数影响，B树的时间复杂度为O(logN)。
B+树:
非叶子节点仅存索引：B+树的非叶子节点只存储Key值作为索引，不存储Value值，而B树节点同时存储Key和Value。
叶子节点链表结构：所有叶子节点通过指针连接成一个有序链表，便于进行范围查询。
构建：
索引上浮机制：在插入数据导致节点分裂时，中间Key值被提升到父节点，但数据本身仍保留在叶子节点中。
节点分裂约束：与B树类似，非根节点的子节点数量需满足最少为K/2向上取整的要求，确保树的平衡性。
4.栈
想象成一个杯子容器，先放进去的会到最下边，把上边的拿走才能拿下边的
特点：先进后出FILO
入栈出栈O(1)
5.队列
一个通道，一端出队一端入队
特点：先进先出FIFO
入队列出队列O(1)
