数据结构与算法

参考 https://gitee.com/ShengSanYi/CS-Xmind-Note 408 专业课笔记 需要认真学习

无序表线性查找的平均查找次数是 n+ 1 /2
有序表折半查找的平均查找次数是 log2(n + 1) - 1
hash 表查找 完全没冲突的次数是 O(1)
冲突
装填因子 α(存储的序列长度 / hash 表能存储的总长度)
拉链法解决冲突: ASL ≈ 1 + α/2 线性探测法: (1 + 1/ (1- α)) / 2

数据结构

参考: 我的第一本算法书.pdf

存储结构	优点	缺点
顺序存储	存储密度大（＝ 1），存储空间利用率高	存储空间分配不灵活; 空间复杂度高; 插入或删除元素时不方便
链式存储	插入或删除元素时很方便	存储密度小

栈

顺序存储结构
链式存储结构
应用： 递归 四则运算的括号问题

队列

平常我们排队
顺序存储： 给定数组长度，只能存长度个数据
使用循环队列解决问题 -->
指针 front rear(队尾 是下一个元素要存放的位置)
when (rear +1 ) % queueSize == front 队列满 (保留了一个元素位置不用)
队列的长度： ( rear - front + queueSize) % queueSize

散列表

存储的是由键（key）和值（value）组成的数据。

• 线性查询的缺点: 数据量越多，线性查找耗费的时间就越长。
  由此可知 ：由于数据的查询较为耗时，所以此处并不适合使用数组来存储数据。但使用哈希表便可以解决这个问题。这次我们用 5 个箱子的数组来存储数据。使用哈希函数（Hash）计算 Item 的键,也就是哈希值,将得到的哈希值除以数组的长度 5，求得其余数,结巴数据放到数组的余数位置,如果出现冲突(另一个数据的哈希值%5 得到的位置已经有元素了),使用链表,在其后存储数据

• 散列函数构造要求

  • 散列占用的空间尽量小

  • 尽量均匀的存放元素, 以避免冲突

    常用方法: 直接定址法; 除留余数法

• 查询数据(key="wang"):
  现根据哈希算法就算出哈希值,得到存再数组里面的位置,在在链表中去线性查找 key 是 wang 的数据

• 冲突: 不同的关键码映射到同一个散列表 key1 != key2 结果 h(key1) = h(key2) h 为散列函数

• 冲突解决: 链地址法/开放地址法/

• 散列表的所有操作 增删改查都是 o(1)级别

有序表

• 哈希表升级版本,他们的 key 是有序得,操作级别的 o(logn)级别

堆: 是一种图的树形结构

利用数组实现的完全二叉树结构 size 就是数组长度 i 位置左孩子下标为 2i+1 右孩子 2i+2 i 位置的父节点 (i-1) / 2
被用于实现“优先队列”
优先队列是一种数据结构，可以自由添加数据，但取出数据时要从最小值开始按顺序取出。
堆中的每个结点最多有两个子结点。树的形状取决于数据的个数。另外，结点的排列顺序为从上到下，同一行里则为从左到右。

• 在堆中存储数据时必须遵守这样一条规则
  子结点必定大于父结点。因此，最小值被存储在顶端的根结点中。往堆中添加数据时，为了遵守这条规则，一般会把新数据放在最下面一行靠左的位置。当最下面一行里没有多余空间时，就再往下另起一行，把数据加在这一行的最左端。
• 取数据:
  取出的是最上面的数据。由于最上面的数据被取出，因此堆的结构也需要重新调整。
  将最后的数据（最后一行,最后一个节点）移动到最顶端。
  如果子结点的数字小于父结点的，就将父结点与其左右两个子结点中较小的一个进行交换。
• 解说:
  堆中最顶端的数据始终最小，所以无论数据量有多少，取出最小值的时间复杂度都
  为 O(1)。
  另外，因为取出数据后需要将最后的数据移到最顶端，然后一边比较它与子结点数据
  的大小，一边往下移动，所以取出数据需要的运行时间和树的高度成正比。假设数据量为
  n，根据堆的形状特点可知树的高度为 log2n ，那么重构树的时间复杂度便为 O(logn)。
  添加数据也一样。在堆的最后添加数据后，数据会一边比较它与父结点数据的大
  小，一边往上移动，直到满足堆的条件为止，所以添加数据需要的运行时间与树的高度
  成正比，也是 O(logn)。

