1.B树

1.1.B树的基本概念

1.B树的本质上就是多叉排序树：每个结点将树分成相应的区间

(1)根结点：（负无穷，22）（22，正无穷）

(2)根结点的左孩子：（负无穷，5）（5，11）（11，22）

(3)根结点的右孩子：（22，36）（36，45）（45，正无穷）

以此类推，结论：设该结点关键字个数为m，则该结点能形成m + 1个分区

(1)图中最少的结点为（22）：一个关键字，形成两个分区

2)图中最多的结点为（47，48，50，56）：四个关键字，形成五个分区

2.结点中关键字有序（可以使用折半查找）

3.除了根节点外，任何结点至少拥有⌈ m / 2 ⌉个分叉，即 ⌈ m / 2 ⌉ - 1 个关键字（尽可能降低树的高度，从而提升搜索效率）；最多含有 m - 1 个关键字，即 m 个分叉

4.叶子结点为失败结点（最后一层的紫色结点，不带信息，指向它们的指针为NULL），终端结点为关键字的最后一层（倒数第二层蓝色结点）

5.所有子树的高度都相等，即所有叶子结点都出现在同一层（绝对平衡，在满足3的情况下防止单边树出现）

6.若根节点不是终端结点，则至少拥有两棵子树（绝对平衡，满足5）

7.非叶子结点的结构中：n为该结点的关键字个数，p0 - pn 为区间指针，k1 - k2为结点的关键字（参考1）

8.n个关键字的B树必有n + 1个叶子结点（n个关键字将其划分为 n + 1 个区间）

1.2.B树的最大和最小高度（可以推）

1.最小高度hMin：每个结点的关键字为m - 1， 有m个分叉

即

因此，

2.最大高度hMax

1.2.B树的插入

1.新元素一定是插入到最底层的终端节点，通过查找来确定插入位置（子树0 < 关键字1 < 子树2 < 关键字2 ....）

2.对于m阶B树，当前结点的关键字个数为⌈ m / 2 ⌉ - 1 ≤ n ≤ (m - 1)

3.插入结点后若当前结点的关键字个数超过上限，则选择 ⌈ m / 2 ⌉ 向上进行分裂

设该树为5阶B树，即关键字最多为4个

1.插入25

2.插入38

3.插入49

4.插入60

5.插入80。此时（25，38，49，60，80）不满足5阶B树定义（结点中关键字最大个数为4）

选择第 ⌈ m / 2 ⌉ 个关键字，即49，新建根节点，并加入，它左边和右边的关键字分别为其的左右子树，并使存放数据49的左右指针指向它们

6.插入90

7.插入99

8.插入88。此时（60，80，88，90，99）不满足5阶B树定义（结点中关键字最大值为4）

选择第 ⌈ m / 2 ⌉ 个关键字，即88，加入根节点，它左边和右边的关键字分别为其的左右子树，并使存放数据88的左右指针分别指向它们

9.插入83

10.插入87

11. 插入70。此时（60，70，80，83，87）不满足5阶B树定义（结点中关键字最大值为4）

选择第 ⌈ m / 2 ⌉ 个关键字，即80，加入根节点（保存在根节点中指向该结点指针右边存放数据的位置），它左边和右边的关键字分别为其的左右子树，并使存放数据80的左右指针分别指向它们

12.依次插入92、93、94。此时（90，92，93，94，99）不满足5阶B树定义（结点中关键字最大值为4）

选择第 ⌈ m / 2 ⌉ 个关键字，即93，加入根节点（保存在根节点中指向该结点指针右边存放数据的位置），它左边和右边的关键字分别为其的左右子树，并使存放数据93的左右指针分别指向它们

13.依次插入73、74、75。此时（60，70，73，74，75）不满足5阶B树定义（结点中关键字最大值为4）

选择第 ⌈ m / 2 ⌉ 个关键字，即73，加入根节点（保存在根节点中指向该结点指针右边存放数据的位置），它左边和右边的关键字分别为其的左右子树，并使存放数据73的左右指针分别指向它们

此时（49，73，80，88，93）不满足5阶B树定义（结点中关键字最大值为4）

选择第 ⌈ m / 2 ⌉ 个关键字，即80，新建根节点，并加入，它左边和右边的关键字分别为其的左右子树，并使存放数据80的左右指针分别指向它们

1.3.B.树的删除

1.若删除的是非终端结点：找到直接前驱或者直接后继，并用其将被删除结点替换（将删除非终端结点转换为删除终端结点）

(1)直接前驱：找到左子树的最右下结点（二叉排序树的方法）

删除80

A.找到其左子树中最右下结点，即77

B.77替换80，80删除

(2)直接后继：找到右子树的最左下结点（二叉排序树的方法）

删除77

A.找到其右子树中最左下结点，即82

B.82替换77，77删除

2.若删除的元素为终端结点，且删除后结点元素个数＜⌈ m / 2 ⌉ - 1：兄弟够借和兄弟不够借

(1)兄弟够借：被删除结点的兄弟结点的元素个数 > ⌈ m / 2 ⌉ - 1

①找当前元素的后继、后继的后继依次顶替

删除38：

A.删除38

B.找到25的后继49，49的后继70

C.将49插入到存放25的结点，70顶替49的位置

②找当前元素的前驱、前驱的前驱依次顶替

