算法和数据结构的介绍和原理
面向面试和平时知识储备

红黑树

• 详见：https://www.jianshu.com/p/e136ec79235c
• 查找/插入/删除的复杂度都是O(logN)
• 是AVL树（平衡二叉搜索树）
• 比AVL树多了一个颜色属性
• 能够实现自平衡，黑色平衡

定义

• 有二叉搜索树的一般要求
  1. 结点是红色或黑色。

1. 根结点是黑色。

2. 所有叶子都是黑色。（叶子是NULL结点）

3. 每个红色结点的两个子结点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色结点）

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

实现自平衡的三种操作

• 左旋

  • 以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。
  • 左旋只影响旋转结点和其右子树的结构，把右子树的结点往左子树挪了。

• 右旋

  • 以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。
  • 右旋只影响旋转结点和其左子树的结构，把左子树的结点往右子树挪了。
• 变色
  • 结点的颜色由红变黑或由黑变红。

查找

• 和平衡二叉树的查找一样

1. 从根结点开始查找，把根结点设置为当前结点

2. 判断当前结点的状态，若当前结点为空，返回null

3. 若当前结点不为空，用当前结点的key跟查找key作比较
   • 若当前结点key等于查找key，那么该key就是查找目标，返回当前结点
   • 若当前结点key大于查找key，把当前结点的左子结点设置为当前结点，重复步骤
   • 若当前结点key小于查找key，把当前结点的右子结点设置为当前结点，重复步骤

• 最坏时间复杂度为O(2lgN)，即整棵树正好红黑相隔的时候。

插入

• 插入操作包括两部分工作

  1. 查找插入的位置
  2. 插入后自平衡

• 查找插入的父结点和查找操作差别不大

  1. 从根结点开始查找
  2. 判断根结点的状态，若根结点为空，那么插入结点作为根结点，结束
  3. 若根结点不为空，那么把根结点作为当前结点
  4. 判断当前结点的状态，若当前结点为空，返回当前结点的父结点，结束
  5. 若当前结点不为空，比较当前结点的key和插入结点的key
     • 若当前结点的key等于插入结点的key，更新当前结点的值，结束
     • 若当前结点的key大于插入结点的key，把当前结点的左子结点设为当前结点
     • 若当前结点的key小于插入结点的key，把当前结点的右子节点设为当前结点
  6. 回到第四步，重复执行
• 插入后自平衡：设插入结点的颜色为红色，然后通过旋转和变色来实现自平衡
• 因为红色结点的父节点为黑色结点时，红黑树的黑色平衡没有被破坏，不需要做自平衡操作
• 如果插入结点是黑色，那么插入位置所在子树的黑色结点数量总是多1，必须做自平衡

删除

• 删除操作也包括两部分操作

  1. 查找目标结点
  2. 删除后自平衡

• 查找目标结点就是使用查找操作，当结点不存在时忽略此次删除操作

• 删除结点有以下三种情景
  1. 若删除结点无子结点，直接删除
  2. 若删除结点只有一个子结点，用子结点替换删除结点
  3. 若删除结点有两个子结点，用中序遍历顺序的下一个结点替换删除结点，也就是大于删除结点的最小结点，也是右子树的最左结点
• 删除后通过选转和变色来实现自平衡

B+树

• 详见：https://www.jianshu.com/p/71700a464e97
• 是n叉树
• 通常用于数据库和操作系统的文件系统中
• 特点是能保持数据稳定有序，插入与修改拥有较稳定的对数时间复杂度
• 叶子结点才记录数据，其他结点都是索引

定义

1. 根结点至少有两个子女

2. 每个中间结点都至少包含ceil(m / 2)个孩子，最多有m个孩子。

3. 所有的叶子结点都位于同一层。

4. 每个结点中的元素从小到大排列，结点当中k-1个元素正好是k个孩子包含的元素的值域分划。

5. 有k个子树的中间结点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子结点。

6. 所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依元素key的大小自小而大顺序链接。

7. 所有的中间结点元素都同时存在于子结点，在子结点元素中是最大（或最小）元素。

和B树的区别

• 有k个子结点的结点必然有k个关键码
• 非叶结点仅具有索引作用，跟记录有关的信息均存放在叶结点中。
• 树的所有叶结点构成一个有序链表，可以按照关键码排序的次序遍历全部记录。

查找