树

树是 n (n>0)个结点的有限集

​ 如果 n=0 称为空树

​ 如果 n>0 则他满足一下两个条件:

- 有且仅有一个特定的称为 **跟 **的节点
- 其余结点可以分为 m (m>=0)个互不相交的有限集 T1,T2,T3,...,Tm,其中每一个集合本身又是一棵树, 并称为跟的**子树**

基本术语

结点的度: 结点拥有的子树个数

- 度为0 的节点称为 **叶子节点** 或者 **终端节点**

• 度不为 0 的节点称为分支节点 或者 非终端结点 ; 非根节点的分支节点也称为 内部节点

树的度: 树内所有节点的度的最大值

节点关系

• 双亲就是父节点
• 位于同一层的所有节点互称堂兄弟
• 祖先节点是指该节点到根节点的唯一路径中的任意节点

二叉树

每个节点最多只有两个 "叉" 的树, 由 左子树 和 右子树 组成

每个节点最多由两个孩子

二叉树不是树的特殊情况, 他们是两个不同的概念
二叉树节点必须区分 左子树 和 右子树, 即使只有一颗子树的情况,也要说明是左子树还是右子树
树当节点只有一个孩子时, 无需区分

思考: 具有三个节点的二叉树有几种形态,普通树呢?
二叉树: 5种
树: 2种

二叉树的性质

• 1.非空二叉树上叶子结点数等于度为 2 的结点数加 1
• 2.非空二叉树上第 K 层上至多有 2^k−1 个结点（K≥1）
• 3.高度为 H 的二叉树至多有 2^H-1 个结点（H≥1）
• 4.具有 N 个（N>0）结点的完全二叉树的高度为 [log2(N+1)]或[log2N] +1。

二叉树的存储结构

• 顺序存储
  • 二叉树的顺序存储结构就是用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素。
• 链式存储
  • 二叉树每个结点最多两个孩子，所以设计二叉树的结点结构时考虑两个指针指向该结点的两个孩子。

特殊二叉树

满二叉树

一颗深度为 k 且有 2^k -1 个节点的二叉树

每层都是满的

完全二叉树

深度为 k 的具有 n 个节点的二叉树, 当且仅当其每个节点都与深度为 k 的满二叉树中编号为 1~n 的节点 一一对应

在满二叉树中,从最后一个节点开始,连续去掉任意个节点, 即是完全二叉树

线索二叉树

• N 个结点的二叉链表，每个结点都有指向左右孩子的
  结点指针，所以一共有 2N 个指针，而 N 个结点的二叉
  树一共有 N-1 条分支，也就是说存在 2N-(N-1)=N+1 个空指针。比如左图二叉树中有 6 个结点，那么就有 7 个空
  指针。
• 大量的空余指针能否利用起来？
  • 如果某个节点的左孩子为空,则将空的左孩子指针域改为指向其前驱; 如果某个节点的右孩子为空,则将空的右孩子指针域改为指向其后继节点
  • 指向前驱和后继的指针称为线索，加上线索的二叉链表就称为线索链表，相应的二叉树就称为线索二叉树
  • 对二叉树以某种次序遍历使其变为线索二叉树的过程就叫做线索化

哈夫曼树( 最优二叉树 )

我们要对学生成绩进行划分成 5 个等级, 你会怎么书写代码?

使用if else判断  或者 Switch语句判断构成判断树:
>90 --Y--> return A
   |--N--> >80 --Y--> return B
   			  |--N--> >70 --Y--> return C
   			  			 |--N--> >60 --Y--> return D
		    			  			|--N--> return E
但是我们从 中间开始判断的话
比如 >80 --Y--> >90 --Y--> return A
				   |--N--> return B
		|--N--> >70  ...
					...
在数据量很大时候,方式一和方式二的效率是不一样的
怎么找到一种效率最高的判别树呢?  ---> 哈夫曼树

概念

路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径。

结点的路径长度：两结点间路径上的分支数。

树的路径长度：从树根到每一个结点的路径长度之和。记作：TL

结点数目相同的二叉树中，完全二叉树是路径长度最短的二叉树

反过来不成立

权（weight）：将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。

