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

红黑树

  • 详见: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个孩子包含的元素的值域分划。

并查集

初始化

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

    按秩合并优化

  • 设每个结点的秩为1

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

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

合并

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

路径压缩优化

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

按秩合并优化

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

KMP

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

next数组

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

Dijkstra

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

步骤

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

标签: none

添加新评论