基本概念
- 查找：在数据结构中寻找满足条件的元素的过程。查找可能成功或失败
- 查找表：用于查找的数据结构，支持插入，删除，查询元素，不支持插入删除的是静态查找表，否则是动态查找表
- 关键字：标识元素的数据项的值
- 平均查找长度ASL:给定每个元素的查找概率，计算出所有查找过程的平均关键字比较次数
顺序查找和折半查找
顺序查找
- 一般线性表顺序查找：从一端开始，逐个搜索关键字是否满足条件
- 有序表顺序查找：因为有序，有些失败的情况不一定要扫完整个表
- 可以用顺序存储或链式存储
- 可以用二叉树表示查找过程，叶子结点表示失败的情况，方便计算ASL
折半查找
- 适合有序的顺序存储表
- 每次和中间位置元素比较，若相等则查找成功，否则缩短一半的搜索范围
- 可以用二叉树表示查找过程，叶子结点表示失败的情况，方便计算ASL
分块查找
- 又叫索引顺序查找
- 结合了顺序查找和分块查找的优点
- 查找表分成若干子块，块内无序，块间有序
- 需要索引表，记录每个块最大关键字和第一个元素地址
- 查找先顺序查找或折半查找，确定元素所在块，再在块内顺序查找。
- 平均查找长度 = 分块查找的平均查找长度 + 块内查找的平均查找长度
红黑树
定义
- 结点是红色或黑色二叉查找树
- 根结点和叶结点（是空结点可忽略）都是黑色的
- 红色结点不能连续
- 根到所有叶结点路径上黑色结点个数相同
平衡性
- 叶子的普通深度不会超过2倍的其黑色深度
- 由黑色高度至少是
，则 - 所有叶结点的深度值不会超过两倍的差距
插入
- 插入结点z设置为红色
- 如果z是根结点，则z变成黑色，树黑高加1
- 如果z的父亲是黑色，则此时已经满足红黑树
- 如果z的父亲是红色（显然z必然有爷爷，从而必然有叔叔）
- 如果z的叔叔是黑色，根据z、z父亲、z爷爷的路径形状进行LL、LR、RR、RL旋转，同时调整z、z父亲、z爷爷的颜色，使得平衡后的子树树根为黑
- 如果z的叔叔是红色，则令z爷爷是红，z的父亲和叔叔变黑，此后把爷爷看作z，回到最开始步骤，继续向上层调整
删除
- 如果是非终端结点，则把后继值放入该结点，然后删除后继，注意此时只移动值，不改变颜色
- 如果是红色终端结点，或根结点，则直接删除
- 如果是黑色终端，且不是根结点（必然有父亲p，兄弟y，记m和n为y的孩子，且m靠近x的一侧），用NULL的双黑色（黑色计算两次）的叶结点x代替该删除结点，下面目标就是把双黑x变成单黑x
- 情况1：如果y为红色，此时p为黑，旋转y和p，并交换y和p的颜色，转情况2/3/4
- 情况2：如果y为黑色，m红，n黑，旋转m和y，并交换y和m的颜色，转情况3
- 情况3：如果y为黑色，n红，旋转y和p，交换y和p的颜色，x变单黑，n变黑，完成调整
- 情况4：如果y为黑色，m黑，n黑，则x变单黑，y变红
- p如果是根（必然是黑），不用变色，调整完成，调整前后总的黑色深度减1
- p如果是红色，则变为黑，调整完成。
- p如果是黑色，且不是根结点，则把p看作x，继续向根方向循环处理，运行情况1-4。
- 记忆
- 插入：叔叔黑色自身LR；叔叔红色往下拉
- 自身LR指的是，自身、自身的父亲、自身的爷爷三个人LR旋转
- LR后的子树根是黑色
- 删除：兄弟红色远侄LR、近侄红色近侄孙LR、远侄红色则远侄LR、都不红色则上拉
- 结束只能是第三个或第四个情况
- 第三个情况的子树根颜色不变
- 插入：叔叔黑色自身LR；叔叔红色往下拉
B树和B+树
B树
定义
- 又叫做多路平衡查找树
- B树结点孩子最大值是阶
- B树结点关键字个数是子树范围数减1
- 根若不是终端结点，根结点的子树数范围
- 除了根结点，其他结点的子树数范围
- 非叶结点包含：
是关键字个数 是关键字，从左到右递增 是关键字均小于 ，均大于 的子树
- 叶结点在最后一层，一般用空指针表示，代表查找失败的位置，叶结点数比树中总关键字数多1
高度（磁盘存取次数）
- 这里规定高度不包含叶结点，即根节点在第1层，叶结点在第h+1层
- 利用叶结点数是树中总关键字数加1，n+1最小是
，最大是 ，很容易求出给定关键字数情况下的B树高度的范围
查找
- 在B树中找结点，需要从磁盘中读
- 结点内顺序或折半查找关键字
- 起始结点是根结点
- 结点内查找失败则继续根据指针信息读子树，直到查找到叶结点（空指针），则查找失败
插入
- 定位：查找失败时定位到最底层的非叶结点的插入位置
- 插入
- 若插入后结点关键字个数小于等于m-1，可以直接插入
- 否则以结点中间关键字为分割位置，把结点分裂成两个结点，并把中间关键字放入父结点；若父节点关键字个数大于等于m，继续向上层分裂，直至传到根使得树高增1
删除
- 若删除的关键字不在最底层非叶结点（终端结点），则用该关键字前驱或后继代替，再删除前驱或后继
- 只需要考虑被删关键字在终端结点的情况
- 若结点关键字个数删除前大于等于
，则直接删除 - 兄弟够借
- 即结点关键字个数删除前等于
，邻近的兄弟结点关键字个数大于等于 - 则可以把兄弟结点关键字给父结点，父结点关键字给删除结点
- 即结点关键字个数删除前等于
- 兄弟不够借，即结点关键字个数删除前等于
，左右兄弟结点关键字个数等于 - 则结点删除关键字后，把该结点、左或右兄弟、该兄弟和删除结点在父结点中对应的关键字，合并到一个结点中
- 显然新结点关键字数为
，满足B树定义。 - 如果父结点关键字的减少使得父结点不满足定义，则继续向上处理。
- 如果处理到了父结点是根结点，则根结点删除，合并结点称为新的根结点
- 若结点关键字个数删除前大于等于
- 记忆
- 插入：分裂，中间给父，迭代
- 删除：兄弟够借，兄弟给父，父给我；兄弟不够借，兄弟和我和中间合并，父亲继续迭代
B+树
- 应数据库所需出现的B树的变形
- 定义：
- m阶B+树的一个结点最多有m个孩子
- 非叶根结点子树数至少
- 非叶其他结点子树数至少
- 结点关键字数等于子树数
- 叶结点包含所有关键字和相应的记录指针，叶子结点之间按大小顺序链接排列
- 分支结点的关键字指对应子树中最大关键字，分支结点包含指向该子树的指针
- 对比B树
- B+树结点关键字个数和子树相同，B树结点关键字比子树少1
- m阶B+树结点子树个数和m阶B树结点子树个数范围相同
- B+树的叶结点包含信息，非叶结点仅索引作用，无存储信息。B树的叶结点为空，对应查找失败。
- B+树的叶结点会重复出现分支结点的关键字，B树关键字不会重复
- B+树的多路查找一定是查找到叶结点为止，每次查找都是从根到叶的路径。B树的叶结点为空，且查找不一定到最底层非叶结点（终端结点）
- B+树有两个头指针
- 一个指向根结点，以多路查找
- 一个指向关键字最小的叶结点，以顺序查找
散列表
基本概念
- 散列函数：把关键字映射为地址的函数 Hash(key)=address
- 冲突：把不同的关键字映射到同一个地址，这些关键字叫同义词。冲突不可避免，但好的散列函数能减少冲突
- 散列表：根据关键字直接访问的数据结构
- 理想情况散列表查找时间开销是O(1)
散列函数构造方法
- 定义域包含所有关键字，值域依赖于散列表大小和地址范围
- 散列函数算出的地址最好能等概率均匀的分布在整个地址空间中，减少冲突
- 散列函数尽量简单，能快速算出
直接定址法
， 是常数 - 即直接取关键字的某线性函数
- 没有冲突，计算简单
- 适合关键字分布基本连续，否则空位较多造成存储浪费
除留余数法
， 是不大于散列表长且最接近或等于的质数 - 简单常用的方法，关键是选好
，使得关键字均匀映射到散列空间，减小冲突
数字分析法
- 设关键字是r进制数
- 关键字在各个位不一定分布都均匀
- 选取分布均匀的若干位作为散列地址
- 适合已知关键字集合，如果更换了关键字，则需要重新构造新散列函数
平方取中法
- 取关键字平方的中间几位作为散列地址
- 散列地址和关键字每个位都有关系，分布比较均匀，适合关键字每位取值都不均匀或者均小于散列地址所需位数的情况
处理冲突
开放地址法
- 即开地址法，Open-Hash
为增量序列，一般 - 线性探查法
，且 - 容易造成堆积
- 平方探查法
， 必须是 形式的素数 - 又叫二次探查法，可以避免堆积
- 缺点是不能探测到散列表所有单元，但至少能探测一半单元
- 再散列法
- 需要用到第二个哈希函数来解决冲突，又叫双重哈希法
- 最多m-1次再探测，都失败后回到
位置
- 伪随机序列法：
为伪随机数序列 - 注：开放地址法不能随便删除元素，可以增加标记位进行逻辑删除，定期维护散列表进行物理删除
拉链法
- 即闭地址法，Closed-Hash
- 把同义词存储在一个线性链表里
- 线性链表由散列地址唯一标识
散列查找和性能分析
- 散列查找和散列表构造的步骤相同
- 平均查找长度ASL衡量查找效率
- 同一组关键词和散列函数，冲突处理方法不同，开哈希闭哈希选择不同，ASL一般不一样
- 散列表的查找效率取决于
- 散列函数
- 冲突处理方法
- 装填因子
- 又叫负载因子
- 描述表满的程度，表越满，冲突发生的可能性越大
， 为表中记录数， 为散列表长度
补充说明
- 查找成功的平均查找长度为
- 查找失败的平均查找长度为
- 这里一般是认为
， - 如果综合考虑，即认为
也是一种理解，具体要根据题意分析