结点的带权路径长度：从根结点到该结点之间的路径长度与该结点的权的乘积。

算法

时间复杂度

O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)

排序

• 冒泡排序 相邻两个数比较 大的放右边 --> 右边最大值

• 选择排序 找出序列中最小的数字,和当前位置交换 --> 不稳定

• 插入排序 它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

• 堆排序
  堆排序的特点是利用了数据结构中的堆。

  堆排序一开始需要将 n 个数据存进堆里，所需时间为 O(nlogn)。排序过程中，堆从空堆的状态开始，逐渐被数据填满。由于堆的高度小于 log2n，所以插入 1 个数据所需要的时间为 O(logn)。
  每轮取出最大的数据并重构堆所需要的时间为 O(logn)。由于总共有 n 轮，所以重构后排序的时间也是 O(nlogn)。因此，整体来看堆排序的时间复杂度为 O(nlogn)。
  这样来看，堆排序的运行时间比之前讲到的冒泡排序、选择排序、插入排序的时间 O(n2) 都要短，但由于要使用堆这个相对复杂的数据结构，所以实现起来也较为困难。

• 归并排序
  归并排序算法会把序列分成长度相同的两个子序列，当无法继续往下分时（也就是每个子序列中只有一个数据时），就对子序列进行归并。归并指的是把两个排好序的子序列合并成一个有序序列。该操作会一直重复执行，直到所有子序列都归并为一个整体为止。
  总的运行时间为 O(nlogn)，这与前面讲到的堆排序相同。

• 快排
  快速排序是一种“分治法”。它将原本的问题分成两个子问题（比基准值小的数和比基准值大的数），然后再分别解决这两个问题。子问题，也就是子序列完成排序后，再像一开始说明的那样，把他们合并成一个序列，那么对原始序列的排序也就完成了。
  不过，解决子问题的时候会再次使用快速排序，甚至在这个快速排序里仍然要使用快速排序。只有在子问题里只剩一个数字的时候，排序才算完成。
  像这样，在算法内部继续使用该算法的现象被称为“递归”。

  整体的时间复杂度为 O(nlogn)。
  如果运气不好，每次都选择最小值作为基准值，那么每次都需要把其他数据移到基准值的右边，递归执行 n 行，运行时间也就成了 O(n2)。
  这就相当于每次都选出最小值并把它移到了最左边，这个操作也就和选择排序一样了。此外，如果数据中的每个数字被选为基准值的概率都相等，那么需要的平均运行时间为 O(nlogn)。

查找

线性查找

线性查找是一种在数组中查找数据的算法（关于数组的详细讲解在 1-3 节）。即便数据没有按顺序存储，也可以应用线性查找。线性查找的操作很
简单，只要在数组中从头开始依次往下查找即可。

线性查找需要从头开始不断地按顺序检查数据，因此在数据量大且目标数据靠后，
或者目标数据不存在时，比较的次数就会更多，也更为耗时。若数据量为 n，线性查找的时间复杂度便为 O(n)。

二分查找

它只能查找已经排好序的数据。二分查找通过比较数组中间的数据与目标数据的大小，可以得知目标数据是在数组的左边还是右边。因此，比较一次就可以把查找范围缩小一半.
数据量为 n 的数组，将其长度减半 log2n 次后，其中便只剩一个数据了。也就是说，在二分查找中重复执行“将目标数据和数组中间的数据进行比较后将查找范围减半”的操作 log2n 次后，就能找到目标数据（若没找到则可以得出数据不存在的结论），因此它的时间复杂度为 O(logn)。

hash 表查找

具有很好的平均性能, 优于一些传统的技术
链地址法比开放地址法优
除留余数法优于其他类型函数

线性索引查找

索引就是把一个关键字与它对应的记录相关联的过程, 一个索引由若干个索引项构成, 每个索引项至少包含关键字和其对应的记录在存储器中的位置等信息;

索引按照结构可以分为线性索引、树形索引和多级索引。

线性索引

稠密索引

稠密索引是指在线性索引中，将数据集中的每个记录对应一个索引项，

一一对应关系, 索引项一定是按照关键码有序的排序, 这样查找索引时可以折半 插值 斐波那契等查找算法; 缺点是数据量很大时候, 内存占用很大, 可能会引发访问磁盘从而性能大大折扣

分块索引

类似图书馆图书分类, 内存分页

