算法和数据结构的介绍和原理
面向面试和平时知识储备
红黑树
- 详见:https://www.jianshu.com/p/e136ec79235c
- 查找/插入/删除的复杂度都是O(logN)
- 是AVL树(平衡二叉搜索树)
- 比AVL树多了一个颜色属性
- 能够实现自平衡,黑色平衡
定义
- 有二叉搜索树的一般要求
- 结点是红色或黑色。
-
根结点是黑色。
-
所有叶子都是黑色。(叶子是NULL结点)
-
每个红色结点的两个子结点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色结点)
- 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。
实现自平衡的三种操作
-
左旋
- 以某个结点作为支点(旋转结点),其右子结点变为旋转结点的父结点,右子结点的左子结点变为旋转结点的右子结点,左子结点保持不变。
- 左旋只影响旋转结点和其右子树的结构,把右子树的结点往左子树挪了。
-
右旋
- 以某个结点作为支点(旋转结点),其左子结点变为旋转结点的父结点,左子结点的右子结点变为旋转结点的左子结点,右子结点保持不变。
- 右旋只影响旋转结点和其左子树的结构,把左子树的结点往右子树挪了。
- 变色
- 结点的颜色由红变黑或由黑变红。
查找
- 和平衡二叉树的查找一样
-
从根结点开始查找,把根结点设置为当前结点
-
判断当前结点的状态,若当前结点为空,返回null
- 若当前结点不为空,用当前结点的key跟查找key作比较
- 若当前结点key等于查找key,那么该key就是查找目标,返回当前结点
- 若当前结点key大于查找key,把当前结点的左子结点设置为当前结点,重复步骤
- 若当前结点key小于查找key,把当前结点的右子结点设置为当前结点,重复步骤
- 最坏时间复杂度为O(2lgN),即整棵树正好红黑相隔的时候。
插入
-
插入操作包括两部分工作
- 查找插入的位置
- 插入后自平衡
-
查找插入的父结点和查找操作差别不大
- 从根结点开始查找
- 判断根结点的状态,若根结点为空,那么插入结点作为根结点,结束
- 若根结点不为空,那么把根结点作为当前结点
- 判断当前结点的状态,若当前结点为空,返回当前结点的父结点,结束
- 若当前结点不为空,比较当前结点的key和插入结点的key
- 若当前结点的key等于插入结点的key,更新当前结点的值,结束
- 若当前结点的key大于插入结点的key,把当前结点的左子结点设为当前结点
- 若当前结点的key小于插入结点的key,把当前结点的右子节点设为当前结点
- 回到第四步,重复执行
- 插入后自平衡:设插入结点的颜色为红色,然后通过旋转和变色来实现自平衡
- 因为红色结点的父节点为黑色结点时,红黑树的黑色平衡没有被破坏,不需要做自平衡操作
- 如果插入结点是黑色,那么插入位置所在子树的黑色结点数量总是多1,必须做自平衡
删除
-
删除操作也包括两部分操作
- 查找目标结点
- 删除后自平衡
-
查找目标结点就是使用查找操作,当结点不存在时忽略此次删除操作
- 删除结点有以下三种情景
- 若删除结点无子结点,直接删除
- 若删除结点只有一个子结点,用子结点替换删除结点
- 若删除结点有两个子结点,用中序遍历顺序的下一个结点替换删除结点,也就是大于删除结点的最小结点,也是右子树的最左结点
- 删除后通过选转和变色来实现自平衡
B+树
- 详见:https://www.jianshu.com/p/71700a464e97
- 是n叉树
- 通常用于数据库和操作系统的文件系统中
- 特点是能保持数据稳定有序,插入与修改拥有较稳定的对数时间复杂度
- 叶子结点才记录数据,其他结点都是索引
定义
-
根结点至少有两个子女
-
每个中间结点都至少包含
ceil(m / 2)
个孩子,最多有m个孩子。 -
所有的叶子结点都位于同一层。
-
每个结点中的元素从小到大排列,结点当中
k-1
个元素正好是k个孩子包含的元素的值域分划。 -
有k个子树的中间结点包含有k个元素(B树中是k-1个元素),每个元素不保存数据,只用来索引,所有数据都保存在叶子结点。
-
所有的叶子结点中包含了全部元素的信息,及指向含这些元素记录的指针,且叶子结点本身依元素key的大小自小而大顺序链接。
- 所有的中间结点元素都同时存在于子结点,在子结点元素中是最大(或最小)元素。
和B树的区别
- 有k个子结点的结点必然有k个关键码
- 非叶结点仅具有索引作用,跟记录有关的信息均存放在叶结点中。
- 树的所有叶结点构成一个有序链表,可以按照关键码排序的次序遍历全部记录。
查找
- 自顶向下逐层查找
- 在每个结点中使用二分查找
- 若在每个索引结点中查找失败,比较查找失败时的停止元素的key和查找key的大小
- 若查找元素的key较大,选择停止元素的key的右子结点继续查找
- 否则选择左子结点继续查找
- 若在叶子结点中查找失败,返回null
B+树查找优于B树的地方
- B+树中间结点只有索引,因此同样数据量的情况下,B+树要比B树更矮胖,查询IO次数更少
- B树查询到匹配元素即可停止,而B+树要查询到叶子结点中指定元素才能停止,因此B+树的查询性能更稳定
- 对于查找处于某个范围间的元素,B+树只需要在链表上遍历即可,而B树需要频繁做中序遍历才行
插入
- 插入操作是自底向上的
- 判断根结点的状态
- 若根结点为空,则树为空树,直接创建一个结点并将记录插入其中,此时这个叶子结点也是根结点,结束
- 根据key值找到叶子结点,向这个叶子结点插入记录
- 判断当前结点的元素个数,若元素个数小于或等于m - 1 ,结束
- 若元素个数大于m - 1
- 则将这个叶子结点分裂成左右两个叶子结点,左叶子结点包含前m / 2个记录,右结点包含剩下的记录
- 将第m / 2 + 1个记录的key进位到父结点中
- 将新增了元素的父结点作为当前结点,回到第三步
- 判断根结点的状态
删除
- 查找叶子结点中相应的key,若查找失败,结束
- 删除对应的key,若删除后当前结点key的个数大于或等于ceil(m / 2) - 1,结束
- 若兄弟结点(也就是和当前结点拥有同一个父结点的结点)结点个数大于ceil(m / 2) - 1,则向兄弟结点借一个元素,并用借到的元素key替换它们共同父结点中的key,结束
- 例如4阶B+树中当前结点中的元素是10,兄弟结点中的元素是7、8、9,父结点中有索引元素10,则将兄弟结点中的元素9给予当前结点,用9代替父结点中的索引元素10
- 若兄弟结点也没有富余的key,则当前结点和兄弟结点合并成一个新的叶子结点,并且删除父亲结点中的对应元素。若父亲结点删除后不合要求,则按B树删除后的调整方法进行调整。
B树
定义
- 根结点至少有两个子女
- 每个中间结点都至少包含
ceil(m / 2)
个孩子,最多有m个孩子。 - 每一个叶子结点都包含
k-1
个元素,其中m/2 <= k <= m
。 - 所有的叶子结点都位于同一层。
- 每个结点中的元素从小到大排列,结点当中
k-1
个元素正好是k个孩子包含的元素的值域分划。
并查集
- https://zhuanlan.zhihu.com/p/93647900
- 主要用于解决一些元素分组的问题
- 常用森林来表示
- 逻辑结构是一系列不相交的集合
- 可以使用按秩合并来优化
初始化
- 设每个结点的父结点为自己
按秩合并优化
- 设每个结点的秩为1
查询(判断两个结点是否属于同一个集合)
- 只要判断是否有相同的根结点
- 不断向上查找父结点,直到找到父结点为自己的结点
合并
- 找到两个集合的根结点
- 将其中一个根结点的父结点设为另一个根结点
路径压缩优化
- 把沿途的每个结点的父结点都设置为它的根结点
按秩合并优化
- 分别找到两个结点的根结点
- 秩低的结点的父结点改为秩高结点的根结点
- 如果秩相同且根结点不同则新根结点的秩 + 1
KMP
- 目的是提高字符串的匹配效率
- 主要思想是消除匹配失败时的回溯,只改变模式串的匹配位置,减少不必要的匹配
- 通过next数组来标记失配时模式串应跳到哪个位置
next数组
- next数组记录了当前字符之前的字符串中有多大长度的相同前缀后缀
- 例如next[j] = k,代表下标j之前的字符串中有最大长度为k的相同前缀后缀
Dijkstra
- 用来解决单源最短路问题
- 是用贪心策略实现的,也就是先认为从距离最短的点到其他点距离更短,再逐个加入未遍历过的距离最短的点查找更短的距离,最后遍历所有的点
步骤
- 先找到源点到各个点的直接最短距离
- 选取刚才找到的距离最短的点,遍历其他的点,若使用该点作为中转站距离更短则更新路径和最短距离
- 重复第二步,直到遍历完所有的点
评论