• 自顶向下逐层查找
• 在每个结点中使用二分查找
• 若在每个索引结点中查找失败，比较查找失败时的停止元素的key和查找key的大小
  • 若查找元素的key较大，选择停止元素的key的右子结点继续查找
  • 否则选择左子结点继续查找
• 若在叶子结点中查找失败，返回null

B+树查找优于B树的地方

• B+树中间结点只有索引，因此同样数据量的情况下，B+树要比B树更矮胖，查询IO次数更少
• B树查询到匹配元素即可停止，而B+树要查询到叶子结点中指定元素才能停止，因此B+树的查询性能更稳定
• 对于查找处于某个范围间的元素，B+树只需要在链表上遍历即可，而B树需要频繁做中序遍历才行

插入

• 插入操作是自底向上的
  1. 判断根结点的状态
     • 若根结点为空，则树为空树，直接创建一个结点并将记录插入其中，此时这个叶子结点也是根结点，结束
  2. 根据key值找到叶子结点，向这个叶子结点插入记录
  3. 判断当前结点的元素个数，若元素个数小于或等于m - 1 ，结束
  4. 若元素个数大于m - 1
  5. 则将这个叶子结点分裂成左右两个叶子结点，左叶子结点包含前m / 2个记录，右结点包含剩下的记录
  6. 将第m / 2 + 1个记录的key进位到父结点中
  7. 将新增了元素的父结点作为当前结点，回到第三步

删除

1. 查找叶子结点中相应的key，若查找失败，结束
2. 删除对应的key，若删除后当前结点key的个数大于或等于ceil(m / 2) - 1，结束
3. 若兄弟结点（也就是和当前结点拥有同一个父结点的结点）结点个数大于ceil(m / 2) - 1，则向兄弟结点借一个元素，并用借到的元素key替换它们共同父结点中的key，结束
   • 例如4阶B+树中当前结点中的元素是10，兄弟结点中的元素是7、8、9，父结点中有索引元素10，则将兄弟结点中的元素9给予当前结点，用9代替父结点中的索引元素10
4. 若兄弟结点也没有富余的key，则当前结点和兄弟结点合并成一个新的叶子结点，并且删除父亲结点中的对应元素。若父亲结点删除后不合要求，则按B树删除后的调整方法进行调整。

B树

定义

1. 根结点至少有两个子女
2. 每个中间结点都至少包含ceil(m / 2)个孩子，最多有m个孩子。
3. 每一个叶子结点都包含k-1个元素，其中m/2 <= k <= m。
4. 所有的叶子结点都位于同一层。
5. 每个结点中的元素从小到大排列，结点当中k-1个元素正好是k个孩子包含的元素的值域分划。

并查集

• https://zhuanlan.zhihu.com/p/93647900
• 主要用于解决一些元素分组的问题
• 常用森林来表示
• 逻辑结构是一系列不相交的集合
• 可以使用按秩合并来优化

初始化

• 设每个结点的父结点为自己

  按秩合并优化

• 设每个结点的秩为1

查询（判断两个结点是否属于同一个集合）

• 只要判断是否有相同的根结点
• 不断向上查找父结点，直到找到父结点为自己的结点

合并

• 找到两个集合的根结点
• 将其中一个根结点的父结点设为另一个根结点

路径压缩优化

• 把沿途的每个结点的父结点都设置为它的根结点

按秩合并优化

1. 分别找到两个结点的根结点
2. 秩低的结点的父结点改为秩高结点的根结点
3. 如果秩相同且根结点不同则新根结点的秩 + 1

KMP

• 目的是提高字符串的匹配效率
• 主要思想是消除匹配失败时的回溯，只改变模式串的匹配位置，减少不必要的匹配
• 通过next数组来标记失配时模式串应跳到哪个位置

next数组

• next数组记录了当前字符之前的字符串中有多大长度的相同前缀后缀
• 例如next[j] = k，代表下标j之前的字符串中有最大长度为k的相同前缀后缀

Dijkstra

• 用来解决单源最短路问题
• 是用贪心策略实现的，也就是先认为从距离最短的点到其他点距离更短，再逐个加入未遍历过的距离最短的点查找更短的距离，最后遍历所有的点

步骤

1. 先找到源点到各个点的直接最短距离
2. 选取刚才找到的距离最短的点，遍历其他的点，若使用该点作为中转站距离更短则更新路径和最短距离
3. 重复第二步，直到遍历完所有的点