倒排索引

索引项的通用结构是：

• 次关键码，例如上面的“英文单词”；
• 记录号表，例如上面的“文章编号”。

其中记录号表存储具有相同次关键字的所有记录的记录号（可以是指向记录的指针或者是该记录的主关键字）。这样的索引方法就是倒排索引（inverted index）

二叉查找树(二叉排序树 BST 树)

数据存储于二叉查找树的各个结点中。
二叉查找树有两个性质。
第一个是每个结点的值均大于其左子树上任意一个结点的值。
第二个是每个结点的值均小于其右子树上任意一个结点的值。

根据这两个性质可以得到以下结论。首先，二叉查找树的最小结点要从顶端开始，往其左下的末端寻找。
反过来，二叉查找树的最大结点要从顶端开始，往其右下的末端寻找。

• 中序遍历二叉查找树的结果是 从小到大排序好的数据

• 常用于查找算法中,如果查找的数据集是有序线性表,并且是顺序存储的,查找可以使用折半查找/插值查找/斐波那契等查找算法,
  可惜,因为有序,在插入和删除上需要消耗大量的时间,二叉查找树就是可以插入删除效率不错,又可以高效的实现查找的算法;
  我们打算对集合做查找,在我们打算创建此集合的时候就考虑用二叉树结构,而且是排好序的二叉树来创建;
  构造一颗二叉查找树的目的,并不是为了排序,而是为了提高查找和插入删除关键词的速度;

创建二叉树,就是二叉树插入节点,递归的按照顺序插入
删除二叉树节点,包括三种情况,① 如果删除节点在叶子节点,直接删除;② 如果删除节点只有左节点或右节点,删除节点,把子节点介入到删除节点父节点 ③ 如果删除节点包括左右节点,在删除节点左子树找最大节点或者右子树最小节点,替换需要删除的节点,删除替换的节点(这个删除节点任然需要递归删除)

二叉排序树的性能和树高度有关,同时同一集合按照不同的节点插入会生成不同的树结构,引申出来平衡二叉树

• 添加数据:
  顶端结点开始寻找添加数字的位置。
  依次往下比较,得到位置
• 删除数据:
  删除的节点下面没节点
  删除的节点下面一个节点
  删除的节点下面两个节点 左右子树重新梳理数据
• 解说:
  我们可以把二叉查找树当作是二分查找算法思想的树形结构体现（二分查找的详细
  说明在 3-2 节）。因为它具有前面提到的那两个性质，所以在查找数据或寻找适合添加
  数据的位置时，只要将其和现有的数据比较大小，就可以根据比较结果得知该往哪边移
  动了。
  比较的次数取决于树的高度。所以如果结点数为 n，而且树的形状又较为均衡的话，
  比较大小和移动的次数最多就是 log2n。因此，时间复杂度为 O(logn)。但是，如果树的
  形状朝单侧纵向延伸，树就会变得很高，此时时间复杂度也就变成了 O(n)。

平衡二叉树(AVL 树)(有别于 AVL 算法)

是二叉排序树,同时左子树和右子树的高度之差绝对值<=1 ,同时左子树和右子树也是 AVL 树
平衡因子: 节点左子树的高度 - 节点右子树的高度
平衡二叉树所有节点的平衡因子只能是 -1 0 1
对于一颗 n 个节点的 AVL 树,其高度保持在 O(log2n)数量级,ASL 也保持在 o(log2n)级

当我们在平衡二叉树插入一个数据,有可能导致失衡, 此时必须重新调整树的结构
平衡调整的四种类型: LL 型(插入节点是失衡节点的左子树的左子树) LR 型(插入节点是左子树的右孩子)
RL 型 RR 型
调整原则: 找到插入数据之后的最小不平衡树 降低树高度; 满足二叉排序树,调整节点

平衡二叉树的目的是为了减少二叉查找树层次，提高查找速度

平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等

红黑树

R-B Tree，全称是 Red-Black Tree，又称为“红黑树”，它一种平衡二叉树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。它可以在 O(log n)时间内做查找，插入和删除;

平衡二叉树，Java 集合中的 TreeSet 和 TreeMap，C++ STL 中的 set、map，以及 Linux 虚拟内存的管理，都是通过红黑树去实现的

AVL

