数据结构与算法学习（四）：第四阶段知识总结

1. 位图概述

1. 概念
   1. 一种“特殊”的散列表
   2. 通过数组下标来定位数据，访问效率非常高
   3. 每个数字用一个二进制位来表示，数字范围不大的情况下，需要的内存空间非常节省

2. 字符串匹配算法概述

1. 单模式串算法

   • BM 算法

     1. 概念

        • 利用模式串本身的特点，在模式串中某个字符与主串不能匹配的时候，将模式串往后多滑动几位，以此来减少不必要的字符比较，提高匹配的效率

     2. 实现

        1. 好后缀规则和坏字符规则
        2. 好后缀规则可以独立于坏字符规则使用
        3. 坏字符规则的实现比较耗内存，为了节省内存，只用好后缀规则来实现 BM 算法

   • KMP 算法

     • 概念
       1. 根据规律在遇到坏字符的时候，把模式串往后多滑动几位
       2. 和 BM 算法的本质非常类似

2. 多模式串算法

   • AC 自动机

     1. 概念

        • 在 Trie 树之上，加了类似 KMP 的 next 数组，只不过此处的 next 数组是构建在树上

     2. 实现

        1. 将多个模式串构建成 Trie 树，在 Trie 树上构建失败指针
        2. 在 AC 自动机中匹配主串

3. 红黑树概述

1. 概念

   1. 一种大致平衡的二叉查找树，一类被标记为黑色，一类被标记为红色
   2. 一种性能非常稳定的二叉查找树

2. 概念辨析

   1. 根节点是黑色的
   2. 每个叶子节点都是黑色的空节点（NIL），即叶子节点不存储数据
   3. 任何相邻的节点都不能同时为红色，即红色节点是被黑色节点隔开的
   4. 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数组的黑色节点

3. 实现

   1. 按照固定的操作步骤，保持插入、删除的过程，不破坏平衡树的定义即可
   2. 找准关注节点，不要搞丢、搞错关注节点
   3. 插入操作的平衡调整比较简单，删除操作就比较复杂

4. 操作

   • 基础操作

     • 左旋和右旋

   • 插入操作

     1. 原则：插入的节点必须是红色的，二叉查找树中新插入的节点都放在叶子节点上
     2. 如果插入节点的父节点是黑色的，那什么都不用做；如果插入的节点是根节点，那直接改变它的颜色，把它变成黑色

   • 删除操作

     1. 针对删除节点初步调整
     2. 针对关注节点进行二次调整

5. 应用

   1. 在工程中，但凡用到动态插入、删除、查找数据的场景，都可以用红黑树
   2. 实现起来比较复杂，很多场景可以用跳表来替代红黑树

4. 哈希算法概述

1. 概念

   1. 将任意长度的二进制值串映射为固定长度的二进制值串，这个映射的规则就是哈希算法
   2. 通过原始数据映射之后得到的二进制值串就是哈希值

2. 设计步骤

   1. 从哈希值不能反向推导出原始数据
   2. 对输入数据非常敏感，哪怕原始数据只修改了一个 Bit，最后得到的哈希值也大不相同
   3. 散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小
   4. 哈希算法的执行效率要尽量高效，针对较长的文本，也能快速地计算出哈希值

3. 应用

   • 安全加密，唯一标识，数据校验，散列函数，负载均衡，数据分片，分布式存储