读书笔记-算法-第三章
第三章 查找
- 符号表
- 符号表最主要的目的就是将一个键和一个值联系起来
- 能够将一个键值对插入符号表并希望在之后能够从符号表的所有键值对中按照键直接找到相对应的值
- 设计原则
- 每个键只对应着一个值（表中不允许存在重复的键）
- 当用例代码向表中存入的键值对和表中已有的键（及关联的值）冲突时，新的值会替代旧的值
- 键不能为空
- 不允许有空值
- 删除操作
- 延时删除
- put(key,null)是delete(key)的一种简单的（延时型）实现
- 即时删除
- 延时删除
- 基础API
- 有序的符号表API
- 通过实现comparabel接口带来接口的有序性
- 通过实现comparabel接口带来接口的有序性
- 最大键和最小键
- 区别在于优先队列中可以存在重复的键但符号表中不行，而且有序符号表支持的操作更多
- 向下取整和向上取整
- 向下取整（floor）操作（找出小于等于该键的最大键）
- 向上取整（ceiling）操作（找出大于等于该键的最小键）
- 排名和选择
- 范围查找
- 例外情况
- 当一个方法需要返回一个键但表中却没有合适的键可以返回时，我们约定抛出一个异常（另一种合理的方法是在这种情况下返回空）
- 成本模型
- 统计比较的次数（等价性测试或是键的相互比较）
- 在内循环不进行比较（极少）的情况下，我们会统计数组的访问次数
- 无序链表的顺序查找
- 符号表中使用的数据结构的一个简单选择是链表，每个结点存储一个键值对
- 每次查找遍历链表，使用equals方法进行比较
- 插入也是遍历链表，如果匹配，则进行更新，没有匹配的就插入
- 我们使用命中表示一次成功的查找，未命中表示一次失败的查找
- 注意其中的node构建方法，以及get和put方法
- 性能分析
- 在含有N对键值的基于（无序）链表的符号表中，未命中的查找和插入操作都需要N次比较。命中的查找在最坏情况下需要N次比较。特别地，向一个空表中插入N个不同的键需要~(N^2)/2次比较
- 查找一个已经存在的键并不需要线性级别的时间。一种度量方法是查找表中的每个键，并将总时间除以N。
- 在查找表中的每个键的可能性都相同的情况下时，这个结果就是一次查找平均所需的比较数。我们将它称为随机命中
- 在含有N对键值的基于（无序）链表的符号表中，未命中的查找和插入操作都需要N次比较。命中的查找在最坏情况下需要N次比较。特别地，向一个空表中插入N个不同的键需要~(N^2)/2次比较
- 符号表中使用的数据结构的一个简单选择是链表，每个结点存储一个键值对
有序数组中的二分查找
- 使用的数据结构是一对平行的数组，一个存储键一个存储值
- 核心是rank()方法，它返回表中小于给定键的键的数量，其实就相当于返回这个给定键应该所处的位置
- get()方法，只要给定的键存在于表中，rank()方法就能够精确地告诉我们在哪里能够找到它
- put()方法，只要给定的键存在于表中，rank()方法就能够精确地告诉我们到哪里去更新它的值
- 递归的rank()保留了以下性质
- 如果表中存在该键，rank()应该返回该键的位置，也就是表中小于它的键的数量
- 如果表中不存在该键，rank()还是应该返回表中小于它的键的数量
- 效率分析
顺序查找和二分查找的效率对比
二叉查找树
- 定义
- 我们所使用的数据结构由结点组成，结点包含的链接可以为空（null）或者指向其他结点
- 在二叉树中，每个结点只能有一个父结点（只有一个例外，也就是根结点，它没有父结点），而且每个结点都只有左右两个链接，分别指向自己的左子结点和右子结点
- 左子结点小于父节点，右子结点大于父结点
- 基本实现
- 数据表示
- 我们嵌套定义了一个私有类来表示二叉查找树上的一个结点。每个结点都含有一个键、一个值、一条左链接、一条右链接和一个结点计数器
- 一棵二叉查找树代表了一组键（及其相应的值）的集合，而同一个集合可以用多棵不同的二叉查找树表示
- 查找
- 在二叉查找树中查找一个键的递归算法：如果树是空的，则查找未命中
- 如果被查找的键和根结点的键相等，查找命中
- 否则我们就（递归地）在适当的子树中继续查找
- 如果被查找的键较小就选择左子树，较大则选择右子树
- 插入
- 和查找很类似，找到对应的父节点，比父节点大就插入右边，比父节点小就插入左边
- 和查找很类似，找到对应的父节点，比父节点大就插入右边，比父节点小就插入左边
- 数据表示
- 分析
- 最好的情况就是二叉树左右两边的子结点是完全平衡的，这样找到子结点最多次数是lgN
- 最差的情况就是所有的子结点都在左半边或者右半边，找到子结点最多次数是N
- 在由N个随机键构造的二叉查找树中，查找命中平均所需的比较次数为～2lnN（约1.39lgN）
- 其他操作
- 最大键和最小键
- 如果根结点的左链接为空，那么一棵二叉查找树中最小的键就是根结点；如果左链接非空，那么树中的最小键就是左子树中的最小键
- 如果根结点的右链接为空，那么一棵二叉查找树中最大的键就是根结点；如果右链接非空，那么树中的最大键就是右子树中的最大键
- 向上取整和向下取整
- 如果给定的键key小于二叉查找树的根结点的键，那么小于等于key的最大键floor(key)一定在根结点的左子树中
- 如果给定的键key大于二叉查找树的根结点，那么只有当根结点右子树中存在小于等于key的结点时，小于等于key的最大键才会出现在右子树中，否则根结点就是小于等于key的最大键
- 删除操作
- 思路
- 从其子结点中选取后继结点。后继结点的选取规则是，所有比被删除结点大的子结点中，最小的那个
- 代码操作方式
- 将指向即将被删除的结点的链接保存为t；将x指向它的后继结点min(t.right)
- 将x的右链接（原本指向一棵所有结点都大于x.key的二叉查找树）指向deleteMin(t.right)，也就是在删除后所有结点仍然都大于x.key的子二叉查找树
- 将x的左链接（本为空）设为t.left（其下所有的键都小于被删除的结点和它的后继结点）
- 思路
- 范围查找
- 我们首先需要一个遍历二叉查找树的基本方法，叫做中序遍历
- 将所有落在给定范围以内的键加入一个队列Queue并跳过那些不可能含有所查找键的子树
- 我们首先需要一个遍历二叉查找树的基本方法，叫做中序遍历
- 最大键和最小键
- 性能分析
- 总结
- 总结
- 定义
平衡查找树
- 2-3查找树
- 我们将一棵标准的二叉查找树中的结点称为2结点（含有一个键和两条链接），而现在我们引入3结点，它含有两个键和三条链接
- 定义
- 2结点，含有一个键（及其对应的值）和两条链接，左链接指向的23树中的键都小于该结点，右链接指向的23树中的键都大于该结点
- 3结点，含有两个键（及其对应的值）和三条链接，左链接指向的23树中的键都小于该结点，中链接指向的23树中的键都位于该结点的两个键之间，右链接指向的23树中的键都大于该结点
- 基本操作
- 查找：大于或者小于的情况类似，不过多了一种在三结点中如果目标值落在两个值中间，那么就要找中间的子结点
- 插入
- 向2-结点中插入键，那就把2-结点变成3-结点
- 向一棵只含有一个3-结点的树中插入新键，那就把3-结点变成4-结点，然后再分解成为2-3树
- 向一个父结点为2-结点的3-结点中插入新键，看图比较清楚，就不文字解释了
- 向一个父结点为3-结点的3-结点中插入新键，看图比价清楚，就不文字解释了
- 分解根结点
- 向2-结点中插入键，那就把2-结点变成3-结点
- 查找：大于或者小于的情况类似，不过多了一种在三结点中如果目标值落在两个值中间，那么就要找中间的子结点
- 这些局部变换不会影响树的全局有序性和平衡性：任意空链接到根结点的路径长度都是相等的
- 在一棵大小为N的2-3树中，查找和插入操作访问的结点必然不超过lgN个
- 需要考虑的变换情况太多，代码比较难完全顾及到，因此暂且看作是一个概念，作为其他树的基础
- 红黑二叉查找树
- 定义
- 红黑二叉查找树背后的基本思想是用标准的二叉查找树（完全由2-结点构成）和一些额外的信息（替换3-结点）来表示2-3树
- 红链接将两个2-结点连接起来构成一个3-结点
- 黑链接则是2-3树中的普通链接
- 这样的红黑树同时也满足：
- 红链接均为左链接
- 没有任何一个结点同时和两条红链接相连
- 该树是完美黑色平衡的，即任意空链接到根结点的路径上的黑链接数量相同
- 红黑树都既是二叉查找树，也是2-3树，将其平铺开来，就是一棵2-3树
- 实现方案
- 颜色表示
- 在结点中定义一个变量存储红黑值，规定指向它的父节点的链接如果是红色的，该变量定为true，如果是黑色则为false
- 在结点中定义一个变量存储红黑值，规定指向它的父节点的链接如果是红色的，该变量定为true，如果是黑色则为false
- 旋转
- 出现红色右链接或者两条连续的红链接时需要进行旋转
- 我们只是将用两个键中的较小者作为根结点变为将较大者作为根结点
- 插入新结点
- tips：可以理解为所有的插入都是新增一个红色的链接，而我们要处理的就是调整这个红色的链接，以保持红黑树中的平衡
- 向单个2- 结点中插入新键
- 如果新键在老键的左侧加入，那就是一个合理的红色结点，这个2- 结点会变成一个3- 结点（由一条红色左链接相连的两个2- 结点表示一个3- 结点）
- 如果新键在老键的右侧加入，那就是一个错误的红色结点，需要进行旋转，通过左旋来完成
- 向树底部的2- 结点插入新键
- 如果指向新结点的是父结点的左链接，那么父结点就直接成为了一个3- 结点
- 如果指向新结点的是父结点的右链接，这就是一个错误的3- 结点，但一次左旋转就能够修正它
- 向一棵双键树（即一个3- 结点）中插入新键
- 如果新键大于原3-结点中的两个值，加到父节点的右链接，此时出现两个红链接，因此调整为将两个红链接变黑，下面两种情况最终也会变成这种结果
- 如果新键小于原3-结点中的两个值，加到左子结点的左链接，此时左边链接出现连续两个红链接，此时进行两步操作
- 将父节点进行右旋
- 将两个红链接变黑
- 如果新键介于原3-结点的两个值中间，加到左子结点的右链接，此时出现右边的红链接，需要进行三步操作
- 将左子结点进行左旋，此时变成连续两个红链接
- 将父节点右旋
- 将两个红链接变黑
- 注意：上述过程将两个红链接变黑的情况下，也会将再上一层的父节点变红，如果这个变红的结点引起连锁的红黑树不平衡问题，也需要按照之前的原则进行转换
- 向树底部的3- 结点插入新键
- 跟上一种情况差不多，只不过多了一步父节点变红之后的转换
- 跟上一种情况差不多，只不过多了一步父节点变红之后的转换
- 将红链接在树中向上传递
- 如果右子结点是红色的而左子结点是黑色的，进行左旋转
- 如果左子结点是红色的且它的左子结点也是红色的，进行右旋转
- 如果左右子结点均为红色，进行颜色转换
- 删除操作
- 自上而下的2-3-4树
- 如果根结点是4结点，我们就将它分解成三个2结点，使得树高加1
- 如果遇到一个父结点为2结点的4结点，我们将4结点分解为两个2结点并将中间键传递给它的父结点，使得父结点变为一个3结点
- 如果遇到一个父结点为3结点的4结点，我们将4结点分解为两个2结点并将中间键传递给它的父结点，使得父结点变为一个4结点
- 用红黑树的方式实现2-3-4树
- 将4结点表示为由三个2结点组成的一棵平衡的子树，根结点和两个子结点都用红链接相连；
- 在向下的过程中分解所有4结点并进行颜色转换
- 和插入操作一样，在向上的过程中用旋转将4结点配平2
- 删除最小键
- 从树底部删除一个3-结点中的键最简单，删除最小键之后直接留下一个2-结点即可
- 从树底部删除一个2-结点的键，会留下一个空链接，破坏了树的平衡，所以我们的做法是把2-结点变成3-结点或者4-结点
- 如果当前结点的左子结点不是2结点，完成
- 如果当前结点的左子结点是2结点而它的亲兄弟结点不是2结点，将左子结点的兄弟结点中的一个键移动到左子结点中
- 如果当前结点的左子结点和它的亲兄弟结点都是2结点，将左子结点、父结点中的最小键和左子结点最近的兄弟结点合并为一个4结点，使父结点由3结点变为2结点或者由4结点变为3结点
- 一般删除
- 删除非树底部的结点，依然是按照删除最小键的逻辑，只是删除后需要按照二叉树查找后继结点的逻辑补上去
- 自上而下的2-3-4树
- 性能分析
- 一棵大小为N的红黑树的高度不会超过2lgN
- 一棵大小为N的红黑树中，根结点到任意结点的平均路径长度为lgN
- 颜色表示
- 定义
- 2-3查找树
散列表
- 散列算法
- 第一步是用散列函数将被查找的键转化为数组的一个索引。理想情况下，不同的键都能转化为不同的索引值。
- 第二步就是一个处理碰撞冲突的过程：：拉链法和线性探测法
- 散列函数
- 易于计算并且能够均匀分布所有的键，即对于任意键，0到M-1之间的每个整数都有相等的可能性与之对应
- 正整数
- 除留余数法：我们选择大小为素数M的数组，对于任意正整数k，计算k除以M的余数（用素数可以最大程度降低计算出重复的索引）
- 浮点数
- 如果键是0到1之间的实数，我们可以将它乘以M并四舍五入得到一个0至M-1之间的索引值
- 或者将键表示为二进制数然后再使用除留余数法（Java就是这么做的）
- 字符串
- 将字符串作为大整数即可
- 将字符串作为大整数即可
- 组合键
- 如果键的类型含有多个整型变量，我们可以和String类型一样将它们混合起来
int hash= ( ( ( day * R + month ) % M ) * R + year ) % M
- 如果键的类型含有多个整型变量，我们可以和String类型一样将它们混合起来
- java中的约定
- Java令所有数据类型都继承了一个能够返回一个32比特整数的hashCode()方法
- 每一种数据类型的hashCode()方法都必须和equals()方法一致
- a.equals(b)返回true，那么a.hashCode()的返回值必然和b.hashCode()的返回值相同
- 但如果两个对象的hashCode()方法的返回值相同，这两个对象也有可能不同，我们还需要用equals()方法进行判断
- 设计原则
- 一致性：等价的键必然产生相等的散列值
- 高效性：计算简便
- 均匀性：均匀地散列所有的键
- 拉链法
- 将大小为M的数组中的每个元素指向一条链表，链表中的每个结点都存储了散列值为该元素的索引的键值对
- 查找分两步：首先根据散列值找到对应的链表，然后沿着链表顺序查找相应的键
- 散列表的大小
- 选择适当的数组大小M，既不会因为空链表而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间
- 线性探测法
- 实现散列表的另一种方式就是用大小为M的数组保存N个键值对，其中M>N
- 我们需要依靠数组中的空位解决碰撞冲突。基于这种策略的所有方法被统称为开放地址散列表
- 具体做法
- 当碰撞发生时（当一个键的散列值已经被另一个不同的键占用），我们直接检查散列表中的下一个位置（将索引值加1），此时可能：
- 命中，该位置的键和被查找的键相同
- 未命中，键为空（该位置没有键）
- 继续查找，该位置的键和被查找的键不同。
- 例如：有下列键值对分别put，A-2，C-4，S-0，H-5。其中通过键值分别算出的散列值是A=4，C=5，S=6，H=4。可以看到，在A，C，S分别插入到数组中后，插入H时，4的位置已经有A了，此时顺延至5的位置，但是5的位置也有C，所以只能一直顺延至7的位置。
- 删除操作
- 删除就不能直接删除改键，因为有上述线性顺延的逻辑，可想而知，如果我们删除了C，那就没办法找到H，所以需要将被删除键的右侧所有键都重新插入散列表
- 当碰撞发生时（当一个键的散列值已经被另一个不同的键占用），我们直接检查散列表中的下一个位置（将索引值加1），此时可能：
- 开放地址类的散列表的性能也依赖于N/M的比值，但意义有所不同。我们将其称为散列表的使用率。对于基于拉链法的散列表，是每条链表的长度，因此一般大于1；对于基于线性探测的散列表，是表中已被占用的空间的比例，它是不可能大于1的
- 键簇
- 元素在插入数组后聚集成的一组连续的条目，也叫做键簇
- 在之前的例子中A-C-S-H就是一个键簇
- 长键簇更长的可能性比短键簇更大
- 当散列表快满的时候查找所需的探测次数是巨大的，保证N/M的值不大于1/2
- 散列表的弊端
- 每种类型的键都需要一个优秀的散列函数
- 性能保证来自于散列函数的质量
- 散列函数的计算可能复杂而且昂贵
- 难以支持有序性相关的符号表操作
- 散列算法
应用
- 相对二叉查找树，散列表的优点在于代码更简单，且查找时间最优（常数级别，只要键的数据类型是标准的或者简单到我们可以为它写出满足（或者近似满足）均匀性假设的高效散列函数即可）
- 二叉查找树相对于散列表的优点在于抽象结构更简单（不需要设计散列函数）
- 红黑树可以保证最坏情况下的性能且它能够支持的操作更多（如排名、选择、排序和范围查找）
- 使用原始数据类型进行存储键值可以更高效