最早的平衡二叉树之一。应用相对其他数据结构比较少。windows 对进程地址空间的管理用到了 AVL 树

多路查找树

一个节点只存储一个元素时,在元素非常多的时候,要么使得树的度非常大,要么树的高度非常高

多路查找树: 每一个节点的孩子树可以多余两个,且每一个节点可以存储多个元素。由于它是查找树,所有元素之间存在特定的排列关系
主要有四种: 2-3 树 2-3-4 树 B 树 B+树

2-3 树

每一个节点都具有两个孩子(称为 2 节点)或者三个孩子(称为 3 节点)

• 一个 2 结点包含一个元素和两个孩子（或没有孩子），且与二叉排序树类似，左子树包含的元素小于该元素，右子树包含的元素大于该元素。不过，与二叉排序树不同的是，这个 2 结点要么没有孩子，要有就有两个，不能只有一个孩子。
• 一个 3 结点包含一小一大两个元素和三个孩子（或没有孩子），一个 3 结点要么没有孩子，要么具有 3 个孩子。如果某个 3 结点有孩子的话，左子树包含小于较小元素的元素，右子树包含大于较大元素的元素，中间子树包含介于两元素之间的元素。

2-3-4 树

2-3 树的扩展,包含了 4 节点的使用,一个 4 节点包含小中大三个元素和 4 个孩子(或者没有孩子)

B 树

是一种平衡的多路查找树, 2-3 2-3-4 树都是 B 树的特例, 节点最大的孩子数目称为 B 树的 阶

B 树的数据结构就是为内外存的数据交互准备的

B+树

B ＋树是应文件系统所需而出的一种 B 树的变形树，注意严格意义上讲，它其实已经不是之前定义的树了。在 B 树中，每一个元素在该树中只出现一次，有可能在叶子结点上，也有可能在分支结点上。而在 B ＋树中，出现在分支结点中的元素会被当作它们在该分支结点位置的中序后继者（叶子结点）中再次列出。另外，每一个叶子结点都会保存一个指向后一叶子结点的指针。

安全算法

• 哈希函数
  第一个特征是输出的哈希值数据长度不变。
  第二个特征是如果输入的数据相同，那么输出的哈希值也必定相同。
  第三个特征是即使输入的数据相似，但哪怕它们只有一比特的差别，那么输出的哈希值也会有很大的差异。输入相似的数据并不会导致输出的哈希值也相似。
  第四个特征是即使输入的两个数据完全不同，输出的哈希值也有可能是相同的，虽然出现这种情况的概率比较低。这种情况叫作“哈希冲突”。
  第五个特征是不可能从哈希值反向推算出原本的数据。输入和输出不可逆这一点和加密有很大不同。
  最后一个特征是求哈希值的计算相对容易。

哈希函数的算法中具有代表性的是 MD5 ①、SHA-1 ② 和 SHA-2 等

常用算法技巧

运算符妙用

• 与运算符 JavaScript 使用 32 位按位运算数 JavaScript 将数字存储为 64 位浮点数，但所有按位运算都以 32 位二进制数执行
  • 利用 n & (n - 1)消去 n 最后的一位 1
  • num = 10010 num & (~num + 1) 就得到二进制右侧第一个 1
  • num & 1 取得 num 二进制表示右侧第一个二进制位
• 异或运算
  1. 特性一：两个相同的数相互异或，运算结果为 0，例如 n ^ n = 0;
  2. 特性二：任何数和 0 异或，运算结果不变，例如 n ^ 0 = n;
  3. 特性三：支持交换律和结合律，例如 x ^ ( y ^ x) = (x ^ y) ^ x;
• 位移
  • num >>>0 将二进制数转换成无符号数; 去掉浮点数小数部分

递归

相同的递归子问题
时间复杂度 master 公式: T(N) = a _ T(N / b) + o(N 的 d 次方) N 代表数据量 a 代表子问题执行多少次
如果 logb^a < d 时间复杂度 o(N 的 d 次方)
如果 logb^a > d 时间复杂度 o(N 的 logb^a 次方)
如果 logb^a = d 时间复杂度 o(N 的 logb^a 次方 _ logb^a)

快慢指针

如果有一个链表, 给两个指针, 快指针一次走两步, 慢指针一次走一步, 当快指针走完的时候, 慢指针走到中间位置