删除90：

A.删除90

B.找到92的前驱88，88的前驱87

C.将88插入到存放92的结点，87顶替88的位置

(2)兄弟不够借：被删除结点的兄弟结点的元素个数 = ⌈ m / 2 ⌉ - 1，则将兄弟结点、被删除结点和双亲结点的关键字进行合并（该操作可能影响双亲结点的结点个数，若合并后不满足，则逐层递归合并；根节点合并后元素个数为0，则删除根节点）

删除49：

A.找到兄弟结点71、72，找到双亲结点的关键字70

B.进行合并

C.合并后其双亲结点不满足元素个数 ≥ ⌈ m / 2 ⌉ - 1 的要求，因此双亲结点、双亲结点的兄弟节点和双亲结点的双亲结点进行合并

2.B+树

1.每个分支结点最多有 m 个子树，m 个关键字对应 m 棵子树，即每个关键字对应一个子树（B树为 m 棵子树，但m - 1 个关键字分成 m 个区间，即 m 棵子树）

2.非叶根节点最少有两棵子树（B树为一棵子树），其他分支节点最少有 ⌈ m / 2 ⌉ 棵子树（B树为⌈ m / 2 ⌉ 棵子树）——目的是为了追求绝对平衡，保证左右高度相同

3.结点的子树个数和关键字个数相等，n 叉树有 n 个分叉（B树结点的子树个数为关键字个数 + 1—— n + 1个分叉，n 个 数据）

4.所有叶结点包含全部关键字（即分支结点中出现过的关键字在叶子结点中会重复出现，而B树中在分支结点出现过的关键字叶子结点不会出现，即每个关键字只出现一次）以及指向相应记录的指针（eg：B+树中存放的是学号，找到某人的学号后，该学号的记录指针可以指向他的个人信息），叶结点中关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接（可以通过叶子结点相互连接的指针进行顺序查找）

5.分支节点中仅起索引作用（使单个磁盘中能读取的元素的个数更多，从而增加检索效率），即仅包含其各个子树的最大值和指向这个含有这个最大值的子树的指针（类似分块查找的索引表，在分支节点中找到元素仅能找到指向它的指针，需要继续往下寻找直到叶子结点）（B树中每个结点都包含了关键字对应的存储地址）

6.B+树不管查找成功还是失败，都必须到存放叶子结点的最后一层（B树中，若在分支结点找到该元素，则查找成功，无需到叶子结点）

3.散列表

3.1.散列表的基本概念

散列表：关键字和存储地址具有直接关系

同义词：不同的关键字通过散列函数映射到同一个值

冲突：通过散列函数确定的位置已经存放元素

装填因子：表中记录数/散列表长度（装填因子越大，发生冲突概率越高，散列表查找效率越低）

3.2.散列函数的构造方法

目的：尽可能减少冲突

1.除留余数法：H(key) = key % p

取一个不大于 m 但最接近 m 或等于 m 的质数

2.直接定址法：H(key) = key 或者 H(key) = a - key

适用于关键字基本连续（不会产生冲突），例如学号

3.数字分析法：若不同数码出现概率不同，选择数码分布较为均与的若干位作为散列地址

适用于已知的关键字集合，例如手机号的存储，选择后几位作为散列地址

4.平方取中法：计算关键字的平方，并取其中间几位数字作为散列函数

3.3.处理冲突的方法

1.开放定址法：散列表中的空闲地址既能存放同义词，也能存放非同义词

d为增量序列

设表长为16，在第一次计算散列函数时，仅有可能存放在[0，12]的位置上，[13，15]只有通过同义词冲突时才有可能被存放

①线性探测法：发生冲突的时，依次查找下一个位置是否为空，d为0、1、2、3...

查找失败时，查找数组中的空位置算一次查找

删除元素时，不能简单的物理上删除元素，而是作删除标记，逻辑上删除（副作用：在查找的时候，可能会因逐一遍历逻辑删除的结点而浪费时间）

查找效率分析：

A查找成功：每个查找元素从初始散列函数计算得到的位置移动到的目标元素的移动次数相加 / 表中总元素个数

B查找失败：每个查找元素从初始散列函数计算得到的位置移动到第一个空元素的移动次数相加 / 第一次散列函数可能取值的个数

缺点：容易造成同义词、非同义词聚集的现象，从而严重影响查找效率

②平方探测法：d为0的平方，1的平方，-1的平方，2的平方，-2的平方..

③伪随机法：d为伪随机数列

④再散列法：第一个散列函数冲突时，使用第二个散列函数进行再散列

2.拉链法：所有的发生冲突的同义词用链表存储，适用于经常增、删的情况

①查找成功的平均长度：（1 * 6 + 2 * 4 + 3 * 1 + 4 * 1）/ 12 = 21 / 12

查找一次：（14、68、19、20、23、11）

查找两次：（1、55、84、10）

查找三次：（27）

查找四次：（79）

②查找失败的平均长度：（0 + 4 + 0 + 2 + 0 + 0 + 2 + 1 + 0 + 0 + 2 + 1） / 13 = 12 / 13 = 0.92

依次查找每个结点上挂着的指针的个数 / 第一次散列函数可能取值的个数（即0 - 12）

查找失败的时候空指针不算一次查找，即记作0