25考研数据结构复习·7.4B树和B+树7.5散列（Hash）表

目录

B树和B+树

B树

m阶B树的核心特性

B树的插入

B树的删除

非终端结点关键字

终端结点关键字

低于下限

B+树

散列（Hash）表

基本概念

散列函数的构造

👩‍💻 除留余数法

直接定址法

数字分析法

平方取中法

处理冲突的方法——拉链法

插入操作

查找操作

删除操作

处理冲突的方法——开放定址法

基本原理

元素的操作

插入

查找

👩‍💻 删除

四种常用的“探测序列”

四种增量序列的“覆盖率

---

B树和B+树

B树

含n个关键字的m叉B树

m阶B树的核心特性

1. 👩‍💻 （尽可能“满”）根节点的子树∈[2,m]，关键字数∈[1,m-1]。其他结点的子树数∈[⌈m/2⌉,m]；关键字∈[⌈m/2⌉-1,m-1]
2. 👩‍💻（尽可能“平衡”）对任一结点，其所有子树高度都相同
3. 关键字的值：子树0<关键字1<子树1<关键字2<子树2<……（类比二叉查找树 左<中<右）

B树的插入

1. 通过“查找”确定插入位置（一定是在终端结点）
2. 若插入后结点关键字个数未超过上限，则无需做其他处理
3. 若插入后关键字个数超过上限，则需要将当前结点的中间元素放到父节点中，当前节点分裂为两个部分：该操作会导致父节点关键字个数+！，若父节点关键字个数也超过了上限，则需要再向上分裂；根节点的分裂会导致B树高度+1

B树的删除

非终端结点关键字

1. 用其直接前驱或直接后继替代其位置，转化为对”终端结点“的删除
2. 直接前驱：当前关键字左边指针所指子树中”最右下“的元素
3. 直接后继：当前关键字右边指针所指子树中”最坐下“的元素

终端结点关键字

删除后结点关键字个数未低于下限，无需任何处理

低于下限

1. 右兄弟够借，则用当前结点的后继、后继的后继依次顶替空缺
2. 左兄弟够借，则用当前结点的前驱，前驱的前驱依次顶替空缺
3. 左（右）兄弟不够借，则需要与父节点内的关键字、左（右）兄弟进行合并。合并后导致父节点关键字数量-1，可能需要继续合并。

B+树

	m阶B树	m阶B+树
类比	二叉查找树的进化 → m叉查找树	分块查找的进化 → 多级分块查找
关键字与分叉	n个关键字对应n+1个分叉（子树）	n个关键字对应n个分叉
结点包含的信息	所有结点中都包含记录的信息	只有最下层叶子节点才包含记录的信息（可使树更矮）
查找方式	不支持顺序查找。查找成功时，可能停在任何一层结点，查找速度”不稳定“	支持顺序查找。查找成功或失败都会到达最下一层结点，查找速度“稳定”
相同点	除根节点外，最少⌈m/2⌉个分叉（确保结点不能太”空“）任何一个结点的子树都要一样高（确保”绝对平衡“）

散列（Hash）表

基本概念

1. 散列表：又称哈希表，可以根据数据元素的关键字计算出它在散列表中的存储地址
2. 散列函数：建立了“关键字”→“存储地址”的映射关系
3. 同义词：若不同的关键字通过散列函数映射到同一个存储地址，则称它们为“同义词”
4. 冲突（碰撞）：在散列表中插入一个数据元素时，若插入的位置已经存储了其他元素，则这种情况视为“冲突（碰撞）”

散列函数的构造

👩‍💻 除留余数法

1. 散列地址：H(key) = key % p 其中，p通常是不大于散列表表长的最大质数
2. 适用场景：较为通用，只要关键字是整数即可

直接定址法

1. 散列地址：H(key) = a * key + b 其中，a和b是常数
2. 适用场景：关键字分布基本连续

数字分析法

1. 选取数码分布较为均匀的若干位作为散列地址
2. 适用场景：关键字集合已知，且关键字的某几个数码位分布均匀

平方取中法

1. 计算关键字的平方，取中间几位作为散列地址
2. 适用场景：关键字的每位取值都不够均匀

处理冲突的方法——拉链法

拉链法（又称链接法、链地址法）：把所有“同义词”存储在一个链表中

插入操作

1. 根据散列函数计算新元素的散列地址
2. 将新元素插入散列地址对应的链表（可用头插法或尾插法）

查找操作

1. 根据散列函数计算新元素的散列地址
2. 顺序查找散列列表对应的链表，直到查找成功或查找失败
3. 在分析查找长度时，通常只统计“关键字的对比次数”，而链表“空指针的对比次数”不计入查找长度

删除操作

1. 根据散列函数计算新元素的散列地址
2. 顺序查找散列地址对应的链表，若查找成功，将目标元素从链表中删除

处理冲突的方法——开放定址法

基本原理

当初始散列地址发生冲突时，根据“探测序列”探测下一个地址Hi=(H(key)+di)%m

元素的操作

插入

根据散列函数算出初始散列地址，若发生冲突，就“探测”下一个地址，直到找到一个空闲地址，即可插入元素

查找

根据散列函数算出初始散列地址，对比关键字，若关键字不匹配，就“探测”下一个地址，直到关键字匹配（成功）或探测到一个空位置（失败）

👩‍💻 删除

先按照“查找操作”的规则找到目标元素，若查找成功，就把目标元素“逻辑删除”。注意不能“物理删除”。

四种常用的“探测序列”

1. 👩‍💻 线性探测法：

2. 平方探测法：,.其中k≤m/2

3. 双散列法：.其中hash_2(key)是另一散列函数

4. 伪随机序列法：是一个伪随机序列，如

四种增量序列的“覆盖率”

1. 线性探测率：经过m-1次冲突，一定能探测到散列表的所有单元。
2. 平方探测法：一般来说，探测序列至少能覆盖到散列表的一半单元。若能保证表长m是一个可以表示成4x+3的素数，则可以探测到散列表的所有单元
3. 双散列法：若能保证hash2(key)的值和表长m互质，则经过m-1次冲突，一定能探测到散列表的所有单元
4. 伪随机序列法：只要伪随机序列设计和理论，就能 探测到全部单元